LinkedList介绍

还是和ArrayList同样的套路，顾名思义，linked，那必然是基于链表实现的，链表是一种线性的储存结构，将储存的数据存放在一个存储单元里面，并且这个存储单元里面还维护了下一个存储单元的地址。在LinkedList的链表储存单元中，不仅存放了下一个存储单元的地址，还存放了上一个单元的储存地址，因为Linked是双向链表，双向链表就是可以通过链表中任意一个存储单元可以获取到上一个存储单元和下一个存储单元。

先看一下这个神秘的储存单元，在LinkedList的内部类中声明：

复制代码
private static class Node<E> {      E item;      Node<E> next;      Node<E> prev;       Node(Node<E> prev, E element, Node<E> next) {          this.item = element;          this.next = next;          this.prev = prev;      } }
复制代码

Node就是LinkedList的储存单元，在JDK1.6中叫Entry，不过结构还是一样的，里面有三个变量一个带这三个参数的构造方法，这三个变量分别是

1.item：存储在存储单元Node中的元素

2.next：下一个存储单元

3.prev：下一个存储单元

 

LinkedList的关注点

1.是否允许为空：是

2.是否允许重复数据：是

3.是否有序：是

4.是否线程安全：否

和之前讲的ArrayList的四个关注点一模一样

LinkedList的声明：

复制代码
public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {     transient int size = 0;      transient Node<E> first;      transient Node<E> last;      ... }
复制代码

LinkedList除了实现List、Cloneable和Serializable接口外还实现了Deque接口，说明LinkedList具有队列的特性，可以当做队列使用

举个简单的小栗子：

复制代码
1 List<String> list= new LinkedList<>(); 2 list.add("11"); 3 list.add("22"); 4 list.add("33");
复制代码

LinkedList提供了两种构造方法，例子使用的是第一种也是最常用的无参构造器：

public LinkedList() { }

这个构造方法没有执行其他任何的操作，这与jdk1.6有所不同，jdk1.6中声明了一个header节点，然后执行了 header.next = header.previous = header，jdk1.8中声明了first和last两个节点，但是构造的时候没有操作这两个节点。

第二种构造器和ArrayList一样提供了一个传入集合的构造方法public LinkedList(Collection<? extends E> c) 

添加元素

接着看第二行list.add("11")做了什么：

复制代码
 1 public boolean add(E e) {  2      linkLast(e);  3      return true;  4 }  5  6 void linkLast(E e) {  7      final Node<E> l = last;  8      final Node<E> newNode = new Node<>(l, e, null);  9      last = newNode; 10      if (l == null) 11          first = newNode; 12