什么是双向链表？

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表的逻辑结构图解

在最后添加节点图解

在中间添加节点图解

删除节点图解

Java代码实现

/**
 * 双向链表
 * @author 爱吃鱼的乌贼
 *
 */
public class DoubleLink {
    private Node head;
    private Node tail;

    public DoubleLink() {
        //初始化链表
        head = new Node(0);
        //刚开始尾指针和头指针一样，只有一个节点
        tail = head;
    }
    //打印节点信息
    public void printNodes() {
        Node temp = head;
        while(temp!=null) {
            System.out.println("[data="+temp.data+";pre="+temp.pre+";next="+temp.next+"]");
            temp = temp.next;
        }
    }
    //1、在尾部添加节点
    public void addTailNode(Object newData) {
        //1、新生成一个节点
        Node newNode = new Node(newData);
        //2、把节点添加到最后
        tail.next = newNode;
        newNode.pre=tail;
        //3、新节点为尾节点
        tail = newNode;
    }

    //2、按data的顺序递增新增节点:这样子要从后往前找
    public void addDataNode(Object newData) {
        Node temp = tail;
        while(temp!=null) {
            if((Integer)newData>=(Integer)temp.data) {
                //就在这个位置添加
                //如果temp是tail则直接调用在最后添加即可
                if(temp==tail) {
                    addTailNode(newData);
                }else {
                    //若不是尾节点，则直接添加即可
                    Node newNode = new Node(newData);
                    newNode.next = temp.next;
                    newNode.pre = temp;
                    temp.next.pre =newNode; 
                    temp.next=newNode;
                }
                return;
            }
            temp = temp.pre;
        }
    }

    //3、删除节点：这里可以删除除了头节点的任意节点
    public void delDataNode(Object newData) {
        Node temp = head.next;
        while(temp!=null) {
            if(newData==temp.data) {
                //头节点
                if(temp==tail)  {
                    tail = temp.pre;
                    temp.pre.next=null;
                }else {    
                    temp.pre.next=temp.next;
                    temp.next.pre=temp.pre;
                }
                return;
            }
            temp = temp.next;
        }
    }




    public Node getHead() {
        return head;
    }
    public void setHead(Node head) {
        this.head = head;
    }
    public Node getTail() {
        return tail;
    }
    public void setTail(Node tail) {
        this.tail = tail;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }
    class Node{
        //数据域
        private Object data;
        //前驱
        private Node pre;
        //后继
        private Node next;

        public Node() {
            super();
        }

        @Override
        public String toString() {
            return "Node [data=" + data + "]";
        }

        public Node(Object data) {
            super();
            this.data = data;
        }
        public Object getData() {
            return data;
        }
        public void setData(Object data) {
            this.data = data;
        }
        public Node getPre() {
            return pre;
        }
        public void setPre(Node pre) {
            this.pre = pre;
        }
        public Node getNext() {
            return next;
        }
        public void setNext(Node next) {
            this.next = next;
        }

    }
}

其它变种自行实现！

代码测试

public class DoubleLinkTest {

    public static void main(String[] args) {
        DoubleLink doubleLink = new DoubleLink();
        doubleLink.addTailNode(1);
        doubleLink.addTailNode(2);
        doubleLink.addDataNode(4);
        doubleLink.addDataNode(3);
        doubleLink.printNodes();
        System.out.println("------------删除3-------------");
        doubleLink.delDataNode(3);
        doubleLink.printNodes();
        System.out.println("------------删除4-------------");
        doubleLink.delDataNode(4);
        doubleLink.printNodes();
        System.out.println("------------删除0-------------");
        doubleLink.delDataNode(0);
        doubleLink.printNodes();

    }

}

结果输出:

[data=0;pre=null;next=Node [data=1]]
[data=1;pre=Node [data=0];next=Node [data=2]]
[data=2;pre=Node [data=1];next=Node [data=3]]
[data=3;pre=Node [data=2];next=Node [data=4]]
[data=4;pre=Node [data=3];next=null]
------------删除3-------------
[data=0;pre=null;next=Node [data=1]]
[data=1;pre=Node [data=0];next=Node [data=2]]
[data=2;pre=Node [data=1];next=Node [data=4]]
[data=4;pre=Node [data=2];next=null]
------------删除4-------------
[data=0;pre=null;next=Node [data=1]]
[data=1;pre=Node [data=0];next=Node [data=2]]
[data=2;pre=Node [data=1];next=null]
------------删除0-------------
[data=0;pre=null;next=Node [data=1]]
[data=1;pre=Node [data=0];next=Node [data=2]]
[data=2;pre=Node [data=1];next=null]

总结

双向链表实现脑袋中一定要按每个节点都是对象来分析，而head，tail,pre,next,temp这些只是指针而已，坚持这个标准就不会乱。