前言

本篇作为吃透java集合系列第四篇，主要来了解一下LinkedList，通过本篇你将了解到如下：

1、LinkedList的List特性

2、LinkedList的Queue特性

一：LinkedList

LinkedList类是List接口的实现类，它是一个集合，可以根据索引来随机的访问集合中的元素，还实现了Deque接口，它还是一个队列，可以当成双端队列来使用。

虽然LinkedList是一个List集合，但是它的实现方式和ArrayList是完全不同的，ArrayList的底层是通过一个动态的Object[]数组实现的，而LinkedList的底层是通过双向链表来实现的，因此它的随机访问速度是比较差的，但是它的删除，插入操作很快。

• LinkedList是基于双向循环链表实现的，除了可以当作链表操作外，它还可以当作栈、队列和双端队列来使用。
• LinkedList同样是非线程安全的，只在单线程下适合使用。
• LinkedList允许null插入。

• 实现List接口，具有List集合的特性。
• 实现Deque接口，具有队列的特性。
• 实现Cloneable接口，可以通过clone来实现浅拷贝
• 实现Serializable接口，可以序列化，通过writeObject和readObject自定义序列化。

LinkedList的底层结构如下图所示

F表示头结点引用，L表示尾结点引用，链表的每个结点都有三个元素，分别是前继结点引用(P)，结点元素的值(E)，后继结点的引用(N)。结点由内部类Node表示，我们看看它的内部结构。

Node这个内部类其实很简单，只有三个成员变量和一个构造器，item表示结点的值，next为下一个结点的引用，prev为上一个结点的引用，通过构造器传入这三个值。接下来再看看LinkedList的成员变量和构造器。

LinkedList持有头结点的引用和尾结点的引用，它有两个构造器，一个是无参构造器，一个是传入外部集合的构造器。与ArrayList不同的是LinkedList没有指定初始大小的构造器。

二：LinkedList的List特性

	//增
 /**
	* 将指定的元素追加到此列表的末尾
	*/
	public boolean add(E e) {
 linkLast(e);
 return true;
 }
 /**
	* 在此列表中的指定位置插入指定的元素。
	*/
	public void add(int index, E element) {
 checkPositionIndex(index);
 if (index == size)
 linkLast(element);
 else
 linkBefore(element, node(index));
 }
 /**
	* 将指定集合中的所有元素追加到此列表的末尾。
	*/
	public boolean addAll(Collection<? extends E> c) {
 return addAll(size, c);
 }
 /**
	* 将指定集合中的所有元素插入到此列表中，从指定的位置开始。
	*/
	public boolean addAll(int index, Collection<? extends E> c) {
 checkPositionIndex(index);
 Object[] a = c.toArray();
 int numNew = a.length;
 if (numNew == 0)
 return false;
 Node<E> pred, succ;
 if (index == size) {
 succ = null;
 pred = last;
 } else {
 succ = node(index);
 pred = succ.prev;
 }
 for (Object o : a) {
 @SuppressWarnings("unchecked") E e = (E) o;
 Node<E> newNode = new Node<>(pred, e, null);
 if (pred == null)
 first = newNode;
 else
 pred.next = newNode;
 pred = newNode;
 }
 if (succ == null) {
 last = pred;
 } else {
 pred.next = succ;
 succ.prev = pred;
 }
 size += numNew;
 modCount++;
 return true;
 }
 /**
	* 头插入
	*/
	public void addFirst(E e) {
 linkFirst(e);
 }
 /**
	* 尾插入
	*/
	public void addLast(E e) {
 linkLast(e);
 }
	//删
 /**
	* 从列表中删除指定元素的第一个出现（如果存在）。
	*/
	public boolean remove(Object o) {
 if (o == null) {
 for (Node<E> x = first; x != null; x = x.next) {
 if (x.item == null) {
 unlink(x);
 return true;
 }
 }
 } else {
 for (Node<E> x = first; x != null; x = x.next) {
 if (o.equals(x.item)) {
 unlink(x);
 return true;
 }
 }
 }
 return false;
 }
 /**
	* 删除该列表中指定位置的元素。
	*/
	public E remove(int index) {
 checkElementIndex(index);
 return unlink(node(index));
 }
 /**
	* 从此列表中删除并返回第一个元素。
	*/
	public E removeFirst() {
 final Node<E> f = first;
 if (f == null)
 throw new NoSuchElementException();
 return unlinkFirst(f);
 }
 /**
	* 从此列表中删除并返回最后一个元素。
	*/
	public E removeLast() {
 final Node<E> l = last;
 if (l == null)
 throw new NoSuchElementException();
 return unlinkLast(l);
 }
	//改
 /**
	* 用指定的元素替换此列表中指定位置的元素。
	*/
	public E set(int index, E element) {
 checkElementIndex(index);
 Node<E> x = node(index);
 E oldVal = x.item;
 x.item = element;
 return oldVal;
 }
	//查
 /**
	* 返回此列表中指定位置的元素。
	*/
	public E get(int index) {
 checkElementIndex(index);
 return node(index).item;
 }

LinkedList的添加元素的方法主要是调用linkLast和linkBefore两个方法，linkLast方法是在链表后面链接一个元素，linkBefore方法是在链表中间插入一个元素。LinkedList的删除方法通过调用unlink方法将某个元素从链表中移除。下面我们看看链表的插入和删除操作的核心代码。

	/**
 * 返回指定位置的节点
 */
 Node<E> node(int index) {
 // assert isElementIndex(index);
 if (index < (size >> 1)) {
 Node<E> x = first;
 for (int i = 0; i < index; i++)
 x = x.next;
 return x;
 } else {
 Node<E> x = last;
 for (int i = size - 1; i > index; i--)
 x = x.prev;
 return x;
 }
 }
 /**
 * 连接到第一个元素
 */
 private void linkFirst(E e) {
 final Node<E> f = first;
 final Node<E> newNode = new Node<>(null, e, f);
 first = newNode;
 if (f == null)
 last = newNode;
 else
 f.prev = newNode;
 size++;
 modCount++;
 }
 /**
 * 链接到最后一个元素
 */
 void linkLast(E e) {
 final Node<E> l = last;
 final Node<E> newNode = new Node<>(l, e, null);
 last = newNode;
 if (l == null)
 first = newNode;
 else
 l.next = newNode;
 size++;
 modCount++;
 }
 /**
 * 在succ前插入元素e
 */
 void linkBefore(E e, Node<E> succ) {
 // assert succ != null;
 final Node<E> pred = succ.prev;
 final Node<E> newNode = new Node<>(pred, e, succ);
 succ.prev = newNode;
 if (pred == null)
 first = newNode;
 else
 pred.next = newNode;
 size++;
 modCount++;
 }
 /**
 * 去掉头结点
 */
 private E unlinkFirst(Node<E> f) {
 // assert f == first && f != null;
 final E element = f.item;
 final Node<E> next = f.next;
 f.item = null;
 f.next = null; // help GC
 first = next;
 if (next == null)
 last = null;
 else
 next.prev = null;
 size--;
 modCount++;
 return element;
 }
 /**
 * 去掉尾结点
 */
 private E unlinkLast(Node<E> l) {
 // assert l == last && l != null;
 final E element = l.item;
 final Node<E> prev = l.prev;
 l.item = null;
 l.prev = null; // help GC
 last = prev;
 if (prev == null)
 first = null;
 else
 prev.next = null;
 size--;
 modCount++;
 return element;
 }
 /**
 * 去掉指定的节点
 */
 E unlink(Node<E> x) {
 // assert x != null;
 final E element = x.item;
 final Node<E> next = x.next;
 final Node<E> 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;
 }

三：LinkedList的Queue特性

通过对双向链表的操作还可以实现单项队列，双向队列和栈的功能。

单向队列操作：

双向队列操作：

栈操作：

不管是单向队列还是双向队列还是栈，其实都是对链表的头结点和尾结点进行操作，它们的实现都是基于addFirst()，addLast()，removeFirst()，removeLast()这四个方法。

• LinkedList是基于双向链表实现的，不论是增删改查方法还是队列和栈的实现，都可通过操作结点实现
• LinkedList无需提前指定容量，因为基于链表操作，集合的容量随着元素的加入自动增加
• LinkedList删除元素后集合占用的内存自动缩小，无需像ArrayList一样调用trimToSize()方法
• LinkedList的所有方法没有进行同步，因此它也不是线程安全的，应该避免在多线程环境下使用