初识LinkedList

上一篇中讲授了ArrayList，本篇文章讲授一下LinkedList的实现。

LinkedList是基于链表实现的，所以先讲授一下什么是链表。链表原先是C/C++的观念，是一种线性的存储布局，意思是将要存储的数据存在一个存储单位内里，这个存储单位内里除了存放有待存储的数据以外，还存储有其下一个存储单位的地点（下一个存储单位的地点是须要的，有些存储布局还存放有其前一个存储单位的地点），每次查找数据的时候，通过某个存储单位中的下一个存储单位的地点寻找其后头的谁人存储单位。

这么讲大概有点抽象，先提一句，LinkedList是一种双向链表，双向链表我认为有两点寄义：

1、链表中任意一个存储单位都可以通过向前可能向后寻址的方法获取到其前一个存储单位和其后一个存储单位

2、链表的尾节点的后一个节点是链表的头结点，链表的头结点的前一个节点是链表的尾节点

LinkedList既然是一种双向链表，一定有一个存储单位，看一下LinkedList的根基存储单位，它是LinkedList中的一个内部类：

private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;
    ...
}

看到LinkedList的Entry中的”E element”，就是它真正存储的数据。”Entry<E> next”和”Entry<E> previous”暗示的就是这个存储单位的前一个存储单位的引用地点和后一个存储单位的引用地点。用图暗示就是：

四个存眷点在LinkedList上的谜底

添加元素

首先看下LinkedList添加一个元素是怎么做的，如果我有一段代码：

public static void main(String[] args)
{
     List<String> list = new LinkedList<String>();
     list.add("111");
     list.add("222");
}

逐行阐明main函数中的三行代码是如何执行的，首先是第3行，看一下LinkedList的源码：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    private transient Entry<E> header = new Entry<E>(null, null, null);
    private transient int size = 0;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
        header.next = header.previous = header;
    }
    ...
}

看到，new了一个Entry出来名为header，Entry内里的previous、element、next都为null，执行结构函数的时候，将previous和next的值都配置为header的引用地点，照旧用绘图的方法暗示。32位JDK的字长为4个字节，而今朝64位的JDK一般回收的也是4字长，所以就以4个字长为单元。header引用地点的字长就是4个字节，假设是0×00000000，那么执行完”List<String> list = new LinkedList<String>()”之后可以这么暗示：

接着看第4行add一个字符串”111″做了什么：

public boolean add(E e) {
     addBefore(e, header);
     return true;
}

private Entry<E> addBefore(E e, Entry<E> entry) {
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
}

第2行new了一个Entry出来，大概不太好领略，按照Entry的结构函数，我把这句话”翻译”一下，大概就好领略了：

1、newEntry.element = e;

2、newEntry.next = header.next;

3、newEntry.previous = header.previous;

header.next和header.previous上图中已经看到了，都是0×00000000，那么假设new出来的这个Entry的地点是0×00000001，继承绘图暗示：

一共五步，每一步的操纵步调都用数字暗示出来了：

1、新的entry的element赋值为111;

2、新的entry的next是header的next，header的next是0×00000000，所以新的entry的next即0×00000000;

3、新的entry的previous是header的previous，header的previous是0×00000000，所以新的entry的next即0×00000000;