系列文章：
前言
本文開始分析LinkedList。ArrayList和LinkedList都實現(xiàn)了List接口，但內(nèi)部數(shù)據(jù)結構有所區(qū)別，LinkedList內(nèi)部是基于鏈表實現(xiàn)的，所以其插入和刪除操作效率較高，但是隨機訪問效率就相對較低。其定義如下：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
可以看到LinkedList繼承AbstractSequentialList，實現(xiàn)了List，Deque，Cloneable，java.io.Serializable四個接口。
AbstractSequenceList實現(xiàn)了大部分List接口的方法，Deque接口定義了雙端隊列的操作。
本文源碼分析基于jdk 1.8.0_121
繼承關系
LinkedList繼承關系
java.lang.Object
|___ java.util.AbstractCollection<E>
|___ java.util.AbstractList<E>
|___ java.util.AbstractSequentialList<E>
|___ java.util.LinkedList<E>
所有已實現(xiàn)的接口：
Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>
關系圖
LinkedList關系圖
LinkedList的本質(zhì)是雙向鏈表，LinkedList中first,last,size等成員比較重要，first是鏈表的頭指針，last是尾指針，size是雙向鏈表中節(jié)點的個數(shù)，鏈表的節(jié)點對應Node類數(shù)據(jù)結構如下：
private static class Node<E> {
E item; // 節(jié)點值
Node<E> next; // 指向下一個節(jié)點
Node<E> prev; // 指向上一個節(jié)點
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
AbstractSequenceList
AbstractSequentialList 繼承自 AbstractList，是 LinkedList 的父類，提供了List接口大部分實現(xiàn)。
AbstractSequentialList 實現(xiàn)了“隨機訪問”方法get(int index)、set(int index, E element)、add(int index, E element)、remove(int index)。
要實現(xiàn)一個列表，我們只需要擴展此類，并提供 listIterator 和 size 方法的實現(xiàn)即可。對于不可修改的列表，我們只需要實現(xiàn)列表迭代器的 hasNext、next、hasPrevious、previous、index 方法即可。
API
boolean add(E e)
void add(int index, E element)
boolean addAll(Collection<? extends E> c)
boolean addAll(int index, Collection<? extends E> c)
void addFirst(E e)
void addLast(E e)
void clear()
Object clone()
boolean contains(Object o)
Iterator<E> descendingIterator()
E element()
E get(int index)
E getFirst()
E getLast()
int indexOf(Object o)
int lastIndexOf(Object o)
ListIterator<E> listIterator(int index)
boolean offer(E e)
boolean offerFirst(E e)
boolean offerLast(E e)
E peek()
E peekFirst()
E peekLast()
E poll()
E pollFirst()
E pollLast()
E pop()
void push(E e)
E remove()
E remove(int index)
boolean remove(Object o)
E removeFirst()
boolean removeFirstOccurrence(Object o)
E removeLast()
boolean removeLastOccurrence(Object o)
E set(int index, E element)
int size()
<T> T[] toArray(T[] a)
Object[] toArray()
源碼分析
首先我們知道LinkedList是一個雙向鏈表，但是同時也實現(xiàn)了List接口，因此也可以根據(jù)索引值（index）來獲取，更改，刪除節(jié)點等。那么是如何把鏈表和索引值聯(lián)系的呢？LinkedList是通過一個計數(shù)索引值來實現(xiàn)的，當我們調(diào)用get(int index)時，我們會把index和鏈表長度的1/2比較，如果index值小·，則從鏈表頭向后遍歷；反之；如果index值大，則從鏈表尾遍歷。其余方法原理類似。
成員對象
transient int size = 0; // 節(jié)點個數(shù)
transient Node<E> first; // 表頭
transient Node<E> last; // 表尾
構造函數(shù)
// 默認構造函數(shù)
public LinkedList() {
}
// 創(chuàng)建包含集合c的LinkedList
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
增加元素
// 添加元素，添加到last節(jié)點后
public boolean add(E e) {
linkLast(e);
return true;
}
// 新建一個節(jié)點newNode，讓其prev屬性為當前l(fā)ast節(jié)點，last屬性為null
// 如果當前l(fā)ast節(jié)點為null，則令first節(jié)點為newNode
// 如果當前l(fā)ast節(jié)點不為null，則讓其next屬性為newNode
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++;
}
// 先檢查index，如果index值正好為size，那么添加到last節(jié)點后
// 否則，添加到index位置處，node(index)獲取當前index處節(jié)點
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
// 先獲取當前index處節(jié)點的前一個節(jié)點pred
// 再新建節(jié)點newNode，如果pred節(jié)點為null，則令first為newNode
// 否則pred的next節(jié)點為newNode，同時改變size和修改計數(shù)值
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++;
}
// 添加集合c到LinkedList中
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
// 在index處添加所有集合c中所有節(jié)點
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;
}
// 添加元素到頭節(jié)點位置
public void addFirst(E e) {
linkFirst(e);
}
// 把元素e設置為第一個節(jié)點
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++;
}
// 添加元素到尾節(jié)點位置
public void addLast(E e) {
linkLast(e);
}
設置元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
獲取元素
// 返回index處節(jié)點值
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 返回頭節(jié)點值
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
// 返回尾節(jié)點值
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
刪除元素
// 從LinkedList中刪除對象o
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;
}
// 刪除index處節(jié)點
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
// 刪除第一個元素
public E remove() {
return removeFirst();
}
// 刪除第一個元素
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);
}
toArray
// 返回LinkedList的Object[]數(shù)組
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
// 返回T類型的數(shù)組
public <T> T[] toArray(T[] a) {
// 若數(shù)組a的大小小于LinkedList的元素個數(shù)
// 則新建一個T[]數(shù)組，T[]的大小為LinkedList大小，并將該T[]賦值給a。
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
克隆函數(shù)
// 克隆函數(shù)
public Object clone() {
LinkedList<E> clone = superClone();
// 重新初始化
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// 添加所有節(jié)點數(shù)值
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
// 調(diào)用父clone函數(shù)
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
其余函數(shù)
// 將e添加到鏈表末尾
public boolean offer(E e) {
return add(e);
}
// 將e添加到鏈表頭節(jié)點處
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// 將e添加到鏈表末尾
public boolean offerLast(E e) {
addLast(e);
return true;
}
// 返回頭節(jié)點，頭節(jié)點為null則返回null
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 返回尾節(jié)點，尾節(jié)點為null則返回null
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
// 返回頭節(jié)點并刪除
// 頭節(jié)點為null則返回null
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 返回尾節(jié)點并刪除
// 尾節(jié)點為null則返回null
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
// 將e插入到雙向鏈表頭節(jié)點
public void push(E e) {
addFirst(e);
}
// 刪除并返回第一個節(jié)點
public E pop() {
return removeFirst();
}
小結
-
LinkedList是通過雙向鏈表實現(xiàn)的，內(nèi)部有節(jié)點的數(shù)據(jù)結構 -
LinkedList實現(xiàn)了Deque，而Deque接口定義了在隊列兩端訪問元素的方法，有增加，刪除，獲取第一個元素等方法。 -
LinkedList可以作為FIFO先進先出的隊列，下列方法等效
| 隊列方法 | 等效方法 |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
-
LinkedList可以作為LIFO后進先出的棧，下列方法等效
| 棧方法 | 等效方法 |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
遍歷方式
迭代器遍歷
Iterator iter = list.iterator();
while(iter.hasNext()) {
iter.next();
}
隨機訪問
for (int i=0; i<list.size(); i++) {
list.get(i);
}
foreach循環(huán)
for (Integer integ:list) {
;
}
pollFirst
while(list.pollFirst() != null)
;
pollLast
while(list.pollLast() != null)
;
removeFirst
try {
while(list.removeFirst() != null)
;
} catch (NoSuchElementException e) {
...
}
##
removeLast
try {
while(list.removeLast() != null)
;
} catch (NoSuchElementException e) {
...
}
通過隨機訪問的方式遍歷LinkedList時，效率很低，因此需要盡量避免這種方式。
