Linkedlist源码详解

介绍

LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个次序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。如许看来，LinkedList简直就是个万能冠军。当你需要利用栈大概队列时，可以思量利用LinkedList，一方面是因为Java官方已经声明不建议利用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类(它是个接口名字，无法直接创建)。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList(看成栈或队列利用时)有着更好的性能。
对于频繁的插入或删除元素的操纵，建议利用LinkedList类，服从较高；底层利用双向链表存储

1. //存储链表的第一个节点
2. transient Node<E> first;
4. //存储链表的最后一个节点
5. transient Node<E> last;

复制代码

LinkedList的实现方式决定了所有跟下标相关的操纵都是线性时间，而在首段大概末端删除元素只需要常数时间。为寻求服从LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先接纳Collections.synchronizedList()方法对其举行包装。
底层实现

底层数据布局

LinkedList底层通过双向链表实现。双向链表的每个节点用内部类Node表现。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元（也就是没有虚拟变量），当链表为空的时间first和last都指向null。

1. transient int size = 0;
3. /**
4. * Pointer to first node.
5. * Invariant: (first == null && last == null) ||
6. *            (first.prev == null && first.item != null)
7. */
8. transient Node <E> first;
10. /**
11. * Pointer to last node.
12. * Invariant: (first == null && last == null) ||
13. *            (last.next == null && last.item != null)
14. */
15. transient Node <E> last;

复制代码

此中Node是私有的内部类:

1. private static class Node <E> {
2.     E item;
3.     Node <E> next;
4.     Node <E> prev;
6.     Node(Node <E> prev, E element, Node <E> next) {
7.         this.item = element;
8.         this.next = next;
9.         this.prev = prev;
10.     }
11. }

复制代码

构造函数

[code] /**  * Constructs an empty list.  */ public LinkedList() {} /**  * Constructs a list containing the elements of the specified  * collection, in the order they are returned by the collection's  * iterator.  *  * @param  c the collection whose elements are to be placed into this list  * @throws NullPointerException if the specified collection is null  */ public LinkedList(Collection