前言
本篇作为吃透java集合系列第四篇，主要来了解一下LinkedList，通过本篇你将了解到如下：
1、LinkedList的List特性
2、LinkedList的Queue特性
一：LinkedList
LinkedList类是List接口的实现类，它是一个集合，可以根据索引来随机的访问集合中的元素，还实现了Deque接口，它还是一个队列，可以当成双端队列来使用。
虽然LinkedList是一个List集合，但是它的实现方式和ArrayList是完全不同的，ArrayList的底层是通过一个动态的Object[]数组实现的，而LinkedList的底层是通过双向链表来实现的，因此它的随机访问速度是比较差的，但是它的删除，插入操作很快。
- LinkedList是基于双向循环链表实现的，除了可以当作链表操作外，它还可以当作栈、队列和双端队列来使用。
- LinkedList同样是非线程安全的，只在单线程下适合使用。
- LinkedList允许null插入。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- 实现List接口，具有List集合的特性。
- 实现Deque接口，具有队列的特性。
- 实现Cloneable接口，可以通过clone来实现浅拷贝
- 实现Serializable接口，可以序列化，通过writeObject和readObject自定义序列化。
LinkedList的底层结构如下图所示
F表示头结点引用，L表示尾结点引用，链表的每个结点都有三个元素，分别是前继结点引用§，结点元素的值(E)，后继结点的引用(N)。结点由内部类Node表示，我们看看它的内部结构。
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这个内部类其实很简单，只有三个成员变量和一个构造器，item表示结点的值，next为下一个结点的引用，prev为上一个结点的引用，通过构造器传入这三个值。接下来再看看LinkedList的成员变量和构造器。
/**
* 集合元素个数
*/
transient int size = 0;
/**
* 头结点
*/
transient Node<E> first;
/**
* 尾节点
*/
transient Node<E> last;
/**
* 无参构造器
*/
public LinkedList() {
}
/**
* 传入外部集合的构造器
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
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特性
通过对双向链表的操作还可以实现单项队列，双向队列和栈的功能。
单向队列操作：
//获取头结点
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//获取头结点
public E element() {
return getFirst();
}
//弹出头结点
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//移除头结点
public E remove() {
return removeFirst();
}
//在队列尾部添加结点
public boolean offer(E e) {
return add(e);
}
双向队列操作：
//在头部添加
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//在尾部添加
public boolean offerLast(E e) {
addLast(e);
return true;
}
//获取头结点
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//获取尾结点
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
栈操作：
//入栈
public void push(E e) {
addFirst(e);
}
//出栈
public E pop() {
return removeFirst();
}
不管是单向队列还是双向队列还是栈，其实都是对链表的头结点和尾结点进行操作，它们的实现都是基于addFirst()，addLast()，removeFirst()，removeLast()这四个方法。
- LinkedList是基于双向链表实现的，不论是增删改查方法还是队列和栈的实现，都可通过操作结点实现
- LinkedList无需提前指定容量，因为基于链表操作，集合的容量随着元素的加入自动增加
- LinkedList删除元素后集合占用的内存自动缩小，无需像ArrayList一样调用trimToSize()方法
- LinkedList的所有方法没有进行同步，因此它也不是线程安全的，应该避免在多线程环境下使用
![Java集合-LinkedList工作原理及实现概述链表结构定义add方法set和get方法[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)