一、双向链表是什么？
使用双向链表是可以提升链表的综合性能的。一张图就可以表示得很清楚了
二、双向链表自实现
1.node方法（根据下标查找元素）
private Node<E> node(int index) { rangeCheck(index);//这是自己封装的一个检查函数，用来检查index的合法性，否则抛出异常 if (index < (size >> 1)) { Node<E> node = first; for (int i = 0; i < index; i++) { node = node.next; } return node; } else { Node<E> node = last; for (int i = size - 1; i > index; i--) { node = node.prev; } return node; } }
根据下标找出对应的节点，如果是单链表，则要从头到尾挨个找，但是对于双链表，我们可以先判断下标索引值与链表长度的一半进行对比，如果小于长度的一半，则可以从链表的头开始查找，如果大于了长度的一半，则可以从尾开始查找。
2.add (添加元素）
public void add(int index, E element) { rangeCheckForAdd(index); //这是自己封装的一个检查函数，用来检查index的合法性，否则抛出异常 // size == 0 // index == 0 if (index == size) { // 往最后面添加元素 Node<E> oldLast = last; last = new Node<>(oldLast, element, null); if (oldLast == null) { // 这是链表添加的第一个元素 first = last; } else { oldLast.next = last; } } else { Node<E> next = node(index); Node<E> prev = next.prev; Node<E> node = new Node<>(prev, element, next); next.prev = node; if (prev == null) { // index == 0 first = node; } else { prev.next = node; } } size++; }
3.remove(删除元素）
public E remove(int index) { rangeCheck(index); //这是自己封装的一个检查函数，用来检查index的合法性，否则抛出异常 Node<E> node = node(index); Node<E> prev = node.prev; Node<E> next = node.next; if (prev == null) { // index == 0 first = next; } else { prev.next = next; } if (next == null) { // index == size - 1 last = prev; } else { next.prev = prev; } size--; return node.element; }
4.clear分析
public void clear() { size = 0; first = null; last = null; }
按照之前咱们一般的理解，此时虽然已经把first和last置空了，与链表失去了联系，但是链表中的各个节点都相互指向，都被引用着，所以认为此时双链表不会被JVM回收。错了！！！此时链表相互指向的引线的性质已经变了，他们已经不再是gc root对象了。对于什么是gc root对象，简单的理解就是在栈中被局部变量指向的对象。所以此时clear这个函数是可以的。
三、双向链表 vs 单向链表
粗略对比一下删除的操作数量：
◼ 单向链表： 1 + 2 + 3 + ... + n = (1+n) ∗ n/ 2 = n/2 + n^ 2/ 2 ，除以n平均一下是 1/2 + n/2
◼ 双向链表： (1 + 2 + 3 + ... + n/2 ) * 2 = ((1+ n/2)∗ n/2 )/2 * 2 = n/2 + n^2/4 ，除以n平均一下是 1/2 + n/4
经过对比， 操作数量减少了一半
四、双向链表 vs 动态数组
◼动态数组 ：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费
◼ 双向链表 ：开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费
◼ 如果频繁在 尾部 进行 添加 、 删除 操作， 动态数组 、 双向链表 均可选择
◼ 如果频繁在 头部 进行 添加 、 删除 操作，建议选择使用 双向链表
◼ 如果有频繁的（ 在任意位置 ） 添加 、 删除 操作，建议选择使用 双向链表
◼ 如果有频繁的 查询 操作（随机访问操作），建议选择使用 动态数组
