LinkedList是Java中常用的一個集合類筐喳，是List接口的一個實現(xiàn)類铜幽，而List接口繼承自Collection接口吁讨，所以LinkedList是Collection的一個實現(xiàn)類届巩。
本篇主要討論一下LinkedList底層代碼的實現(xiàn)壮池。
核心成員變量
//size表示linkedList的大小偏瓤，即該linkedList已經(jīng)存儲了多少個元素
transient int size = 0;
//由于linkedList是由鏈表實現(xiàn)的，該first表示鏈表的第一個節(jié)點(diǎn)
transient Node<E> first;
//由于linkedList是由鏈表實現(xiàn)的椰憋，該list表示鏈表的最后個節(jié)點(diǎn)
transient Node<E> last;
Node的實現(xiàn)
//該Node是由雙鏈表的實現(xiàn)
private static class Node<E> {
//該節(jié)點(diǎn)表示實際存儲的元素
E item;
//該節(jié)點(diǎn)的下一個節(jié)點(diǎn)
Node<E> next;
//該節(jié)點(diǎn)的上一個節(jié)點(diǎn)
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList無參構(gòu)造函數(shù)
//該構(gòu)造函數(shù)實際什么也沒有做
public LinkedList() {
}
add(E e)方法的實現(xiàn)
//該方法向鏈表尾部添加一個元素厅克，并返回true
public boolean add(E e) {
//鏈表尾部添加元素
linkLast(e);
return true;
}
//向鏈表尾部添加一個元素
void linkLast(E e) {
//使用一個局部變量指向鏈表里面的最后一個元素
final Node<E> l = last;
//新創(chuàng)建一個node節(jié)點(diǎn)，使該新建的節(jié)點(diǎn)的上一個節(jié)點(diǎn)指向之前鏈表中的最后一個節(jié)點(diǎn)
final Node<E> newNode = new Node<>(l, e, null);
//因為是在尾部添加節(jié)點(diǎn)橙依，所以新創(chuàng)建的節(jié)點(diǎn)賦予last變量证舟，表示last指向鏈表中的最后一個幾點(diǎn)
last = newNode;
//如果l為空，說明之前的鏈表中的節(jié)點(diǎn)元素為空
if (l == null)
//所以新創(chuàng)建的節(jié)點(diǎn)賦予first變量窗骑，到這里表示鏈表中僅有一個節(jié)點(diǎn)元素女责，所以該節(jié)點(diǎn)元素即是第一個節(jié)點(diǎn)，也是最后一個節(jié)點(diǎn)
first = newNode;
else
//如果l不為空创译，說明之前的鏈表不為空抵知，newNode又是最后一個節(jié)點(diǎn)，又因為l為之前舊鏈表的最后一個節(jié)點(diǎn)软族，所以l的下一個節(jié)點(diǎn)指向當(dāng)前新建的節(jié)點(diǎn)
l.next = newNode;
//size+1刷喜，用來表示當(dāng)前數(shù)組已經(jīng)存儲了多少個節(jié)點(diǎn)元素
size++;
modCount++;
}
具體說明：
- 當(dāng)往LinkedList添加元素時，實際在鏈表最后添加一個節(jié)點(diǎn)立砸；
- 當(dāng)往鏈表中添加第一個節(jié)點(diǎn)時掖疮，由于鏈表中僅有一個節(jié)點(diǎn)，所以first指向該節(jié)點(diǎn)颗祝，last也指向該節(jié)點(diǎn)浊闪；
- 當(dāng)往鏈表中添加第二個節(jié)點(diǎn)時，由于鏈表中已經(jīng)有一個節(jié)點(diǎn)螺戳，所以first還是指向鏈表中的第一個節(jié)點(diǎn)搁宾，而新建的第二個節(jié)點(diǎn)的prev指向第一個節(jié)點(diǎn)，last指向新建的第二個節(jié)點(diǎn)温峭，并建第一個節(jié)點(diǎn)的next指向第二個節(jié)點(diǎn)猛铅；
如圖所示：
只有一個節(jié)點(diǎn)的時候
當(dāng)有兩個節(jié)點(diǎn)的時候
remove()方法的實現(xiàn)
public E remove() {
//刪除鏈表中的第一個節(jié)點(diǎn)
return removeFirst();
}
public E removeFirst() {
//獲取鏈表的第一個節(jié)點(diǎn)
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
//刪除第一個的節(jié)點(diǎn)，并返回刪除的數(shù)據(jù)
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
//獲取第一個節(jié)點(diǎn)存儲的數(shù)據(jù)凤藏，用于返回
final E element = f.item;
//獲取第一個節(jié)點(diǎn)的之后的下一個節(jié)點(diǎn)奸忽，第一個節(jié)點(diǎn)被刪除后堕伪，下一個節(jié)點(diǎn)就是first節(jié)點(diǎn)
final Node<E> next = f.next;
//清空第一個節(jié)點(diǎn)的信息，即清空要刪除節(jié)點(diǎn)的信息
f.item = null;
f.next = null;
//將原來第一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)賦予first引用栗菜，也就是原來第二個節(jié)點(diǎn)變?yōu)殒湵淼牡谝粋€節(jié)點(diǎn)
first = next;
//如果原來第一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)為空欠雌，那么說明鏈表此時已經(jīng)為空了
if (next == null)
//此時，將last也置空
last = null;
else
//原來第二個節(jié)點(diǎn)變?yōu)榈谝粋€節(jié)點(diǎn)疙筹，因為第一個節(jié)點(diǎn)前面沒有節(jié)點(diǎn)了富俄，所以將第一個節(jié)點(diǎn)的prev置空
next.prev = null;
//size-1，表示鏈表存儲的數(shù)據(jù)-1
size--;
modCount++;
//返回刪除的元素
return element;
}
具體說明：
- 該方法將刪除鏈表中的第一個節(jié)點(diǎn)而咆，并將刪除的數(shù)據(jù)返回霍比。
remove(Object o)方法實現(xiàn)
//刪除指定元素的節(jié)點(diǎn)，刪除成功暴备，返回true悠瞬，否則，返回false
public boolean remove(Object o) {
if (o == null) {
//如果要刪除的元素為null涯捻，那么將刪除鏈表中第一個為null的節(jié)點(diǎn)
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//刪除鏈表中第一個與傳入值相等的節(jié)點(diǎn)
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//刪除指定節(jié)點(diǎn)
E unlink(Node<E> x) {
//獲取要刪除節(jié)點(diǎn)的元素的值浅妆，用于刪除后返回
final E element = x.item;
//獲取要刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)
final Node<E> next = x.next;
//獲取要刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)
final Node<E> prev = x.prev;
if (prev == null) {
//如果要刪除的上一個節(jié)點(diǎn)為空，說明當(dāng)前要刪除的節(jié)點(diǎn)為第一個節(jié)點(diǎn)
//那么需要將first指向要刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)
first = next;
} else {
//將要刪除的節(jié)點(diǎn)的上一個節(jié)點(diǎn)的引用指向要刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)
//比如原來是1,2,3 那么刪除2后障癌，就變成 1,3 也就是將1指向3
prev.next = next;
//并將刪除的節(jié)點(diǎn)的上一個指針置null凌外，也就是將2指向1的指針置null
x.prev = null;
}
if (next == null) {
//如果要刪除的下一個節(jié)點(diǎn)為空，說明當(dāng)前要刪除的節(jié)點(diǎn)為最后節(jié)點(diǎn)
//那么需要將last指向要刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)
last = prev;
} else {
//將要刪除的節(jié)點(diǎn)的下一個節(jié)點(diǎn)的引用指向要刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)
//比如原來是1,2,3 那么刪除2后涛浙，就變成 1,3 也就是將3指向1
next.prev = prev;
//并將刪除的節(jié)點(diǎn)的下一個指針置null康辑，也就是將2指向3的指針置null
x.next = null;
}
//清空刪除節(jié)點(diǎn)的數(shù)據(jù)
x.item = null;
//size-1，表示刪除了一個數(shù)據(jù)
size--;
modCount++;
//返回刪除的節(jié)點(diǎn)的元素
return element;
}
具體說明：
- 傳入要刪除的數(shù)據(jù)蝗拿，然后遍歷鏈表晾捏，刪除第一個匹配的數(shù)據(jù)節(jié)點(diǎn)；
remove(int index)方法實現(xiàn)
//刪除指定索引下標(biāo)的元素
public E remove(int index) {
//首先哀托，檢查傳入的索引下標(biāo)是否合法惦辛，不合法將拋出IndexOutOfBoundsException
checkElementIndex(index);
//node方法根據(jù)index取出要刪除的節(jié)點(diǎn)，unlink在上面已經(jīng)分析過仓手，就是刪除指定節(jié)點(diǎn)并返回該節(jié)點(diǎn)的數(shù)據(jù)
return unlink(node(index));
}
//檢查索引是否合法
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//傳入索引必須大于等于0小于size
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
//根據(jù)索引下標(biāo)胖齐，變量鏈表，獲取指定下標(biāo)的節(jié)點(diǎn)
Node<E> node(int index) {
//判斷如果要刪除的索引小于size/2嗽冒，則從鏈表左邊開始遍歷查找節(jié)點(diǎn)
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//判斷如果要刪除的索引大于size/2呀伙，則從鏈表右邊開始遍歷查找節(jié)點(diǎn)
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
具體步驟：
- 傳入要刪除的索引下標(biāo)，首先檢查該索引下標(biāo)是否合法添坊；
- 如果下標(biāo)合法剿另，則調(diào)用node（index）查詢要刪除的節(jié)點(diǎn)，如果要刪除的索引下標(biāo)在size的左半部分（index < size/2），那邊將從左邊（first）開始遍歷鏈表查詢雨女，反之從右邊（last）開始查找谚攒；
- 獲取到要刪除的節(jié)點(diǎn)時，調(diào)用unlink(node)刪除節(jié)點(diǎn)氛堕，并返回節(jié)點(diǎn)數(shù)據(jù)馏臭。
set(int index, E element)方法實現(xiàn)
//修改指定索引下標(biāo)的節(jié)點(diǎn)的值，并返回修改前的值
public E set(int index, E element) {
//檢查index是否合法
checkElementIndex(index);
//獲取到index的節(jié)點(diǎn)
Node<E> x = node(index);
//獲取到指定下標(biāo)節(jié)點(diǎn)的舊的值
E oldVal = x.item;
//替換指定下標(biāo)節(jié)點(diǎn)的值
x.item = element;
//返回指定下標(biāo)節(jié)點(diǎn)舊的值
return oldVal;
}
具體步驟：
- 傳入要修改的節(jié)點(diǎn)的索引下標(biāo)與要修改的值讼稚；
- 檢查下標(biāo)是否合法括儒；
- 調(diào)用node(index)獲取指定下標(biāo)的節(jié)點(diǎn)；
- 獲取指定下標(biāo)節(jié)點(diǎn)的值锐想，并為該節(jié)點(diǎn)設(shè)置新的值帮寻；
- 返回指定下標(biāo)節(jié)點(diǎn)替換前的值。
get(int index)方法實現(xiàn)
//根據(jù)Index獲取數(shù)據(jù)
public E get(int index) {
checkElementIndex(index);
//調(diào)用node獲取數(shù)據(jù)
return node(index).item;
}
具體說明：
- 可以看到痛倚，其實get(index)這種方式獲取數(shù)據(jù)规婆，也是通過調(diào)用node(index)去獲取數(shù)據(jù)；
適用場景
通過源碼的分析蝉稳，我們知道，linkedList底層是基于鏈表實現(xiàn)的掘鄙，每個添加一個元素的時候耘戚，都是在鏈表的尾部添加節(jié)點(diǎn)，不涉及到鏈表的循環(huán)遍歷操漠；當(dāng)刪除元素時收津，如果調(diào)用無參的remove方法時，只是刪除鏈表的第一個節(jié)點(diǎn)浊伙，也不涉及到鏈表的循環(huán)遍歷撞秋；而當(dāng)需要通過索引下標(biāo)獲取數(shù)據(jù)的時候，涉及到了鏈表的遍歷嚣鄙；所以在這種添加與刪除節(jié)點(diǎn)比較多而根據(jù)索引去訪問元素比較少的場景下吻贿，比較適合使用linkedList。
