如果本文中有不正確的地方請指出
由于沒有留言可以在公眾號添加我的好友共同討論莫绣。
1.介紹
LinkedList 是線程不安全的畴蒲，允許元素為null的雙向鏈表。
2.繼承結(jié)構(gòu)
我們來看一下LinkedList的繼承結(jié)構(gòu)圖：
代碼實(shí)現(xiàn):
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- Cloneable實(shí)現(xiàn)克隆
- Serializable序列化
- List 定義了一些集合類的方法
- Deque雙向隊(duì)列接口(就是兩端都可以進(jìn)行增加刪除操作)
注意一點(diǎn)LinkedList并沒有實(shí)現(xiàn)RandomAccess所以隨機(jī)訪問是非常慢的对室。
3.屬性
元素個數(shù)
transient int size = 0;
指向第一個節(jié)點(diǎn)的指針(注釋直接就寫著)
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
指向最后一個節(jié)點(diǎn)的指針
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
transient關(guān)鍵字的作用是保持變量不被序列化具體的百度模燥。
不過我們注意到LinkedList是有Node類，這里的Node是一個內(nèi)部類：
- item存儲的元素
- next指向后置節(jié)點(diǎn)
- prev指向前置節(jié)點(diǎn)
- 內(nèi)部類同時包含了一個構(gòu)造函數(shù)
其實(shí)LinkedList 集合就是由許多個 Node 對象y一個連著一個組成手構(gòu)成软驰，可以看下方的圖
可以看上面的四個元素涧窒，分別就是四個Node對象，可以看到node1所指向的prev上一個節(jié)點(diǎn)是空也就是沒有上節(jié)點(diǎn),node4所指向的next節(jié)點(diǎn)為空也就是沒有下一個節(jié)點(diǎn)锭亏。
4.構(gòu)造方法
LinkedList共有兩個構(gòu)造方法纠吴，一個是創(chuàng)建一個空的構(gòu)造函數(shù)，一個是將已有的Collection添加到LinkedList中慧瘤。
因?yàn)長inkedList不同于ArrayList所以初始化不需要指定大小取分配內(nèi)存空間戴已。
5.添加元素
LinkedList有幾種添加方法我們先從add()開始固该。
5.1 add方法
checkPositionIndex(index);
可以看到在調(diào)用Add方法首先校驗(yàn)一下索引是否合法，如果不合法就會拋出異常糖儡。
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
然后如果索引值等于size的值則直接調(diào)用linkLast插入到尾部節(jié)點(diǎn)伐坏。
否則就linkBefore方法。
linkLast方法：
void linkLast(E e) {
//將l設(shè)為尾節(jié)點(diǎn)
final Node<E> l = last;
//構(gòu)造一個新節(jié)點(diǎn)握联，節(jié)點(diǎn)上一個節(jié)點(diǎn)引用指向尾節(jié)點(diǎn)l
final Node<E> newNode = new Node<>(l, e, null);
//將尾節(jié)點(diǎn)設(shè)為創(chuàng)建的新節(jié)點(diǎn)
last = newNode;
//如果尾節(jié)點(diǎn)為空桦沉，表示原先鏈表為空
if (l == null)
//將頭節(jié)點(diǎn)設(shè)為新創(chuàng)建的節(jié)點(diǎn)（尾節(jié)點(diǎn)也是新創(chuàng)建的節(jié)點(diǎn)）
first = newNode;
else
//將原來尾節(jié)點(diǎn)下一個節(jié)點(diǎn)的引用指向新節(jié)點(diǎn)
l.next = newNode;
size++;//節(jié)點(diǎn)數(shù)加1
modCount++;
}
注意一下這里出現(xiàn)了modCount方法，和ArrayList中一樣金闽，iterator和listIterator方法返回的迭代器和列表迭代器實(shí)現(xiàn)使用纯露。
linkBefore:
void linkBefore(E e, Node<E> succ) {
//將pred設(shè)為插入節(jié)點(diǎn)的上一個節(jié)點(diǎn)
final Node<E> pred = succ.prev;
//將新節(jié)點(diǎn)的上引用設(shè)為pred,下引用設(shè)為succ
final Node<E> newNode = new Node<>(pred, e, succ);
//succ的上一個節(jié)點(diǎn)的引用設(shè)為新節(jié)點(diǎn)
succ.prev = newNode;
//如果插入節(jié)點(diǎn)的上一個節(jié)點(diǎn)引用為空
if (pred == null)
//新節(jié)點(diǎn)就是頭節(jié)點(diǎn)
first = newNode;
else
//插入節(jié)點(diǎn)的下一個節(jié)點(diǎn)引用設(shè)為新節(jié)點(diǎn)
pred.next = newNode;
size++;
//同上
modCount++;
}
5.2 addAll()
在LinkedList中有兩個addAll方法一個是 addAll(Collection<? extends E> c)一個是addAll(int index, Collection<? extends E> c),其實(shí)
addAll(Collection<? extends E> c)=addAll(int index, Collection<? extends E> c)
可以看下面的截圖:
源碼如下：
現(xiàn)在開始分析源碼：
首先我們可以看到先調(diào)用了checkPositionIndex(index);方法來檢查索引是否合法。
然后將傳進(jìn)來的Collection轉(zhuǎn)成Object數(shù)組
Object[] a = c.toArray();
如果集合為空就直接返回false
if (numNew == 0)
return false;
如果插入的位置等于鏈表的長度就把新增加的元素放在尾部代芜。
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
最后在循環(huán)要插入的元素埠褪。這里我們可以看到上面也有modCount。
5.3 addFirst()
addFirst是將元素插入到LinkedList的頭部挤庇。
如果現(xiàn)在的機(jī)構(gòu)是下圖的：
addFirst執(zhí)行的操作就是：
紅色是使用addFirst插入后的位置钞速。一下是源碼
調(diào)用了linkFirst方法。
上面的操作時：
- 首先執(zhí)行final Node<E> f = first;將頭節(jié)點(diǎn)賦值給 f
- final Node<E> newNode = new Node<>(null, e, f);將指定元素構(gòu)造成一個新節(jié)點(diǎn)嫡秕，此節(jié)點(diǎn)的指向下一個節(jié)點(diǎn)的引用為頭節(jié)點(diǎn)
//將新節(jié)點(diǎn)設(shè)為頭節(jié)點(diǎn)渴语，那么原先的頭節(jié)點(diǎn) f 變?yōu)榈诙€節(jié)點(diǎn)
first = newNode;
//如果第二個節(jié)點(diǎn)為空，也就是原先鏈表是空
if (f == null)
//將這個新節(jié)點(diǎn)也設(shè)為尾節(jié)點(diǎn)（前面已經(jīng)設(shè)為頭節(jié)點(diǎn)了）
last = newNode;
else
f.prev = newNode;//將原先的頭節(jié)點(diǎn)的上一個節(jié)點(diǎn)指向新節(jié)點(diǎn)
size++;//節(jié)點(diǎn)數(shù)加1
modCount++;//和ArrayList中一樣記錄修改次數(shù)
5.4 addLast方法
addLast是將元素插入到尾部如圖(黃色元素)：
黃色node是新增加淘菩。注意add也是把元素添加到尾部遵班。我們來看一下源碼：
這里看到addLast和add是調(diào)用的同一方法，這里就不在講解潮改∠林＃可以看上方的代碼。
由于文章比較長分為兩次更新汇在。下一篇文章繼續(xù)分析
上次分析了LinkedList的結(jié)構(gòu)和添加方法這次開始分析下面的翰萨。
注意源碼版本為JDK1.8
直接進(jìn)入正題。
1.刪除
1.2remove()
在LinkedList中remove()和removeFirst()是相同的
在LinkedList中的刪除其實(shí)就是通過修改上一個節(jié)點(diǎn)和指向下一個節(jié)點(diǎn)的引用完成的,可以看下面的圖片：
我們可以看到把node6的prev指向清空然后把node3的next設(shè)置成空就完成了刪除的操作糕殉。
看一下JDK的源碼實(shí)現(xiàn)：
調(diào)用removeFirst,在調(diào)用removeFirst中先獲取頭部節(jié)點(diǎn)亩鬼，如果頭節(jié)點(diǎn)為空就拋異常。
調(diào)用unlinkFirst
private E unlinkFirst(Node<E> f) {
final E element = f.item;
//next 為頭結(jié)點(diǎn)的下一個節(jié)點(diǎn)
final Node<E> next = f.next;
f.item = null;
// 將節(jié)點(diǎn)的元素以及引用都設(shè)為 null阿蝶，便于垃圾回收
f.next = null;
//修改頭結(jié)點(diǎn)為第二個節(jié)點(diǎn)
first = next;
//如果第二個節(jié)點(diǎn)為空（當(dāng)前鏈表只存在第一個元素）
if (next == null)
//那么尾節(jié)點(diǎn)也置為 null
last = null;
else
//如果第二個節(jié)點(diǎn)不為空雳锋，那么將第二個節(jié)點(diǎn)的上一個引用置為 null
next.prev = null;
size--;
modCount++;
return element;
}
1.3 removeLast()
我們看一下removeLast，從列表中刪除最后一個元素
首先看到先獲取了last最后一個元素羡洁，如果為空然后就拋異常
然后調(diào)用了unlinkLast
看到unlinkLast方法中有一個 help gc ,它的主要作用就是幫助GC來做垃圾回收玷过。
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;
//幫助GC垃圾回收
l.prev = null;
//尾節(jié)點(diǎn)為倒數(shù)第二個節(jié)點(diǎn)
last = prev;
//如果倒數(shù)第二個節(jié)點(diǎn)為null
if (prev == null)
//那么將節(jié)點(diǎn)也置為 null
first = null;
else
prev.next = null;
//如果倒數(shù)第二個節(jié)點(diǎn)不為空，那么將倒數(shù)第二個節(jié)點(diǎn)的下一個引用置為 null
size--;
modCount++;
return element;
}
同樣執(zhí)行了modCount++
1.3 remove(int index)
根據(jù)索引來刪除元素
//刪除此列表中指定位置的元素
public E remove(int index) {
//判斷索引 index >= 0 && index <= size中時拋出IndexOutOfBoundsException異常
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {//如果刪除節(jié)點(diǎn)位置的上一個節(jié)點(diǎn)引用為null（表示刪除第一個元素）
first = next;//將頭結(jié)點(diǎn)置為第一個元素的下一個節(jié)點(diǎn)
} else {//如果刪除節(jié)點(diǎn)位置的上一個節(jié)點(diǎn)引用不為null
prev.next = next;//將刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)引用指向刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)（去掉刪除節(jié)點(diǎn)）
x.prev = null;//刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)引用置為null
}
if (next == null) {//如果刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)引用為null（表示刪除最后一個節(jié)點(diǎn)）
last = prev;//將尾節(jié)點(diǎn)置為刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)
} else {//不是刪除尾節(jié)點(diǎn)
next.prev = prev;//將刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)的上一個節(jié)點(diǎn)的引用指向刪除節(jié)點(diǎn)的上一個節(jié)點(diǎn)
x.next = null;//將刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)引用置為null
}
//刪除節(jié)點(diǎn)內(nèi)容置為null，便于垃圾回收
x.item = null;
size--;
modCount++;
return element;
}
3.set(int index, E element)
簡單粗暴直接貼代碼
public E set(int index, E element) {
//檢查索引是否合法否則IndexOutOfBoundsException異常
checkElementIndex(index);
//獲取指定索引的元素
Node<E> x = node(index);
E oldVal = x.item;
//將指定索引的元素替換成新的元素
x.item = element;
/返回指定索引位置原來的元素
return oldVal;/
}
4.查找元素
很簡單
4.1 getFirst()
返回第一個元素
public E getFirst() {
獲取頭
final Node<E> f = first;
判斷是否為空
if (f == null)
throw new NoSuchElementException();
元素返回
return f.item;
}
4.2 getLast()
返回最后一個元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
4.3 get
返回指定索引元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
暫時就這么多
原創(chuàng)不易,如果你喜歡本文或者對你有幫助就請轉(zhuǎn)發(fā)
