Java集合(一) —— Collection源碼分析
Java集合(二) —— ArrayList源碼分析
Java集合(三) —— LinkedList源碼分析
Java集合(四) —— PriorityQueue源碼分析
Java集合(五) —— HashSet源碼分析
Java集合(六) —— LinkedHashSet源碼分析
Java集合(七) —— TreeSet源碼分析
Java集合(八) —— HashMap源碼分析
Java集合(九) —— LinkedHashMap源碼分析
Java集合(十) —— TreeMap源碼分析
因?yàn)楸硎龇奖銌栴}宋渔，有時(shí)使用前驅(qū)&后繼節(jié)點(diǎn)凸郑，有時(shí)使用前驅(qū)&后繼指針，事實(shí)上對(duì)象保存的就是對(duì)象的地址或衡，也就是指針。
1.LinkedList繼承關(guān)系
LinkedList.png
2.LinkedList的數(shù)據(jù)結(jié)構(gòu)
private static class Node<E> {
E item;
Node<E> next; // 前驅(qū)節(jié)點(diǎn)
Node<E> prev; // 后繼節(jié)點(diǎn)
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList繼承自AbstractSequentialList并實(shí)現(xiàn)了List接口车遂，底層是雙向鏈表數(shù)據(jù)結(jié)構(gòu)封断；LinkedList同時(shí)實(shí)現(xiàn)了Deque接口，可用作雙向隊(duì)列舶担。
3.LinkedList性能分析
1.LinkedList是基于鏈表實(shí)現(xiàn)的坡疼，不存在容量不足的問題，所以沒有擴(kuò)容方法衣陶，也就沒有因擴(kuò)容帶來的性能問題柄瑰。
2.LinkedList查找元素時(shí)闸氮，根據(jù)index的大小需要從開始或從結(jié)尾遍歷到index位置，其時(shí)間復(fù)雜度為O(n)教沾。
3.LinkedList新增/刪除元素時(shí)蒲跨，不存在數(shù)據(jù)的移動(dòng)，只需要修改前驅(qū)節(jié)點(diǎn)與后繼節(jié)點(diǎn)的指向授翻，不考慮查找的情況下或悲，其時(shí)間復(fù)雜度為O(1)。
總結(jié)(對(duì)比ArrayList)：
- LinkedList在查找數(shù)據(jù)時(shí)需要遍歷鏈表堪唐，性能較差巡语；而新增或刪除只需要修改指針的指向，具有較好的性能淮菠，所以LinkedList常用于查詢較少男公，新增/刪除較多的場(chǎng)景。
- ArrayList具有較好的查詢性能合陵，而新增/刪除都可能引起大量元素的移動(dòng)枢赔，性能較差，所以ArrayList適用于查詢較多曙寡，新增/刪除較少的場(chǎng)景糠爬。
- LinkedList需要額外的內(nèi)存空間保存指針(前向指針(前向節(jié)點(diǎn))/后繼指針(后繼節(jié)點(diǎn)))信息，如果對(duì)內(nèi)存有較高要求举庶，可以考慮其他方案执隧。
- 盡量不要使用for循環(huán)遍歷LinkedList，應(yīng)該使用迭代器户侥，因?yàn)長(zhǎng)inkedList每訪問一個(gè)數(shù)據(jù)都要遍歷鏈表一次(具體看源碼分析)镀琉。
4.LinkedList源碼分析
1.成員變量分析
// 鏈表的大小
transient int size = 0;
// 第一個(gè)節(jié)點(diǎn)(頭結(jié)點(diǎn))
transient Node<E> first;
// 最后一個(gè)節(jié)點(diǎn)(尾結(jié)點(diǎn))
transient Node<E> last;
2.構(gòu)造方法分析
// .. 沒啥好說的
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
3.核心方法分析
3.1新增元素
1.從鏈表尾部新增一個(gè)節(jié)點(diǎn)
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 從鏈表尾部添加一個(gè)新節(jié)點(diǎn)
*/
void linkLast(E e) {
// 定義一個(gè)臨時(shí)變量保存最后一個(gè)節(jié)點(diǎn)
final Node<E> l = last;
// 創(chuàng)建一個(gè)新的節(jié)點(diǎn)，l == 上一個(gè)節(jié)點(diǎn) 蕊唐； null == 下一個(gè)節(jié)點(diǎn)(最后一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為null)
final Node<E> newNode = new Node<>(l, e, null);
// 將新建的節(jié)點(diǎn)置為最后一個(gè)節(jié)點(diǎn)
last = newNode;
if (l == null)
// 如果 l == null表示之前一個(gè)節(jié)點(diǎn)都沒有屋摔，新增節(jié)點(diǎn)之后first也指向新節(jié)點(diǎn)
first = newNode;
else
// 否則，之前的最后一個(gè)節(jié)點(diǎn)的后繼指針指向新建的節(jié)點(diǎn)
l.next = newNode;
// 鏈表大小+1
size++;
// 修改次數(shù)+1
modCount++;
}
2.指定位置新增節(jié)點(diǎn)
/**
* 指定位置新增元素
*/
public void add(int index, E element) {
// 檢查是否越界
checkPositionIndex(index);
if (index == size)
// 鏈表最后新增節(jié)點(diǎn)
linkLast(element);
else
// 查找指定下標(biāo)節(jié)點(diǎn)替梨，在指定下標(biāo)之前新增節(jié)點(diǎn)
linkBefore(element, node(index));
}
/**
* 查找節(jié)點(diǎn)的方法
* 這是LinkedList一個(gè)很重要的方法钓试，LinkedList很多方法都要依賴此方法查找對(duì)應(yīng)的節(jié)點(diǎn)
*/
Node<E> node(int index) {
// 判斷index的大小，決定要從頭開始遍歷鏈表的一半還是從尾部開始遍歷鏈表的一半
if (index < (size >> 1)) {
// 順序遍歷查找第index個(gè)節(jié)點(diǎn)并返回
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 倒序查找第index個(gè)節(jié)點(diǎn)并返回
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
/**
* 指定位置插入新的節(jié)點(diǎn)
*/
void linkBefore(E e, Node<E> succ) {
// succ：指定位置節(jié)點(diǎn)
// pred保存指定位置節(jié)點(diǎn)的前向指針
final Node<E> pred = succ.prev;
// 創(chuàng)建一個(gè)新的節(jié)點(diǎn)
final Node<E> newNode = new Node<>(pred, e, succ);
// 指定位置的節(jié)點(diǎn)的前向指針指向新建的節(jié)點(diǎn)
succ.prev = newNode;
if (pred == null)
// 如果pred == null副瀑，表示原來鏈表為空或者剛好從第一個(gè)節(jié)點(diǎn)插入新的節(jié)點(diǎn)(因?yàn)榈谝粋€(gè)節(jié)點(diǎn)沒有前向節(jié)點(diǎn)弓熏，pred = null)
first = newNode;
else
// 否則，指定位置節(jié)點(diǎn)的前向節(jié)點(diǎn)的后繼指針指向新建的節(jié)點(diǎn)(有些繞口糠睡，自己理解吧)
pred.next = newNode;
size++; // 鏈表大小+1
modCount++; // 修改次數(shù)+1
}
3.批量插入數(shù)據(jù)
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 批量插入數(shù)據(jù)
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 校驗(yàn)是否越界
checkPositionIndex(index);
// 將集合轉(zhuǎn)為數(shù)組
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
// 從鏈表尾部新增節(jié)點(diǎn)
succ = null;
pred = last;
} else {
// 指定位置節(jié)點(diǎn)
succ = node(index);
// 記錄指定位置節(jié)點(diǎn)的前向節(jié)點(diǎn)
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
// 從頭部新增節(jié)點(diǎn)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
// 如果是從尾部新增的節(jié)點(diǎn)挽鞠，就將原先最后一個(gè)節(jié)點(diǎn)指向新增元素之后的最后一個(gè)節(jié)點(diǎn)
last = pred;
} else {
// 如果是從其他某個(gè)位置新增的節(jié)點(diǎn)，就將新增的最后的一個(gè)節(jié)點(diǎn)的后繼指針指向指定位置節(jié)點(diǎn)(succ)；指定位置節(jié)點(diǎn)的前向指針指向新增的最后一個(gè)節(jié)點(diǎn)
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
3.2查找元素
1.查找數(shù)據(jù)
public E get(int index) {
// 檢查是否越界
checkElementIndex(index);
// 返回指定節(jié)點(diǎn)的元素
return node(index).item;
}
關(guān)于node方法之前已經(jīng)說過信认，這里不再重復(fù)材义，但是再說一遍，該方法很重要＜奚汀Ｆ涞唷！
3.3修改元素
1.修改元素
public E set(int index, E element) {
checkElementIndex(index);
// 查找指定位置的Node節(jié)點(diǎn)(又是熟悉的node方法)
Node<E> x = node(index);
// 記錄節(jié)點(diǎn)上的元素
E oldVal = x.item;
// 將舊元素指向新元素
x.item = element;
// 返回舊元素
return oldVal;
}
3.4刪除元素
1.根據(jù)索引刪除
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// 節(jié)點(diǎn)元素
final E element = x.item;
// 后繼節(jié)點(diǎn)
final Node<E> next = x.next;
// 前驅(qū)節(jié)點(diǎn)
final Node<E> prev = x.prev;
if (prev == null) {
// prev == null表示刪除的x是頭結(jié)點(diǎn)
first = next;
} else {
// 否則橄教，前驅(qū)節(jié)點(diǎn)的后繼指針指向x的后繼節(jié)點(diǎn)
prev.next = next;
// 將x的前驅(qū)節(jié)點(diǎn)置為null
x.prev = null;
}
if (next == null) {
// next == null清寇，說明刪除的x的尾結(jié)點(diǎn)
last = prev;
} else {
// 否則喘漏，后繼節(jié)點(diǎn)的前驅(qū)指針指向x的前驅(qū)節(jié)點(diǎn)
next.prev = prev;
// 將x的后繼節(jié)點(diǎn)置為null
x.next = null;
}
// 將x節(jié)點(diǎn)中的元素item置為null护蝶，此時(shí)達(dá)到刪除一個(gè)節(jié)點(diǎn)的目的
x.item = null;
size--;
modCount++;
// 返回移除的元素
return element;
}
2.根據(jù)元素刪除
public boolean remove(Object o) {
// 無論o是否為null，最終都是調(diào)用unlink(x)方法進(jìn)行刪除
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;
}
3.批量刪除
/**
* LinkedList并沒有該方法翩迈，該方法是定義在其父類AbstractCollection上的
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
// 迭代器
Iterator<?> it = iterator();
while (it.hasNext()) {
// 判斷迭代的元素是否包含在容器c中
if (c.contains(it.next())) {
// 真正刪除元素的方法
it.remove();
modified = true;
}
}
return modified;
}
/**
* AbstractSequentialList復(fù)寫父類的方法
*/
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator() {
return listIterator(0);
}
/**
* LinkedList復(fù)寫父類的方法
*/
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
// ListItr初始化時(shí)持灰，將操作計(jì)數(shù)器modCount賦值給expectedModCount。
// 之后每次調(diào)用remove方法都會(huì)校驗(yàn)expectedModCount與modCount是否相等负饲，否則會(huì)拋出異常堤魁。
private int expectedModCount = modCount;
// ...
}
/**
* 調(diào)用next方法，迭代到下一個(gè)節(jié)點(diǎn)
*/
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
// lastReturned的下一個(gè)節(jié)點(diǎn)
Node<E> lastNext = lastReturned.next;
// 刪除lastReturned節(jié)點(diǎn)
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
final void checkForComodification() {
// 校驗(yàn)modCount與expectedModCount
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
5.關(guān)于LinkedList作為雙向隊(duì)列
前面已經(jīng)說過LinkedList實(shí)現(xiàn)了Deque接口返十，可以作為雙向隊(duì)列使用
1.從鏈表頭部或尾部新增節(jié)點(diǎn)
// 作為雙向隊(duì)列從頭部或尾部新增節(jié)點(diǎn)
public void addFirst(E e) {
linkFirst(e);
}
/**
* 從頭部新增節(jié)點(diǎn)
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
// 如果是空鏈表妥泉，則新增的節(jié)點(diǎn)既是第一個(gè)節(jié)點(diǎn)又是最后一個(gè)節(jié)點(diǎn)
last = newNode;
else
// 否則節(jié)點(diǎn)f的前向指針指向新增的節(jié)點(diǎn)
f.prev = newNode;
size++;
modCount++;
}
/**
* 從尾部新增節(jié)點(diǎn)
*/
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++;
}
2.從頭部或尾部獲取元素
// 過于簡(jiǎn)單不做分析
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
3.從頭部或尾部刪除元素
/**
* 從頭部刪除節(jié)點(diǎn)
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
final E element = f.item;
// 記錄f的下一個(gè)節(jié)點(diǎn)
final Node<E> next = f.next;
// 置為null洞坑，表示刪除節(jié)點(diǎn)
f.item = null;
f.next = null; // help GC
// 使next成為第一個(gè)節(jié)點(diǎn)
first = next;
if (next == null)
// 刪除的是最后一個(gè)節(jié)點(diǎn)盲链，則last也置為null
last = null;
else
// 否則next節(jié)點(diǎn)的前向指針置為null(頭結(jié)點(diǎn)的前向指針與尾結(jié)點(diǎn)的后繼指針為null)
next.prev = null;
size--;
modCount++;
return element;
}
/**
* 從尾部刪除節(jié)點(diǎn)
* 與從頭部刪除節(jié)點(diǎn)的邏輯類似
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
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;
}
6.總結(jié)
1.LinkedList是雙向鏈表的數(shù)據(jù)結(jié)構(gòu)，相比于單鏈表迟杂，在刪除一個(gè)節(jié)點(diǎn)時(shí)刽沾，不需要像單鏈表一樣一路保存當(dāng)前節(jié)點(diǎn)的前向節(jié)點(diǎn)，因?yàn)殡p向鏈表當(dāng)前節(jié)點(diǎn)本身就已經(jīng)保存有前向指針排拷，所以刪除時(shí)雙向鏈表比單向鏈表效率更高侧漓。
2.需要額外的內(nèi)存空間保存節(jié)點(diǎn)信息。
3.對(duì)于大數(shù)據(jù)量來說监氢，相比ArrayList布蔗，具有增刪快查找慢特性。
