简介：
LinkedList 集合底层是一个双向链表结构，具有增删快，查询慢的特点,内部包含大量操作首尾元素的方法。适用于集合元素先入先出和先入后出的场景，在队列源码中被频繁使用。
链表结构的节点新增、删除都非常简单，仅仅把前后节点的指向修改下就好了，所以 LinkedList 新增和删除速度很快。
LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。
LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列(Queue)，同时又可以看作一个栈(Stack)。
1、当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类
2、Java里根本没有一个叫做Queue的类(它是个接口名字)。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList(当作栈或队列使用时)有着更好的性能。
LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized)，如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。
模拟LinkedList源码：
点击查看代码
public class MyLinkedList {
//链中一定有一个首节点：
Node first;
//链中一定有一个尾节点：
Node last;
//计数器：
int count = 0;
//提供一个构造器：
public MyLinkedList(){
}
//添加元素方法：
public void add(Object o){
if(first == null){//证明你添加的元素是第一个节点：
//将添加的元素封装为一个Node对象：
Node n = new Node();
n.setPre(null);
n.setObj(o);
n.setNext(null);
//当前链中第一个节点变为n
first = n;
//当前链中最后一个节点变为n
last = n;
}else{//证明已经不是链中第一个节点了
//将添加的元素封装为一个Node对象：
Node n = new Node();
n.setPre(last);//n的上一个节点一定是当前链中的最后一个节点last
n.setObj(o);
n.setNext(null);
//当前链中的最后一个节点的下一个元素 要指向n
last.setNext(n);
//将最后一个节点变为n
last = n;
}
//链中元素数量加1
count++;
}
//得到集合中元素的数量：
public int getSize(){
return count;
}
//通过下标得到元素：
public Object get(int index){
//获取链表的头元素：
Node n = first;
//一路next得到想要的元素
for(int i=0;i<index;i++){
n = n.getNext();
}
return n.getObj();
}
}
class Test{
//这是main方法，程序的入口
public static void main(String[] args) {
//创建一个MyLinkedList集合对象：
MyLinkedList ml = new MyLinkedList();
ml.add("aa");
ml.add("bb");
ml.add("cc");
System.out.println(ml.getSize());
System.out.println(ml.get(0));
}
}
LinkedList整体架构
LinkedList 底层数据结构是一个双向链表，整体结构如下图所示：
上图代表了一个双向链表结构，可以通过前面的节点找到后面的节点,也可以通过后面的节点找到前面的节点
相关概念:
● Node: 代表链中的每个节，Node 的 prev 属性，代表前一个节点的地址，Node 的next 属性，代表后一个节点的地址；
● first :代表双向链表的头节点，它的前一个节点是 null。
● last: 代表双向链表的尾节点，它的后一个节点是 null；
● 如果链表中没有任何数据时，头节点first 和 尾节点last 是同一个节点，前后指向都是 null；
● 因为LinkedList集合是个双向链表，所以机器只要有足够强大的内存，对于LinkedList集合而言是没有大小限制的。
链表中的元素被称为Node， 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;
}
}
LinkedList实现
底层数据结构
LinkedList底层通过双向链表实现，本节将着重讲解插入和删除元素时双向链表的维护过程，也即是之间跟List接口相关的函数，而将Queue和Stack以及Deque相关的知识放在下一节讲。双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。注意当链表为空的时候first和last都指向null。
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
其中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;
}
}
构造函数
/**
* 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<? extends E> c) {
this();
addAll(c);
}
getFirst(), getLast()
获取第一个元素， 和获取最后一个元素:
/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* Returns the last element in this list.
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
removeFirst(), removeLast(), remove(e), remove(index)
节点删除的方式和添加类似，我们可以选择从头部删除，也可以选择从尾部删除，删除操作会把节点的值，前后指向节点都置为 null，帮助 GC 进行回收。
从头部删除
//从头删除节点 f 是链表头节点
private E unlinkFirst(Node<E> f) {
// 拿出头节点的值，作为方法的返回值
final E element = f.item;
// 拿出头节点的下一个节点
final Node<E> next = f.next;
//帮助 GC 回收头节点
f.item = null;
f.next = null;
// 头节点的下一个节点成为头节点
first = next;
//如果 next 为空，表明链表为空
if (next == null)
last = null;
//链表不为空，头节点的前一个节点指向 null
else
next.prev = null;
//修改链表大小和版本
size--;
modCount++;
return
element;
}
从尾部删除节点的代码也是类似的，这里就不再详细解释了。
从源码中我们可以了解到，链表结构的节点新增、删除都非常简单，仅仅把前后节点的指向修改下就好了，所以 LinkedList 新增和删除速度很快。
remove()方法也有两个版本，一个是删除跟指定元素相等的第一个元素remove(Object o)，另一个是删除指定下标处的元素remove(int index)。
删除元素 - 指的是删除第一次出现的这个元素, 如果没有这个元素，则返回false；判断的依据是equals方法， 如果equals，则直接unlink这个node；由于LinkedList可存放null元素，故也可以删除第一次出现null的元素；
点击查看代码
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
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;
}
/**
* Unlinks non-null node x.
*/
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; // GC
size--;
modCount++;
return element;
}
点击查看代码
/**
* Removes the element at the specified position in this list. Shifts any
* subsequent elements to the left (subtracts one from their indices).
* Returns the element that was removed from the list.
*
* @param index the index of the element to be removed
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
删除head元素:
点击查看代码
/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
*/
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;
}
点击查看代码
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
/**
* Unlinks non-null last node l.
*/
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;
}
添加节点
add()方法有两个版本，一个是add(E e)，该方法在LinkedList的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是add(int index, E element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。
如果想在LinkedList集合中添加节点，我们把新加入的节点添加到链表头部，也可以把新加入的节点添加添加到链表尾部，add 方法默认是从尾部开始添加，addFirst 方法是从头部开始添加，下面分别来看下两种不同的添加方式：
从尾部添加（add）
// 从尾部开始添加节点
void linkLast(E e) {
// 把尾节点数据暂存
final Node<E> l = last;
// 新建新的节点，初始化入参含义：
// l 是新节点的前一个节点，当前值是尾节点值
// e 表示当前新增节点，当前新增节点后一个节点是 null
final Node<E> newNode = new Node<>(l, e, null);
// 新建节点添加到尾部
last = newNode;
//如果链表为空（l 是尾节点，尾节点为空，链表即空），
//头部和尾部是同一个节点，都是新建的节点
if (l == null)
first = newNode;
//否则把前尾节点的下一个节点，指向当前尾节点。
else
l.next = newNode;
size++;
//集合元素数量增加1
modCount++;
//实际修改次数增加1}
从源码上来看，尾部添加节点比较简单.
从头部添加（addFirst）
// 从头部添加
private void linkFirst(E e) {
// 头节点赋值给临时变量
final Node<E> f = first;
// 新建节点，前一个节点指向null，e 是新建节点，f 是新建节点的下一个节点，目前值是头节点的值
final Node<E> newNode = new Node<>(null, e, f);
// 新建节点成为头节点
first = newNode;
// 头节点为空，就是链表为空，头尾节点是一个节点
if (f == null)
last = newNode;
//上一个头节点的前一个节点指向当前节点
else
f.prev = newNode;
size++;
modCount++;
}
头部添加节点和尾部添加节点非常类似，只是前者是移动头节点的 prev 指向，后者是移动尾节点的 next 指向。
add(int index, E element), 当index==size时，等同于add(E e); 如果不是，则分两步: 1.先根据index找到要插入的位置,即node(index)方法；2.修改引用，完成插入操作。
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
上面代码中的node(int index)函数有一点小小的trick，因为链表双向的，可以从开始往后找，也可以从结尾往前找，具体朝那个方向找取决于条件index < (size >> 1)，也即是index是靠近前端还是后端。从这里也可以看出，linkedList通过index检索元素的效率没有arrayList高。
/**
* Returns the (non-null) Node at the specified element index.
*/
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;
}
}
addAll()
addAll(index, c) 实现方式并不是直接调用add(index,e)来实现，主要是因为效率的问题，另一个是fail-fast中modCount只会增加1次；
点击查看代码
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the specified
* collection's iterator. The behavior of this operation is undefined if
* the specified collection is modified while the operation is in
* progress. (Note that this will occur if the specified collection is
* this list, and it's nonempty.)
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
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;
}
clear()
为了让GC更快可以回收放置的元素，需要将node之间的引用关系赋空。
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
查询节点
在链表查询某一个节点是比较慢的，因为需要挨个循环查找才行（没有索引），我们看看 LinkedList 的源码是如何寻找节点的：
// 根据链表索引位置查询节点
Node<E> node(int index) {
// 如果 index 处于队列的前半部分，从头开始找，size >> 1 是 size 除以 2 的意思。
if (index < (size >> 1)) {
Node<E> x = first;
// 直到 for 循环到 index 的前一个 node 停止
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果 index 处于队列的后半部分，从尾开始找
Node<E> x = last;
// 直到 for 循环到 index 的后一个 node 停止
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}}
从源码中我们可以发现，LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分。如果是前半部分，就从头开始寻找，反之亦然。通过这种方式，使循环的次数至少降低了一半，提高了查找的性能，这种思想值得我们借鉴。
迭代器
因为 LinkedList 要实现双向的迭代访问，所以我们使用 Iterator 接口肯定不行了，因为 Iterator 只支持从头到尾的访问。Java 新增了一个迭代接口，叫做：ListIterator，这个接口提供了向前和向后的迭代方法，如下所示：
LinkedList 实现了 ListIterator 接口，如下图所示：
// 双向迭代器
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
//上一次执行 next() 或者 previos() 方法时的节点位置
private Node<E> next;
//下一个节点
private int nextIndex;
//下一个节点的位置
//expectedModCount：期望版本号；modCount：目前最新版本号
private int expectedModCount = modCount; …………
}
我们先来看下从头到尾方向的迭代：
// 判断还有没有下一个元素
public boolean hasNext() {
return nextIndex < size;
// 下一个节点的索引小于链表的大小，就有}
// 取下一个元素
public E next() {
//检查期望版本号有无发生变化
checkForComodification();
if (!hasNext())
//再次检查
throw new NoSuchElementException();
// next 是当前节点，在上一次执行 next() 方法时被赋值的。
// 第一次执行时，是在初始化迭代器的时候，next 被赋值的
lastReturned = next;
// next 是下一个节点了，为下次迭代做准备
next = next.next;
nextIndex++;
return lastReturned.item;
}
上述源码的思路就是直接取当前节点的下一个节点，而从尾到头迭代稍微复杂一点，如下：
// 如果上次节点索引位置大于 0，就还有节点可以迭代
public boolean hasPrevious() {
return nextIndex > 0;
}
// 取前一个节点
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
// next 为空场景：1:说明是第一次迭代，取尾节点(last);2:上一次操作把尾节点删除掉了
// next 不为空场景：说明已经发生过迭代了，直接取前一个节点即可(next.prev)
lastReturned = next = (next == null) ? last : next.prev;
// 索引位置变化
nextIndex--;
return lastReturned.item;
}
这里复杂点体现在需要判断 next 不为空和为空的场景，代码注释中有详细的描述。
迭代器删除
LinkedList 在删除元素时，也推荐通过迭代器进行删除，删除过程如下：
public void remove() {
checkForComodification();
// lastReturned 是本次迭代需要删除的值，分以下空和非空两种情况：
// lastReturned 为空，说明调用者没有主动执行过 next() 或者 previos()，直接报错
// lastReturned 不为空，是在上次执行 next() 或者 previos()方法时赋的值
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
//删除当前节点 unlink(lastReturned);
// next == lastReturned 的场景分析：从尾到头递归顺序，并且是第一次迭代，并且要删除最后一个元素的情况下
// 这种情况下，previous() 方法里面设置了 lastReturned = next = last,
//所以 next 和 lastReturned会相等
if (next == lastReturned)
// 这时候 lastReturned 是尾节点，lastNext 是 null，所以 next 也是 null，这样在 previous() 执行时，发现 next 是 null，就会把尾节点赋值给 next
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
LinkedList 适用于要求有顺序、并且会按照顺序进行迭代的场景，主要是依赖于底层的链表结构，在面试中的频率还是蛮高的，相信理清楚上面的源码后，应对面试应该没有问题。