文章目录

(一)双向链表：简介
 (二)双向链表：clear
(三)双向链表：add
(四)双向链表：remove
(五)双向链表：测试
 (六)双向链表：总结
 (七)双向链表：源码分析

(一)双向链表：简介

首先增加成员变量，如下：

然后修改node(int index)方法，如下：

    private Node<E> node(int index) {
        rangeCheck(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;
        }
    }

(二)双向链表：clear

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

此时节点两两之间互相引用，但是还是会被JVM虚拟机销毁，因为JVM除了看对象是否被引用，还要是否被gc root对象引用

gc root对象之一：被栈指针（局部变量）指向的对象
如果节点间接被gc root对象引用着，也不会被销毁

(三)双向链表：add

头节点的prev和尾节点的next指向的都是null

此时如果想往2号节点的位置添加节点，不需要像之前那样通过node(int index)方法找前一个节点了，直接用prev就可以了

首先让前一位元素（1号节点）的next指向新节点

再让2号节点的prev指向新节点

再让新节点的next指向2号节点，prev指向1号节点，最后调整序号就可以了

初步代码如下：

但是我们还要处理一些特殊情况（往头节点/尾节点的位置添加）

最后考虑只有一个元素的情况，如下：

最开始什么都没有，Node<E> oldLast = last;获取的oldLast为null，后面执行oldLast.next = last;必然会报错

代码如下：

(四)双向链表：remove

假设我们要删除2号节点

首先让前一个结点（1号结点）的next指向后一个结点（3号结点）

再让后一个结点的prev指向前一个结点

此时2号元素没有被引用了，被销毁，最后重新调整序号就可以了

代码如下：

考虑边界情况后的完整代码如下：
（无非就是prev可能是null，next可能是null）

(五)双向链表：测试

测试代码如下：

	static void testList(List<Integer> list) {
	    list.add(11);
	    list.add(22);
	    list.add(33);
	    list.add(44);
	
	    list.add(0, 55); // [55, 11, 22, 33, 44]
	    list.add(2, 66); // [55, 11, 66, 22, 33, 44]
	    list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]
	
	    list.remove(0); // [11, 66, 22, 33, 44, 77]
	    list.remove(2); // [11, 66, 33, 44, 77]
	    list.remove(list.size() - 1); // [11, 66, 33, 44]
	
	    Asserts.test(list.indexOf(44) == 3);
	    Asserts.test(list.indexOf(22) == List.ELEMENT_NOT_FOUND);
	    Asserts.test(list.contains(33));
	    Asserts.test(list.get(0) == 11);
	    Asserts.test(list.get(1) == 66);
	    Asserts.test(list.get(list.size() - 1) == 44);
	
	    System.out.println(list);
	}

为了测试方便，修改代码如下：

测试结果如下：
（目前只修改了LinkedList里面的Node内部类的toString()方法）

(六)双向链表：总结

(七)双向链表：源码分析

JDK官方提供的LinkedList跟我们之前写的动态数组很相近，可以自己进去阅读源码

注意：JDK官方提供的LinkedList里面的clear()方法不仅断掉first和last两根线，还断掉了结点之间的线，如下：

目的是为了节省内存，比如在执行clear()方法的同时来了一个迭代器（属于gc root对象）引用最后面一个节点，因为后面的1、2、3节点都连接着，所以不会被销毁，但是迭代器要的只是4号节点

如果把节点之间的线也断掉，效果如下：

无关的节点就会被销毁，如下：