哈嘍偏序，大家好，今天我們來(lái)簡(jiǎn)單聊聊LinkedList
LinkedList是由雙鏈表組成的集合，它不是線程安全的吩案，如果有在多線程中添加或刪除一個(gè)或多個(gè)元素，需要自己做同步處理帝簇，也可以調(diào)用List list = Collections.synchronizedList(new LinkedList(...));來(lái)獲取一個(gè)線程同步的集合徘郭。
下面我們開(kāi)始簡(jiǎn)單分析一下源碼，首先來(lái)看看LinkedList這個(gè)類(lèi)實(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接口來(lái)方便集合操作残揉，同時(shí)也實(shí)現(xiàn)了Deque接口，這樣就有了許多操作鏈表的方法闪湾。
Node
Node類(lèi)是LinkedList的一個(gè)內(nèi)部類(lèi)冲甘，這個(gè)類(lèi)是鏈表中存放元素用的⊥狙看下源碼
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;
}
}
有三個(gè)參數(shù)江醇，item是當(dāng)前元素的值，next指的是下一個(gè)元素何暇，prev指的是上一個(gè)元素陶夜。
重要參數(shù)
transient Node<E> first;
transient Node<E> last;
在LinkedList中有兩個(gè)比較重要的參數(shù)，一個(gè)是first裆站，指的是鏈表中第一個(gè)元素条辟。而last指的就是鏈表中最后一個(gè)元素黔夭。
LinkedList()
public LinkedList() {
}
這個(gè)LinkedList的一個(gè)空構(gòu)造函數(shù)，沒(méi)有做任何其他操作羽嫡。
LinkedList(Collection<? extends E> c)
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
這是一個(gè)帶參數(shù)的構(gòu)造函數(shù)本姥，將傳入進(jìn)來(lái)的集合全部添加到了LinkedList中，addAll這個(gè)方法我們?cè)诤竺孢M(jìn)行講解杭棵。
getFirst()
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
這個(gè)方法是獲取第一個(gè)元素的值婚惫，這里是直接將first賦值給f，因?yàn)閒irst在LinkedList中就是指的第一個(gè)元素魂爪。如果f為null的話就會(huì)報(bào)錯(cuò)先舷。最后會(huì)返回f的值。
getLast()
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
這個(gè)方法是獲取最后一個(gè)元素的值滓侍，這個(gè)方法和getFirst()方法類(lèi)似蒋川，直接將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的下一個(gè)元素賦值給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懒构，證明鏈表中只有一個(gè)元素，那么將最后一個(gè)元素也設(shè)置為null耘擂。
if (next == null)
last = null;
else
//如果不為null胆剧，那么將next的prev設(shè)置為null，原本指向的是f醉冤。
next.prev = null;
size--;
modCount++;
//最后返回f的值秩霍。
return element;
}
這個(gè)方法是移除第一個(gè)元素。還是先將first賦值給f蚁阳，然后調(diào)用unlinkFirst方法并將f傳入铃绒。unlinkFirst的相關(guān)解釋寫(xiě)在了代碼中。
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;
}
這個(gè)方法和removeFirst方法邏輯差不多螺捐，是將最后一個(gè)元素置為null颠悬，然后將倒數(shù)第二個(gè)元素賦值給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一個(gè)新的Node出來(lái)，并將f傳入澜沟，設(shè)置為新Node的下一個(gè)元素灾票。
final Node<E> newNode = new Node<>(null, e, f);
//將第一個(gè)元素設(shè)置為新的Node。
first = newNode;
//如果f為null表示原本鏈表中沒(méi)有元素茫虽，這時(shí)候添加了一個(gè)元
//素后第一個(gè)刊苍，最后一個(gè)元素都是newNode既们，所以要設(shè)置last為newNode。
if (f == null)
last = newNode;
else
//否則將原本第一個(gè)元素的prev設(shè)置為newNode正什。
f.prev = newNode;
size++;
modCount++;
}
在鏈表的頭部添加一個(gè)元素啥纸，關(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)相比只是多了一個(gè)返回值莹妒。
remove(Object o)
public boolean remove(Object o) {
//先判斷傳入的o是否為null。
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
//如果為null绰上，則用==來(lái)比較旨怠。
if (x.item == null) {
//調(diào)用unlink方法來(lái)刪除元素。
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
//如果不為null蜈块，則用equals來(lái)比較值鉴腻。
if (o.equals(x.item)) {
//調(diào)用unlink方法來(lái)刪除元素。
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
// assert x != null;
//將要?jiǎng)h除元素x的item百揭，next爽哎，prev分別提出來(lái)。
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
//如果x的prev為null器一，證明x為第一個(gè)元素课锌，刪除x后，這里就將next設(shè)置為第一個(gè)元素祈秕。
first = next;
} else {
//如果不為空渺贤，將x元素上一個(gè)元素的next指向x的next。
prev.next = next;
x.prev = null;
}
if (next == null) {
//如果x的next為null请毛，說(shuō)明x為最后一個(gè)元素志鞍，設(shè)置last為x的上一個(gè)元素。
last = prev;
} else {
//如果不為空方仿，將x的下一個(gè)元素的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)檫@個(gè)的index默認(rèn)為size此洲，所以會(huì)將c直接添加到鏈表末尾。
checkPositionIndex(index);
//將c轉(zhuǎn)為數(shù)組鳍征，并判斷c的長(zhǎng)度黍翎，如果為0，說(shuō)明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趟紊，說(shuō)明將添加到鏈表末尾，所以pred為last碰酝。
succ = null;
pred = last;
} else {
//如果index不等于size霎匈，說(shuō)明將添加到鏈表中，將目前index的元素賦值給succ送爸，
//并將上一個(gè)元素賦值給pred铛嘱。
succ = node(index);
pred = succ.prev;
}
//通過(guò)for循環(huán)生成新的Node實(shí)例，然后將每一個(gè)新的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墨吓，則為在鏈表末尾添加，我們將我們添加的最后一個(gè)元素設(shè)置為last纹磺。
//如果succ不為null帖烘，則將原本index的下一個(gè)元素添加到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()方法很簡(jiǎn)單秘症，通過(guò)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)方法中乡摹，會(huì)先判斷index是在鏈表的前一半還是在后一半，然后分別從第一個(gè)元素或者是最后一個(gè)元素來(lái)看是向前或向后查找index對(duì)應(yīng)的元素采转。這樣作會(huì)使查找速度更快聪廉。
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對(duì)應(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對(duì)應(yīng)元素前面惯悠。
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
//獲取index對(duì)應(yīng)元素的前一個(gè)元素邻邮。
final Node<E> pred = succ.prev;
//新的Node位置在index對(duì)應(yīng)元素和前一個(gè)元素之間。
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對(duì)應(yīng)的元素，最后調(diào)用unlink方法刪除這個(gè)元素情萤。
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)中用==來(lái)比較，如果不為null筋岛，則用equals來(lái)比較值娶视，最后返回元素對(duì)應(yīng)的index，如果沒(méi)有對(duì)應(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()方法先生成一個(gè)相同size的數(shù)組寝凌，然后通過(guò)for循環(huán)將鏈表的值全部賦值給數(shù)組，最后返回?cái)?shù)組孝赫。
到這里L(fēng)inkedList的一些基本方法就分析完成了较木，代碼并不是很復(fù)雜，我們通過(guò)分析源碼可以發(fā)現(xiàn)LinkedList在增加青柄，刪除方面代碼很簡(jiǎn)單伐债，相對(duì)應(yīng)的速度也就比較快。在查找致开，修改方面的代碼就比較復(fù)雜峰锁，每次都會(huì)從頭開(kāi)始去找相應(yīng)的元素，速度也就會(huì)比較慢双戳。綜合來(lái)看如果你的需求中有大量的增加祖今，刪除的話可以考慮使用LinkedList。
如果文中有錯(cuò)誤的地方歡迎大家指出來(lái)拣技，也可以留言交流。
