双链表原理

双向链表的实现就是在单链表基础上又增加了一个指向前面节点的引用。原理图如下：

因为头节点是没有前驱节点的，所以头节点的 prev 是 null ，而尾节点是没有下一个节点的，所以尾节点的 next 是 null 。

双链表实现

定义节点

写一个类，将节点的值，前一个节点，后一个节点封装到类里面。并且在主类里面定义一个头（head）和尾（last）。

class ListNode{
    public int val;
    public ListNode PRev;
    public ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}

输出节点

这里的打印还是和之前单链表的打印方法一样，通过遍历节点来输出。当节点的 next 为 null 的时候，就说明到了最后一个节点。代码如下：

public void display(){
    ListNode cur = this.head;
    while (cur != null){
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

得到链表的长度

求长度和求单链表的长度一样，也和上面输出的方法一样，只要遍历一次，定义一个 count 每次加 1 就可以了。代码如下：

public int size(){
    ListNode cur = this.head;
    int count = 0;
    while (cur != null){
        count++;
        cur = cur.next;
    }
    return count;
}

查找是否包含关键字 key 在链表当中

这里的查找方法也和单链表一样，从头开始遍历，比较每个节点的值，如果是 key 的话，返回 true ，否则返回 false 。代码如下：

public boolean contains(int key){
    ListNode cur = this.head;
    while (cur != null){
        if(cur.val == key){
            return true;
        }
        cur = cur.next;
    }
    return false;
}

头插法

要注意插入的时候要先判断是不是第一次插入，也就是当前的链表是否为 null 。如果是空，要单独处理。如果不是第一次插入，就让插入的节点的 next 指向原来的头节点，原来的头节点的 prev 指向当前插入的节点。代码如下：

public void addFirst(int data) {
    ListNode node = new ListNode(data);
    //判断是不是第一次
    if(this.head == null || this.last == null){
        this.head = node;
        this.last = node;
        return;
    } else {
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }
}

下面进行测试：

public static void main(String[] args) {
    MyLinkedList myLinkedList = new MyLinkedList();
    myLinkedList.adDFirst(1);
    myLinkedList.addFirst(2);
    myLinkedList.addFirst(3);
    myLinkedList.addFirst(4);
    myLinkedList.addFirst(5);
    System.out.println(myLinkedList.size());
    myLinkedList.display();
    System.out.println(myLinkedList.contains(3));
}

输出如下：

尾插法

尾插法的原理也和头插法类似，也要判断是否为第一次插入。如果是的话，要单独处理。如果不是的话，就让原来尾节点的 next 指向插入的节点，插入节点的 prev 指向原来的尾节点。代码如下：

public void addLast(int data){
    ListNode node = new ListNode(data);
    if (this.head == null){
        this.head = node;
        this.last = node;
    } else {
        this.last.next = node;
        node.prev = this.last;
        this.last = node;
    }
}

测试代码如下：

public static void main(String[] args) {
    MyLinkedList myLinkedList = new MyLinkedList();
    myLinkedList.addLast(1);
    myLinkedList.addLast(2);
    myLinkedList.addLast(3);
    myLinkedList.addLast(4);
    myLinkedList.addLast(5);
    myLinkedList.display();
}

测试结果：

删除第一次出现关键字为key的节点

在删除的时候，只需要将节点的上一个的 next 指向当前节点的 next 下一个节点的 prev 指向当前节点的 prev 。当然也要分是不是头节点和不是头节点的情况。如果是头节点，那么又分为是不是只有一个节点。如果是不是头节点的情况的话，又要分为是不是尾节点。如果是尾节点，也要单独处理。代码如下：

public void remove(int key){
    ListNode cur = this.head;
    while (cur != null){
        if(cur.val == key){
            if(cur == head){//处理头节点
                head = head.next;
                if(head != null) {//如果只有一个节点
                    head.prev = null;
                } else {
                    last = null;
                }
            } else {//处理非头节点
                if(cur == last){//处理尾节点
                    cur.prev.next = cur.next;
                    last = last.prev;
                } else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            return;
        } else {
            cur = cur.next;
        }
    }
}

测试：

public static void main(String[] args) {
    MyLinkedList myLinkedList = new MyLinkedList();
    myLinkedList.addLast(1);
    myLinkedList.addLast(2);
    myLinkedList.addLast(3);
    myLinkedList.addLast(4);
    myLinkedList.addLast(5);
    myLinkedList.display();
    myLinkedList.remove(3);
    myLinkedList.display();
}

测试结果如下：

找到要插入位置的节点

在我们需要在任意位置插入的时候，要先找到这个位置的节点，然后再进行插入。代码如下：

public ListNode seArchNode(int index){
    ListNode cur = this.head;
    while (index != 0){
        cur = cur.next;
        index--;
    }
    return cur;
}

在任意位置插入一个数据节点

在插入的时候，先找到位置，然后在修改节点的指向即可完成插入，但也要判断位置是否合法。代码如下：

public void addIndex(int index,int data){
    ListNode node = new ListNode(data);
    if(index < 0|| index > size()){
        System.out.println("index 位置不合法");
        return;
    }
    if(index == 0){
        addFirst(data);
        return;
    }
    if(index == size()){
        addLast(data);
        return;
    }
    ListNode cur = searchNode(index);
    node.next = cur.prev.next;
    cur.prev.next = node;
    node.prev = cur.prev;
    cur.prev = node;
}

测试：

public static void main(String[] args) {
    MyLinkedList myLinkedList = new MyLinkedList();
    myLinkedList.addLast(1);
    myLinkedList.addLast(2);
    myLinkedList.addLast(3);
    myLinkedList.addLast(4);
    myLinkedList.addLast(5);
    myLinkedList.addIndex(0,99);
    myLinkedList.addIndex(3,99);
    myLinkedList.display();
}

删除所有值为 key 的节点

这里的删除方法和上面的删除一个 key 的节点一样，不过不需要 return 了，让其循环结束就可以了。代码如下：

public void remove(int key){
    ListNode cur = this.head;
    while (cur != null){
        if(cur.val == key){
            if(cur == head){//处理头节点
                head = head.next;
                if(head != null) {//如果只有一个节点
                    head.prev = null;
                } else {
                    last = null;
                }
            } else {//处理非头节点
                if(cur == last){//处理尾节点
                    cur.prev.next = cur.next;
                    last = last.prev;
                } else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
        } else {
            cur = cur.next;
        }
    }
}

测试：

public static void main(String[] args) {
    MyLinkedList myLinkedList = new MyLinkedList();
    myLinkedList.addLast(1);
    myLinkedList.addLast(2);
    myLinkedList.addLast(3);
    myLinkedList.addLast(4);
    myLinkedList.addLast(5);
    myLinkedList.addIndex(3,99);
    myLinkedList.addIndex(0,99);
    myLinkedList.addIndex(7,99);
    myLinkedList.display();
    myLinkedList.removeAllKey(99);
    myLinkedList.display();
}

清空链表

因为在使用链表的时候，可能每个节点都可能会有引用。如果不把引用置为空的话，就还会占用内存。所有在清空链表的时候，我们应该把每个引用置为 null 。代码如下：

public void clear(){
    while (head != null){
        ListNode curNext = head.next;
        head.next = null;
        head.prev = null;
        head = curNext;
    }
    last = null;
}

演示：

public static void main(String[] args) {
    MyLinkedList myLinkedList = new MyLinkedList();
    myLinkedList.addLast(1);
    myLinkedList.addLast(2);
    myLinkedList.addLast(3);
    myLinkedList.addLast(4);
    myLinkedList.addLast(5);
    myLinkedList.display();
    myLinkedList.clear();
    myLinkedList.display();
}