ArrayList随机访问效率很高，但插入和删除性能比较低；LinkedList同样实现了List接口，它的特点与ArrayList几乎正好相反。除了实现了List接口外，LinkedList还实现了Deque和Queue接口，可以按照队列、栈和双端队列的方式进行操作。本节会介绍这些用法，同时介绍其实现原理。

基本用法

LinkedList的构造方法与ArrayList类似，有两个：一个是默认构造方法，另外一个可以接受一个已有的Collection，如下所示：

public LinkedList()public LinkedList(Collection c)

创建如下：

List list = new LinkedList();

LinkedList与ArrayList一样，同样实现了List接口，而List接口扩展了Collection接口，Collection又扩展了Iterable接口，所有这些接口的方法都是可以使用的。
LinkedList还实现了队列接口Queue,所谓队列就类似于日常生活中的各种排队，特点就是先进先出，在尾部添加元素，从头部删除元素，它的接口定义为：

public interface Queue extends Collection { boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek();}

Queue扩展了Collection,它的主要操作有三个：
·在尾部添加元素（add、offer）;
·查看头部元素(element、peek),返回头部元素，但不改变队列；
·删除头部元素(remove、poll),返回头部元素，并且从队列中删除。

每种操作都有两种形式，有什么区别呢？区别在于，对于特殊情况的处理不同。特殊情况是指队列为空或者队列为满，为空容易理解，为满是指队列有长度大小限制，而且已经占满了。LinkedList的实现中，队列长度没有限制，但别的Queue的实现可能有。在队列为空时，element和remove会抛出异常NoSuchElementException，而peek和poll返回特殊值null；在队列为满时，add会抛出异常IllegalStateException，而offer只是返回false。

Java中没有单独的栈接口，栈相关方法包括在了表示双端队列的接口Deque中，主要有三个方法：

1)push表示入栈，在头部添加元素，栈的空间可能是有限的，如果栈满了，push会抛出异常
IllegalStateException。
2)pop表示出栈，返回头部元素，并且从栈中删除，如果栈为空，会抛出异常NoSuch-
ElementException。
3)peek查看栈头部元素，不修改栈，如果栈为空，返回null。

Java中有一个类Stack,它也实现了栈的一些方法，如push/pop/peek等，但它没有实现Deque接口，它是Vector的子类，它增加的这些方法也通过synchronized实现了线程安全，具体就不介绍了。不需要线程安全的情况下，推荐使用LinkedList或ArrayDeque。

栈和队列都是在两端进行操作，栈只操作头部，队列两端都操作，但尾部只添加、头部只查看和删除。有一个更为通用的操作两端的接口Deque。Deque扩展了Queue,包括了栈的操作方法，此外，它还有如下更为明确的操作两端的方法：

void addFirst(E e);void addLast(E e);E getFirst();E getLast();boolean offerFirst(E e);boolean offerLast(E e);E peekFirst();E peekLast();E pollFirst();E pollLast();E removeFirst();E removeLast();

xxxFirst操作头部，xxxLast操作尾部。与队列类似，每种操作有两种形式，区别也是在队列为空或满时处理不同。为空时，getXXX/removeXXX会抛出异常，而peekXXX/polIXXX会返回null。队列满时，addXXX会抛出异常，offerXXX只是返回false。

栈和队列只是双端队列的特殊情况，它们的方法都可以使用双端队列的方法替代，不过，使用不同的名称和方法，概念上更为清晰。

简单总结下：LinkedList的用法是比较简单的，与ArrayList用法类似，支持List接口，还增加了一个接口Deque,可以把它看作队列、栈、双端队列，方便地在两端进行操作。如果只是用作List,那应该用ArrayList还是LinkedList呢？我们需要了解LinkedList的实现原理。

实现原理

我们知道，ArrayList内部是数组，元素在内存是连续存放的，但LinkedList不是。LinkedList直译就是链表，确切地说，它的内部实现是双向链表，每个元素在内存都是单独存放的，元素之间通过链接连在一起。

为了表示链接关系，需要一个节点的概念。节点包括实际的元素，但同时有两个链接，分别指向前一个节点（前驱）和后一个节点（后继）。节点是一个内部类，具体定义为：

private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; }}

Node类表示节点，item指向实际的元素，next指向后一个节点，prev指向前一个节点。
LinkedList内部组成就是如下三个实例变量：

transient int size = 0;transient Node first;transient Node last;

LinkedList的所有public方法内部操作的都是这三个实例变量，我们看一些主要的方法：

add方法的代码为：

public boolean add(E e) { linkLast(e); return true;}

主要就是调用了linkLast,它的代码为：

void linkLast(E e) { final Node l = last; final Node newNode = new Node(l, e, null); last = newNode; if(l == null) first = newNode; else l.next = newNode; size++; modCount++; }

代码的基本步骤如下。
1)创建一个新的节点newNode。1和last指向原来的尾节点，如果原来链表为空，则为null。代码为：Node newNode = new Node(1, e, null);
2)修改尾节点last,指向新的最后节点newNode。代码为：last = newNode;
3)修改前节点的后向链接，如果原来链表为空，则让头节点指向新节点，否则让前一个节点的next指向新节点。同时增加链表大小。

modCount++的目的与ArrayList是一样的，记录修改次数，便于迭代中间检测结构性变化。

我们看下indexOf的代码：

public int indexOf(Object o) {int index = 0;if (o == null) {for (Node x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}return -1;}

代码从头节点顺着链接往后找，如果要找的是null,则找第一个item为null的节点，否则使用equals方法进行比较。

我们再来看删除元素，代码为：

public E remove(int index) { checkElementIndex(index); return unlink(node(index));}

通过node方法找到节点后，调用了unlink方法，代码为：

E unlink(Node x) { final E element = x.item; final Node next = x.next; final Node prev = x.prev; if(prev == null) { first = next; } else { prev.next = next; x.prev = null; } if(next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element;}

删除x节点，基本思路就是让x的前驱和后继直接链接起来，next是x的后继，prev是x的前驱，具体分为两步：
1)让x的前驱的后继指向x的后继。如果x没有前驱，说明删除的是头节点，则修改头节点指向x的后继。
2)让x的后继的前驱指向x的前驱。如果x没有后继，说明删除的是尾节点，则修改尾节点指向x的前驱。

性能特点

用法上，LinkedList是一个List,但也实现了Deque接口，可以作为队列、栈和双端队列使用。实现原理上，LinkedList内部是一个双向链表，并维护了长度、头节点和尾节点，这决定了它有如下特点。
1)按需分配空间，不需要预先分配很多空间。
2)不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率为O(N/2)。
3)不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率O(N）。

4)在两端添加、删除元素的效率很高，为O(1)。
5)在中间插入、删除元素，要先定位，效率比较低，为O(N),但修改本身的效率很高，效率为
0(1)。