java LinkedList源码分析

首先介绍java集合，集合接口Collection，子接口List，Set，Queue。

LinkedList是子结构List的现实。而且它实现了Deque等其他界面，<E>-double ended queue双向队列，Cloneable， java.io.Serializable可克隆和可序列化结构，以及List下的子接口AbstractSequentiallist顺序获取结构。

LinkedList的特点适用于需要频繁添加删除的集合，因为它的添加删除速度远高于ArrayList，顺序遍历速度也高于ArrayList，但不适合随机获取数据。

使用thinking in java ：

--------------------------------------意思和上面一样，眼晕的同学直接跳过这一段。----------------------------------------

List：

Order is the most important feature of a L i s t ; it promises to maintain elements(interface) in a particular sequence. L i s t adds a number of methods to C o l l e c t i o n that allowinsertion and removal of elements in the middle of a L i s t . (This is recommendedonly for a L i n k e d L i s t . ) A L i s t will produce a L i s t I t e r a t o r , and using this youcan traverse the L i s t in both directions, as well as insert and remove elementsin the middle of the list (again, recommended only for a L i n k e d L i s t ).

LinkedList：

Provides optimal sequential access, with inexpensive insertions and deletions fromthe middle of the list. Relatively slow for random access. (Use A r r a y L i s tinstead.) Also has a d d F i r s t ( ) , a d d L a s t ( ) , g e t F i r s t ( ) , g e t L a s t ( ),r e m o v e F i r s t ( ) , and r e m o v e L a s t ( ) (which are not defined in any interfaces orbase classes) to allow it to be used as a stack, a queue, and a dequeue.

--------------------------------------意思和上面一样，眼晕的同学直接跳过这一段。----------------------------------------

顾名思义，LinkedList的实现原理是一个双向列表，每个节点都是Entry，数据推送完全是链表的操作，所以他的插入和删除速度很快，但很难用index找到它

LinkedList关键源码分析：

private transient Entry<E> header = new Entry<E>(null, null, null);

这个成员变量是LinkedList的关键，它在链表中没有实际的数据意义，是链表的标记(如果难以理解，则通俗地理解为链表的第一个无意义元素)，而且transient的修改表明它不会被序列化。header也可以作为队列末尾的元素，因为它是一个双向列表，所以header.next末尾元素后面的元素成为团队的首要元素。知道了这些，看看下面的添加方法

public void addFirst(E e) {addBefore(e, header.next);    } public void addLast(E e) {addBefore(e, header);    }

以上是两个添加函数，用这两个函数来解释LinkedList是如何向集合推送元素的

adddfirst向队列头添加元素，将元素添加到header中.next-队首元素前；

addlast没有向队列添加元素，而是在header之前添加元素；

让我们来看看addbefore(E e,Entry<E> entry)函数

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;    }

Entry的数据结构如下：

private static class Entry<E> {E element; // Entry是当前元素<E> next; // 接下来的元素，靠近lastentry<E> previous; // 以前的元素，靠近firstentry(E element, Entry<E> next, Entry<E> previous) {    this.element = element;    this.next = next;    this.previous = previous;}    }

如果您了解LinkedList的数据结构和推送方法，其他操作原理将很容易解决。这里有解释。其他代码留给有兴趣的人。我希望每个人都能共同提高自己的技术和综合素质