LinkedList概述
LinkedList和ArrayList一样都是实现了List接口，只是ArrayList是可变数组的实现，LinkedList是链表实现。基于链表实现方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问ArrayList更有优势。
LinkedList除了实现List接口以外，还实现了Deque接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。
Linkedlist同样也是线程不安全的，想要让线程变的安全，可以使用如下方式：
List list = Collections.synchronized(new LinkedList(...))
本文源码若无特殊说明，均为JDK1.8
LinkedList源码解析
LinkedList定义
从下面这段代码可以看出LinkedList继承AbstractSequentialList，实现了List、Deque、Cloneable、Serializable。其中
AbstractSequentialList提供了List接口的主要实现，Deque是一个线性Collection，支持在两端插入和移动元素，也就是双端队列的操作。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
内部结构
LinkedList内部是一个双端链表的结构，结构如下图：
从上图可以看出，LinkedList内部是一个双端链表结构，有两个变量，first指向链表头部，last指向链表尾部。
//链表中数据
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类是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;
}
}
构造方法
LinkedList提供了2个构造方法：LinkedList()和LinkedList(Collection<? extends E> c)
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
//添加集合中所有元素
addAll(c);
}
addAll(Collection<? extends E> c)方法
当使用第二个构造方法时，会调用addAll()方法将集合中的元素添加到链表中。
//将集合插入到链表尾部，即开始索引位置为size
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
//将集合从指定位置开始插入
public boolean addAll(int index, Collection<? extends E> c) {
//检查index范围
checkPositionIndex(index);
//得到集合的数据
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//得到插入位置的前驱节点和后继节点
Node<E> pred, succ;
//如果插入位置为尾部，前驱节点为last，后继节点为null
if (index == size) {
succ = null;
pred = last;
} else { //否则，调用node()方法得到后继节点，再得到前驱节点
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;
}
//如果插入位置在尾部，重置last节点
if (succ == null) {
last = pred;
} else {//否则，将插入的链表与先前链表连接起来
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
从上面的代码可以看到，addAll方法主要分为4步：
- 检查index索引范围
- 得到集合数据
- 得到插入位置的前驱和后继节点
- 遍历数据，将数据插入到指定位置
List接口增加方法
add(E e)
add(E e)方法用于将元素添加至链表尾部，方法如下：
/**
* Appends the specified element to the end of this list.
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
//保存原来链表尾部节点，last 是全局变量，用来表示队尾元素
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;
//节点数+1
size++;
modCount++;
}
linkLast方法中就是一个链表尾部添加一个双端节点的操作，但是需要注意对链表为空时头节点的处理。
add(int index, E element)
add(int index, E element)用于在指定位置添加元素
/**
* 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).
*/
public void add(int index, E element) {
checkPositionIndex(index);
//添加在链表尾部
if (index == size)
linkLast(element);
else//添加在链表其他位置
linkBefore(element, node(index));
}
主要看linkBefore()方法，其中有个node(index) ,其实现如下：
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//// 如果 index 在前半段，从前往后遍历获取node
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//如果 index 在后半段，从后往前遍历获取node
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
得到 Node 后，就会去调用 linkBefore(element, node) 方法
/**
* Inserts element e before non-null Node succ.
*/
//将元素节点插入到 succ 之前的位置
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//保存 index 节点的前节点
final Node<E> pred = succ.prev;
//初始化节点，并指明前驱和后继节点
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
//// 判断尾节点是否为空，为空表示当前链表还没有节点
if (pred == null)
first = newNode;
else//succ节点前驱的后继引用指向新节点
pred.next = newNode;
size++;
modCount++;
}
从以上linkBefore方法来看，基本流程如下：
- 创建新节点newNode，将newNode的前驱指针指向pred和后继指针指向succ
- 将succ的前驱指针指向新节点newNode
- 根据pred是否为null，进行不同操作
- 如果pred为null，说明该节点插入在头节点之前，要重置first头节点
- 如果pred不为null，那么直接将pred的后继指针指向newNode即可
linkBefore()方法在第二个参数节点之前插入一个新节点。示意图如下：
Deque接口增加方法
addFirst(E e)方法
addFirst()方法用于将元素添加到链表头部，其实现如下:
/**
* Inserts the specified element at the beginning of this list.
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
//新建节点，以头节点为后继节点
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
//如果链表为空，last节点也指向该节点
if (f == null)
last = newNode;
else//否则，将头节点的前驱指针指向新节点
f.prev = newNode;
size++;
modCount++;
}
从上面的代码看到，实现就是在头节点插入一个节点使新节点成为新节点，但是和linkLast一样需要注意当链表为空时，对last节点的设置。
addLast(E e)方法
addLast()方法用于将元素添加到链表尾部，与add()方法一样。所以实现也一样，如下：
/**
* Appends the specified element to the end of this list.
*/
public void addLast(E e) {
linkLast(e);
}
/**
* Links e as last element.
*/
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++;
}
offer(E e)方法
offer(E e)方法用于将数据添加到链表尾部，其内部调用了add(E e)方法，如下：
/**
* Adds the specified element as the tail (last element) of this list.
*/
public boolean offer(E e) {
return add(e);
}
offerFirst(E e)方法
offerFirst(E e)将数据插入链表头部，与addFirst的区别在于该方法可以返回特定的返回值，而addFirst的返回值为void
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
offerLast(E e)方法
offerLast()与addLast()的区别和offerFirst()和addFirst()的区别一样
/**
* Inserts the specified element at the end of this list.
*/
public boolean offerLast(E e) {
addLast(e);
return true;
}
查找方法
get(int index)方法
get(int index)方法根据指定索引返回数据，在内部调用了node(index),前面已经分析过了
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//检查边界
checkElementIndex(index);
return node(index).item;
}
getFirst()、element()、peek()、peekFirst()方法，获得位置为0的头节点数据
getFirst()、element()、peek()、peekFirst()方法获取位置为0的头节点数据，区别在于对链表为空时的处理，是抛出异常还是返回null。
其中getFirst()和element()方法将会在链表为空时，抛出异常
/**
* 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;
}
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
public E element() {
return getFirst();
}
其中peek()和peekFirst(),当链表为空的时候方法返回null，其实现如下：
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Retrieves, but does not remove, the first element of this list,
* or returns {@code null} if this list is empty.
*
* @return the first element of this list, or {@code null}
* if this list is empty
* @since 1.6
*/
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
getLast()和peekLast()方法，获得位置为size-1的尾节点数据
getLast()和peekLast()为获得为节点数据的方法：
/**
* 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;
}
/**
* Retrieves, but does not remove, the last element of this list,
* or returns {@code null} if this list is empty.
*
* @return the last element of this list, or {@code null}
* if this list is empty
* @since 1.6
*/
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
可以看到，getLast()方法在链表为空时，会抛出NoSuchElementException，而peekLast()则不会，只是会返回null。
idnexOf()方法
idnexOf()方法实现的在于一个从前往后遍历,其方法实现如下：
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
//返回第一个匹配的索引，不包含次元素则返回-1
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
lastIndexOf(Object o)方法
lastIndexOf()方法返回最后一个匹配的索引，实现为从后往前遍历,其方法实现如下：
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @return the index of the last occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
//返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
删除方法
删除操作分为按照位置删除和按照对象删除，其中按照位置删除的方法又有区别，有的只是返回是否删除成功的标志，有的还需要返回被删除的元素
remove(Object o)方法，删除指定对象
当删除指定对象时，只需调用remove(Object o)即可，不过该方法一次只会删除一个匹配的对象，如果删除了匹配对象，返回true，否则false。
/**
* 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;
}
从以上代码，可以看出主要是由unlink()方法来实现删除操作，代码如下：
/**
* 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 {//设置该节点的前节点的 next 为该节点的 next
prev.next = next;
x.prev = null;
}
//删除后继节点,那么设置尾节点为上一个节点
if (next == null) {
last = prev;
} else {//设置该节点的下一个节点的 prev 为该节点的 prev
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
remove(int index)方法，按照位置删除对象
remove(int index)方法用于删除任意位置的元素，如果删除成功将返回true，否则返回false,实现如下：
/**
* 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));
}
remove()、removeFirst()、pop()、poll()、pollFirst()删除头结点的对象
删除头节点的对象的方法有很多，包括remove()、removeFirst()、pop()、poll()、pollFirst()，其中前三个方法在链表为空时将抛出NoSuchElementException，后两个方法在链表为空时将返回null。
remove()、pop()、removeFirst()的实现如下：
public E remove() {
return removeFirst();
}
public E pop() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
poll()和pollFirst()的实现：
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
removeLast()和pollLast()删除尾节点的对象
删除尾节点的对象的方法有removeLast()和pollLast()
removeLast的实现如下：
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
pollLast()的实现如下：
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
set方法
取代在指定位置上的元素，并返回旧值，其实现如下：
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
// 设置 x 节点的值为新值，然后返回旧值
x.item = element;
return oldVal;
}
clear方法
删除该链表中的全部元素，其实现如下：
/**
* 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是基于双端链表的List，其内部的实现源于对链表的操作，所以适用于频繁增加、删除的情况；该类不是线程安全的；另外，由于LinkedList实现了Queue接口，所以LinkedList不止有队列的接口，还有栈的接口，可以使用LinkedList作为队列和栈的实现。