双向链表

1、双向链表

单链表只能从头结点first开始访问链表中的数据元素，如果需要逆序访问单链表中的数据元素将极其低效。
使用双向链表可以很大程度的解决这个问题，双向链表是链表的一种，由节点组成，每个节点中都有两个指针（next和prev），分别指向前面的节点和后面的节点。结构如下

image.png

使用双向链表可以提升链表的综合性能：比如查找，可以根据index是否大于size的一半，如果大于一半就从last节点开始向前访问，如果小于一半就从first节点开始向后访问，最大的操作数量为size的一半。相比于单向链表操作数量可以节省一半。
当双向链表中只有一个元素时，链表的结构如下

image.png

2、双向链表的nodeIndex()

先来看下单向链表的实现

private Node<E> nodeIndex(int index) {
    checkIndex(index);
    Node<E> node = first;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

根据我们前面的分析来进行优化，在双向链表的实现如下

private Node<E> nodeIndex(int index) {
    checkIndex(index);
    Node<E> node = first;
    if (index <= size >> 1) {
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
    } else {
        node = last;
        for (int i = size-1; i > index; i--) {
            node = node.prev;
        }
    }
    return node;
}

3、双向链表的clear（）

单向链表中的实现如下

public void clear() {
    first = null;
    size = 0;
}

双向链表中的实现如下

public void clear() {
    first = null;
    last=null;
    size = 0;
}

将first和last设置成null，其实就是链表中的first和next不再指向头结点和尾结点了，但是各个节点之前还是互相引用的，垃圾回收真的能回收这些节点吗

image.png
将first和last设置成null，链表中的节点不再被GC Root对象LinkedList所引用，即使它们互相引用，依然还是可以被垃圾回收的。

2.1、JVM中GCRoot对象有那些

• 1、虚拟机栈中引用的对象
  虚拟机栈中的引用的对象可以作为GC Root。我们程序在虚拟机的栈中执行，每次函数调用都是一次入栈。在栈中包括局部变量表和操作数栈，局部变量表中的变量可能为引用类型(reference)，他们引用的对象即可作为GC Root。不过随着函数调用结束出栈，这些引用便会消失。
• 2、方法区中类静态属性引用的对象
  简单的说就是我们在类中使用的static声明的引用指向的对象，例如：

class Test{
    private static Person person= new Person(); //Person对象就是GC Root对象
} 

• 3、方法区中常量引用的对象
  简单的说就是我们在类中使用final声明的引用指向的对象，例如：

class Test{
    private final Person person= new Person(); //Person对象就是GC Root对象
} 

• 4、本地方法栈中引用的对象
  就是程序中native本地方法引用的对象。

3、双向链表的add方法

先来看下单向链表的add方法

public void add(int index, E element) {
    checkIndexForAdd(index);
    if (index == 0) {
        first = new Node<E>(element, first);
    } else {
        Node<E> preNode = nodeIndex(index - 1);
        preNode.next = new Node<>(element, preNode.next);
    }
    size++;
}

在每次添加元素的时候需要找到要添加位置的前一个位置的元素，对于双向链表由于有prev指针，就不需要找到前一个元素，我们只需要找到要添加位置的元素即可。

image.png

双向链表是实现如下：
先不考虑特殊情况（向index=0或index=size或链表中没有元素）：

public void add(int index, E element) {
    checkIndexForAdd(index);
    Node<E> nextNode = nodeIndex(index);
    Node<E> preNode = nextNode.prev;
    Node<E> node = new Node<>(preNode, element, nextNode);
    preNode.next = node;
    nextNode.prev = node;
    size++;
}

对于双向链表来说nextNode.prev可能为null，即当index=0时，此时调用preNode.next = node;会报空指针异常问题，所以需要对此做处理

public void add(int index, E element) {
    checkIndexForAdd(index);
    Node<E> nextNode = nodeIndex(index);
    Node<E> preNode = nextNode.prev;
    Node<E> node = new Node<>(preNode, element, nextNode);
    if (preNode == null) { // 等价于index==0
        first = node;
    } else {
        preNode.next = node;
    }
    nextNode.prev = node;
    size++;
}

除此之外还需要处理，向末尾添加元素的情况

public void add(int index, E element) {
    checkIndexForAdd(index);
    //向末尾添加元素
    if (index == size) {
        Node<E> oldLast = last;
        last = new Node<>(oldLast, element, null);
                oldLast.next = last;
    } else {
        Node<E> nextNode = nodeIndex(index);
        Node<E> preNode = nextNode.prev;
        Node<E> node = new Node<>(preNode, element, nextNode);
        // 等价于index==0，向链表头添加元素
        if (preNode == null) { 
            first = node;
        } else {
            preNode.next = node;
        }
        nextNode.prev = node;
    }
    size++;
}

还有一种情况需要处理：当链表为空时，进行添加元素。
当链表为空时，index==size==0，满足条件if(index==size)

public void add(int index, E element) {
    checkIndexForAdd(index);
    // 向末尾添加元素
    // 当链表为空时 index==size==0,
    if (index == size) {
        Node<E> oldLast = last;
        last = new Node<>(oldLast, element, null);
        //链表为空时oldLast为null
        if (oldLast == null) {
            first = last;
        } else {
            oldLast.next = last;
        }
    } else {
        Node<E> nextNode = nodeIndex(index);
        Node<E> preNode = nextNode.prev;
        Node<E> node = new Node<>(preNode, element, nextNode);
        // 等价于index==0，向链表头添加元素
        if (preNode == null) {
            first = node;
        } else {
            preNode.next = node;
        }
        nextNode.prev = node;
    }
    size++;
}

4、双向链表的remove方法

单向链表的实现如下：

public E remove(int index) {
    checkIndex(index);
    Node<E> oldNode = first;
    if (index == 0) {
        first = first.next;
    } else {
        Node<E> preNode = nodeIndex(index - 1);
        oldNode = preNode.next;
        preNode.next = preNode.next.next;
    }
    size--;
    return oldNode.element;
}

双向链表不考虑特殊情况下的实现

public E remove(int index) {
    checkIndex(index);
    Node<E> oldNode = nodeIndex(index);
    Node<E> preNode = oldNode.prev;
    Node<E> nexNode = oldNode.next;
    preNode.next = nexNode;
    nexNode.prev = preNode;
    size--;
    return oldNode.element;
}

我们知道双向链表中头结点的prev为null、尾结点的next为null，所以preNode和nextNode可能为null，处理如下：

public E remove(int index) {
    checkIndex(index);
    Node<E> oldNode = nodeIndex(index);
    Node<E> preNode = oldNode.prev;
    Node<E> nexNode = oldNode.next;
    // index==0时
    if (preNode == null) {
        first = nexNode;
    } else {
        preNode.next = nexNode;
    }
    // index==size-1
    if (nexNode == null) {
        last = preNode;
    } else {
        nexNode.prev = preNode;
    }
    size--;
    return oldNode.element;
}

到此为止双向链表的相关代码已经修改完毕，完整代码如下：

public class LinkedList<E> extends AbstractList<E> {
    private Node<E> first;
    private Node<E> last;

    private static class Node<E> {
        private E element;
        private Node<E> next;
        private Node<E> prev;

        public Node(Node<E> prev, E element, Node<E> next) {
            this.element = element;
            this.next = next;
            this.prev = prev;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();

            sb.append(prev == null ? null : prev.element).append("_");
            sb.append(element).append("_");
            sb.append(next == null ? null : next.element);
            return sb.toString();
        }

    }

    @Override
    public void add(int index, E element) {
        checkIndexForAdd(index);
        // 向末尾添加元素
        // 当链表为空时 index==size==0,
        if (index == size) {
            Node<E> oldLast = last;
            last = new Node<>(oldLast, element, null);
            // 链表为空时oldLast为null
            if (oldLast == null) {
                first = last;
            } else {
                oldLast.next = last;
            }
        } else {
            Node<E> nextNode = nodeIndex(index);
            Node<E> preNode = nextNode.prev;
            Node<E> node = new Node<>(preNode, element, nextNode);
            // 等价于index==0，向链表头添加元素
            if (preNode == null) {
                first = node;
            } else {
                preNode.next = node;
            }
            nextNode.prev = node;
        }
        size++;
    }

    /**
     * 查找位置为index的元素
     */
    private Node<E> nodeIndex(int index) {
        checkIndex(index);
        Node<E> node = first;
        if (index <= size >> 1) {
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    @Override
    public E get(int index) {
        Node<E> node = nodeIndex(index);
        return node.element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = nodeIndex(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    @Override
    public E remove(int index) {
        checkIndex(index);
        Node<E> oldNode = nodeIndex(index);
        Node<E> preNode = oldNode.prev;
        Node<E> nexNode = oldNode.next;
        // index==0时
        if (preNode == null) {
            first = nexNode;
        } else {
            preNode.next = nexNode;
        }
        // index==size-1
        if (nexNode == null) {
            last = preNode;
        } else {
            nexNode.prev = preNode;
        }
        size--;
        return oldNode.element;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null)
                    return i;
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element))
                    return i;
                node = node.next;
            }
        }
        return -1;
    }

    @Override
    public void clear() {
        first = null;
        last = null;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size=" + size + " [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            sb.append(node);
            if (i != size - 1)
                sb.append(" , ");
            node = node.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

5、双向链表 VS 单向链表

image.png

虽然双向链表和单向链表一样，平均复杂度都为O(n)，但是双向链表的操作数量却是单向链表的一半。
其实get()、set()、add()、remove()中都使用了nodeIndex()方法，根据这个方法可知，平均复杂度=（1+2+3...+n/2）*2/n=1/2+n/4
而单向链表的平均复杂度=（1+2+3...+n）/n=1/2+n/2。由此可见双向链表的操作数量比单向链表缩减了近一半。

6、双向链表 VS 动态数组

• 动态数组开辟、销毁内存空间的次数较少，但是可能会造成内存的浪费（可通过缩容进行处理）。
• 双向链表开辟、销毁内存空间的次数较多，但不会造成内存空间的浪费。
• 如果频繁的在尾部进行添加、删除操作，动态数组、双向链表均可选择。
• 如果频繁的在头部进行添加、删除操作，建议选择双向链表。
• 如果频繁的在任意位置进行添加、删除操作，建议选择双向链表。
• 如果频繁的查询操作，建议选择动态数组。