哈嘍，大家好，今天我們來簡單聊聊LinkedList
LinkedList是由雙鏈表組成的集合，它不是線程安全的，如果有在多線程中添加或刪除一個或多個元素，需要自己做同步處理，也可以調(diào)用List list = Collections.synchronizedList(new LinkedList(...));來獲取一個線程同步的集合。
下面我們開始簡單分析一下源碼，首先來看看LinkedList這個類實(shí)現(xiàn)了哪些關(guān)鍵的接口。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
我們可以從源碼中看出LinkedList實(shí)現(xiàn)了List接口來方便集合操作，同時也實(shí)現(xiàn)了Deque接口，這樣就有了許多操作鏈表的方法。
Node
Node類是LinkedList的一個內(nèi)部類，這個類是鏈表中存放元素用的?？聪略创a
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;
}
}
有三個參數(shù)，item是當(dāng)前元素的值，next指的是下一個元素，prev指的是上一個元素。
重要參數(shù)
transient Node<E> first;
transient Node<E> last;
在LinkedList中有兩個比較重要的參數(shù)，一個是first，指的是鏈表中第一個元素。而last指的就是鏈表中最后一個元素。
LinkedList()
public LinkedList() {
}
這個LinkedList的一個空構(gòu)造函數(shù)，沒有做任何其他操作。
LinkedList(Collection<? extends E> c)
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
這是一個帶參數(shù)的構(gòu)造函數(shù)，將傳入進(jìn)來的集合全部添加到了LinkedList中，addAll這個方法我們在后面進(jìn)行講解。
getFirst()
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
這個方法是獲取第一個元素的值，這里是直接將first賦值給f，因?yàn)閒irst在LinkedList中就是指的第一個元素。如果f為null的話就會報錯。最后會返回f的值。
getLast()
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
這個方法是獲取最后一個元素的值，這個方法和getFirst()方法類似，直接將last賦值給l，最后返回l的值。
removeFirst()
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
private E unlinkFirst(Node<E> f) {
//將f的值賦值給element。
final E element = f.item;
//將f的下一個元素賦值給next。
final Node<E> next = f.next;
//將f的值和f中的next都設(shè)置為null，方便GC
f.item = null;
f.next = null; // help GC
//將first設(shè)置為f的next
first = next;
//如果next為null，證明鏈表中只有一個元素，那么將最后一個元素也設(shè)置為null。
if (next == null)
last = null;
else
//如果不為null，那么將next的prev設(shè)置為null，原本指向的是f。
next.prev = null;
size--;
modCount++;
//最后返回f的值。
return element;
}
這個方法是移除第一個元素。還是先將first賦值給f，然后調(diào)用unlinkFirst方法并將f傳入。unlinkFirst的相關(guān)解釋寫在了代碼中。
removeLast()
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(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;
}
這個方法和removeFirst方法邏輯差不多，是將最后一個元素置為null，然后將倒數(shù)第二個元素賦值給last。
addFirst(E e)
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
//將first賦值給f。
final Node<E> f = first;
//根據(jù)傳入的值e，new一個新的Node出來，并將f傳入，設(shè)置為新Node的下一個元素。
final Node<E> newNode = new Node<>(null, e, f);
//將第一個元素設(shè)置為新的Node。
first = newNode;
//如果f為null表示原本鏈表中沒有元素，這時候添加了一個元
//素后第一個，最后一個元素都是newNode，所以要設(shè)置last為newNode。
if (f == null)
last = newNode;
else
//否則將原本第一個元素的prev設(shè)置為newNode。
f.prev = newNode;
size++;
modCount++;
}
在鏈表的頭部添加一個元素，關(guān)鍵解釋放在了代碼中。
addLast(E e)
public void addLast(E e) {
linkLast(e);
}
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++;
}
addLast和addFirst大致邏輯差不多。只是將元素加在了鏈表最后，并重新設(shè)置了last的值。
add(E e)
public boolean add(E e) {
linkLast(e);
return true;
}
add(E e)方法和addLast(E e)相比只是多了一個返回值。
remove(Object o)
public boolean remove(Object o) {
//先判斷傳入的o是否為null。
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
//如果為null，則用==來比較。
if (x.item == null) {
//調(diào)用unlink方法來刪除元素。
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
//如果不為null，則用equals來比較值。
if (o.equals(x.item)) {
//調(diào)用unlink方法來刪除元素。
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
// assert x != null;
//將要刪除元素x的item，next，prev分別提出來。
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
//如果x的prev為null，證明x為第一個元素，刪除x后，這里就將next設(shè)置為第一個元素。
first = next;
} else {
//如果不為空，將x元素上一個元素的next指向x的next。
prev.next = next;
x.prev = null;
}
if (next == null) {
//如果x的next為null，說明x為最后一個元素，設(shè)置last為x的上一個元素。
last = prev;
} else {
//如果不為空，將x的下一個元素的prev指向x的prev。
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
remove(Object o)方法的關(guān)鍵解釋已經(jīng)放在了代碼中。
addAll(Collection<? extends E> c)
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//先檢查傳入的index是否越界，因?yàn)檫@個的index默認(rèn)為size，所以會將c直接添加到鏈表末尾。
checkPositionIndex(index);
//將c轉(zhuǎn)為數(shù)組，并判斷c的長度，如果為0，說明c為空數(shù)組，直接返回false。
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
//如果index等于size，說明將添加到鏈表末尾，所以pred為last。
succ = null;
pred = last;
} else {
//如果index不等于size，說明將添加到鏈表中，將目前index的元素賦值給succ，
//并將上一個元素賦值給pred。
succ = node(index);
pred = succ.prev;
}
//通過for循環(huán)生成新的Node實(shí)例，然后將每一個新的Node以此添加到pred后面。
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;
}
//添加完成后如果succ為null，則為在鏈表末尾添加，我們將我們添加的最后一個元素設(shè)置為last。
//如果succ不為null，則將原本index的下一個元素添加到prev后面。
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
addAll(Collection<? extends E> c)方法的關(guān)鍵解釋放在了代碼中。
clear()
public void clear() {
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++;
}
clear()方法很簡單，通過for循環(huán)依次將元素設(shè)置為null。
get(int index)
public E get(int index) {
//檢查index是否越界。
checkElementIndex(index);
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Node<E> node(int 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;
}
}
在get(int index)方法中，會先判斷index是在鏈表的前一半還是在后一半，然后分別從第一個元素或者是最后一個元素來看是向前或向后查找index對應(yīng)的元素。這樣作會使查找速度更快。
set(int index, E element)
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
這里直接調(diào)用node方法獲取index對應(yīng)的元素，然后將元素的值替換為element。
add(int index, E element)
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
//如果index為size則將element放入新的Node中并添加到鏈表末尾。
linkLast(element);
else
//否則將element放入新的Node中，添加到index對應(yīng)元素前面。
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
//獲取index對應(yīng)元素的前一個元素。
final Node<E> pred = succ.prev;
//新的Node位置在index對應(yīng)元素和前一個元素之間。
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
add(int index, E element)方法的解釋已經(jīng)放在了代碼中。
remove(int index)
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
remove(int index)方法先檢查index是否越界，然后調(diào)用node方法獲取index對應(yīng)的元素，最后調(diào)用unlink方法刪除這個元素。
indexOf
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;
}
先判斷傳入的o是否為null，如果為null則在for循環(huán)中用==來比較，如果不為null，則用equals來比較值，最后返回元素對應(yīng)的index，如果沒有對應(yīng)的元素，則返回-1。
toArray()
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;
}
toArray()方法先生成一個相同size的數(shù)組，然后通過for循環(huán)將鏈表的值全部賦值給數(shù)組，最后返回數(shù)組。
到這里L(fēng)inkedList的一些基本方法就分析完成了，代碼并不是很復(fù)雜，我們通過分析源碼可以發(fā)現(xiàn)LinkedList在增加，刪除方面代碼很簡單，相對應(yīng)的速度也就比較快。在查找，修改方面的代碼就比較復(fù)雜，每次都會從頭開始去找相應(yīng)的元素，速度也就會比較慢。綜合來看如果你的需求中有大量的增加，刪除的話可以考慮使用LinkedList。
如果文中有錯誤的地方歡迎大家指出來，也可以留言交流。
