java集合—LinkedList源碼說(shuō)個(gè)明明白白！
1.LinkedList介紹
我們除了最最常用的ArrayList之外，還有LinkedList，這到底是什么東西？從LinkedList官方文檔，我們可以了解到，它其實(shí)是實(shí)現(xiàn)了List和Queue的雙向鏈表結(jié)構(gòu)，而ArrayList底層則是數(shù)組結(jié)構(gòu)。
下面的講解基于jdk 1.8:
繼承了AbstractSequentialList，實(shí)現(xiàn)了List,Queue,Cloneable,Serializable，既可以當(dāng)成列表使用，也可以當(dāng)成隊(duì)列，堆棧使用。主要特點(diǎn)有：
線程不安全，不同步，如果需要同步需要使用 List list = Collections.synchronizedList(new LinkedList());實(shí)現(xiàn) List接口，可以對(duì)它進(jìn)行隊(duì)列操作實(shí)現(xiàn) Queue接口，可以當(dāng)成堆?；蛘唠p向隊(duì)列使用實(shí)現(xiàn)Cloneable接口，可以被克隆，淺拷貝 實(shí)現(xiàn) Serializable，可以被序列化和反序列化
下面是LinkedList的結(jié)構(gòu)，注意：指針結(jié)束指向的是node，開始的是prev或者next
源碼定義如下：
public?class?LinkedList<E>
????extends?AbstractSequentialList<E>
????implements?List<E>,?Deque<E>,?Cloneable,?java.io.Serializable{
????}
2.成員變量
成員變量相對(duì)比較簡(jiǎn)單，因?yàn)椴幌?code style="font-size: 14px;overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(30, 107, 184);background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;">ArrayList一樣，需要使用數(shù)組保存元素，LinkedList是靠引用來(lái)關(guān)聯(lián)前后節(jié)點(diǎn)，所以這里只有大小，第一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn),以及序列化的uid。
????//?大小
????transient?int?size?=?0;
????//?第一個(gè)節(jié)點(diǎn)
????transient?Node?first;
????//?最后一個(gè)節(jié)點(diǎn)
????transient?Node?last;
??//?序列化uid
????private?static?final?long?serialVersionUID?=?876323262645176354L;
我們來(lái)看看Node到底是何方神圣？其實(shí)就是內(nèi)部類，里面的item是真正保存節(jié)點(diǎn)的地方，next是下一個(gè)節(jié)點(diǎn)的引用，prev是上一個(gè)節(jié)點(diǎn)的引用。這里也體現(xiàn)了LinkedList其實(shí)就是雙線鏈表。
只有一個(gè)構(gòu)造函數(shù)，三個(gè)參數(shù)分別對(duì)應(yīng)三個(gè)屬性。
????private?static?class?Node<E>?{
????????//?節(jié)點(diǎn)里面的數(shù)據(jù)
????????E?item;
????????//?下一個(gè)節(jié)點(diǎn)的引用
????????Node?next;
????????//?上一個(gè)節(jié)點(diǎn)的引用
????????Node?prev;
????????//?節(jié)點(diǎn)的構(gòu)造函數(shù)，重寫之后，無(wú)參數(shù)構(gòu)造器已經(jīng)被覆蓋，三個(gè)參數(shù)分別對(duì)應(yīng)三個(gè)屬性
????????Node(Node?prev,?E?element,?Node?next)?{
????????????this.item?=?element;
????????????this.next?=?next;
????????????this.prev?=?prev;
????????}
????}
3. 構(gòu)造函數(shù)
構(gòu)造函數(shù)有兩個(gè)，一個(gè)是無(wú)參數(shù)構(gòu)造函數(shù)，另一個(gè)是初始化集合元素，里面調(diào)用的其實(shí)是addAll，一看就是將里面所有的元素加入到集合中。
????public?LinkedList()?{
????}
????public?LinkedList(Collection?c)?{
????????this();
????????addAll(c);
????}
4. 常用List方法解析
4.1 查找相關(guān)
4.1.1 getFirst()
獲取第一個(gè)元素：
????public?E?getFirst()?{
????????//?保存第一個(gè)元素為f，注意是final的，
????????final?Node?f?=?first;
????????if?(f?==?null)
????????????//?如果沒有第一個(gè)元素，那么就會(huì)拋出異常
????????????throw?new?NoSuchElementException();
????????//?返回第一個(gè)元素的item
????????return?f.item;
????}
4.1.2 getLast()
獲取最后一個(gè)元素,和獲取第一個(gè)的原理差不多
????public?E?getLast()?{
????????//?保存最后一個(gè)元素的引用為l
????????final?Node?l?=?last;
????????//?如果為空，拋出錯(cuò)誤
????????if?(l?==?null)
????????????throw?new?NoSuchElementException();
????????//?返回item
????????return?l.item;
????}
4.1.3 get(int index)
通過(guò)索引來(lái)獲取元素,里面是調(diào)用了另外一個(gè)方法先獲取節(jié)點(diǎn)，再獲取該節(jié)點(diǎn)的item,在此之前，做了index安全性校驗(yàn)。
????public?E?get(int?index)?{
????????checkElementIndex(index);
????????return?node(index).item;
????}
在?上面的代碼中調(diào)用了通過(guò)索引位置查找節(jié)點(diǎn)位置的函數(shù)，下面我們來(lái)分析一下這個(gè)函數(shù),由于底層是鏈表實(shí)現(xiàn)的，所以呢？遍歷起來(lái)不是很方便，就考慮到位運(yùn)算，如果索引位置在后面一半，就從后往前遍歷查找，否則從前往后遍歷。
????Node?node(int?index)? {
????????//?assert?isElementIndex(index);
????//?size>>1?表示除以2，相當(dāng)于index小于size的一半
????????if?(index?>?1))?{
???????????//?從前面開始遍歷，取出first節(jié)點(diǎn)，因?yàn)橹虚g過(guò)程引用會(huì)變化，所以不可直接操作first
????????????Node?x?=?first;
???????????//?通過(guò)循環(huán)計(jì)數(shù)來(lái)查找
????????????for?(int?i?=?0;?i?????????????????x?=?x.next;
????????????return?x;
????????}?else?{
???????????//?取出最后一個(gè)元素
????????????Node?x?=?last;
???????????//?從后往前遍歷
????????????for?(int?i?=?size?-?1;?i?>?index;?i--)
????????????????x?=?x.prev;
????????????return?x;
????????}
????}
4.1.4 indexOf(Object o)
查找某一個(gè)元素的索引位置,分為兩種情況討論，如果要查找的元素為空，那么就使用==，否則使用equals()，這也從側(cè)面印證了LinedList實(shí)際上是可以存儲(chǔ)null元素的。使用計(jì)數(shù)查找：
????public?int?indexOf(Object?o)?{
????????int?index?=?0;
???????//?如果需要查找null元素
????????if?(o?==?null)?{
????????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????????if?(x.item?==?null)
????????????????????return?index;
????????????????index++;
????????????}
????????}?else?{
???????????//?查找元素不為空
????????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????????if?(o.equals(x.item))
????????????????????return?index;
????????????????index++;
????????????}
????????}
????????return?-1;
????}
4.1.5 lastIndexOf(Object o)
和前面的indexOf差不多，區(qū)別就是這個(gè)是后面開始查找，找到第一個(gè)符合的元素。
????public?int?indexOf(Object?o)?{
????????int?index?=?0;
???????//?查找元素
????????if?(o?==?null)?{
????????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????????if?(x.item?==?null)
????????????????????return?index;
????????????????index++;
????????????}
????????}?else?{
????????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????????if?(o.equals(x.item))
????????????????????return?index;
????????????????index++;
????????????}
????????}
????????return?-1;
????}
4.2 添加元素
4.2.1 addFirst(E e)
將元素e，添加到第一個(gè)節(jié)點(diǎn)，公有方法是addFirst()，但是其實(shí)內(nèi)部調(diào)用是linkFirst()，這是private方法。
????public?void?addFirst(E?e)?{
????????linkFirst(e);
????}
????private?void?linkFirst(E?e)?{
????????//?先保存第一個(gè)節(jié)點(diǎn)
????????final?Node?f?=?first;
????????//?初始化一個(gè)新節(jié)點(diǎn)，prev是null，next是f（之前的首節(jié)點(diǎn)）
????????final?Node?newNode?=?new?Node<>(null,?e,?f);
????????//?更新first為新節(jié)點(diǎn)
????????first?=?newNode;
????????//?如果之前的第一個(gè)節(jié)點(diǎn)是空的，那么就說(shuō)明里面是空的，沒有元素
????????if?(f?==?null)
????????????//?最后一個(gè)元素也是新加入的元素
????????????last?=?newNode;
????????else
????????????//?f的prev前置節(jié)點(diǎn)的引用更新為新的節(jié)點(diǎn)
????????????f.prev?=?newNode;
????????//?個(gè)數(shù)增加
????????size++;
????????//?修改次數(shù)增加
????????modCount++;
????}
4.2.2 addLast(E e)
將元素添加在鏈表最后，其實(shí)內(nèi)部也是直接調(diào)用的private方法linkLast():
????public?void?addLast(E?e)?{
????????linkLast(e);
????}
????void?linkLast(E?e)?{
????????//?保存最后一個(gè)節(jié)點(diǎn)的引用
????????final?Node?l?=?last;
????????//?初始化一個(gè)節(jié)點(diǎn)，前置節(jié)點(diǎn)指針引用指向之前的最后一個(gè)節(jié)點(diǎn)，后續(xù)節(jié)點(diǎn)的引用是null
????????final?Node?newNode?=?new?Node<>(l,?e,?null);
????????//?將最后一個(gè)節(jié)點(diǎn)更新
????????last?=?newNode;
????????//?如果之前的最后一個(gè)節(jié)點(diǎn)是null，說(shuō)明鏈表是空的
????????if?(l?==?null)
????????????//?新節(jié)點(diǎn)同時(shí)是第一個(gè)節(jié)點(diǎn)
????????????first?=?newNode;
????????else
????????????//?否則之前的最后一個(gè)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)引用更新為新的節(jié)點(diǎn)
????????????l.next?=?newNode;
????????//?大小+1
????????size++;
????????//?修改次數(shù)+1
????????modCount++;
????}
4.2.3 add(E e)
增加元素，默認(rèn)也是在鏈表的最后添加，完成返回true：
????public?boolean?add(E?e)?{
????????linkLast(e);
????????return?true;
????}
4.2.4 addAll(Collection c)
往鏈表里面批量添加元素,里面默認(rèn)是在最后面批量添加，內(nèi)部調(diào)用的是addAll(int index, Collection c),添加之前會(huì)判斷索引位置是不是合法的。然后查找需要插入的位置的前后節(jié)點(diǎn)，循環(huán)插入。
????public?boolean?addAll(Collection?c)?{
????????return?addAll(size,?c);
????}
????public?boolean?addAll(int?index,?Collection?c)?{
????????//?檢查添加位置
????????checkPositionIndex(index);
????????//?將需要添加的集合轉(zhuǎn)換成為數(shù)組
????????Object[]?a?=?c.toArray();
????????//?獲取數(shù)組的大小
????????int?numNew?=?a.length;
????????//?如果數(shù)組長(zhǎng)度為0，說(shuō)明沒有需要添加的元素，返回false
????????if?(numNew?==?0)
????????????return?false;
????????//?插入位置的前節(jié)點(diǎn)和后續(xù)節(jié)點(diǎn)
????????Node?pred,?succ;
????????//?如果插入位置索引大小等于鏈表大小，那么就是在最后插入元素
????????if?(index?==?size)?{
????????????//?最后插入元素沒有后續(xù)節(jié)點(diǎn)
????????????succ?=?null;
????????????//?前一個(gè)節(jié)點(diǎn)就是之前的最后一個(gè)節(jié)點(diǎn)
????????????pred?=?last;
????????}?else?{
????????????//?查找到索引為index?的節(jié)點(diǎn)
????????????succ?=?node(index);
????????????//?獲取前一個(gè)節(jié)點(diǎn)
????????????pred?=?succ.prev;
????????}
????????
????????//?循環(huán)插入節(jié)點(diǎn)
????????for?(Object?o?:?a)?{
????????????@SuppressWarnings("unchecked")?E?e?=?(E)?o;
????????????//?初始化新節(jié)點(diǎn)，上一個(gè)節(jié)點(diǎn)是pred
????????????Node?newNode?=?new?Node<>(pred,?e,?null);
????????????//?如果前一個(gè)節(jié)點(diǎn)是null，那么第一個(gè)節(jié)點(diǎn)就是新的節(jié)點(diǎn)
????????????if?(pred?==?null)
????????????????first?=?newNode;
????????????else
????????????????//?否則pred的next置為新節(jié)點(diǎn)
????????????????pred.next?=?newNode;
????????????pred?=?newNode;
????????}
????????//?如果插入位置沒有后續(xù)節(jié)點(diǎn)，也就是succ為null
????????if?(succ?==?null)?{
????????????//?最后一個(gè)節(jié)點(diǎn)也就是pred，剛剛插入的新節(jié)點(diǎn)
????????????last?=?pred;
????????}?else?{
????????????//?加入所有元素之后的最后一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向succ（后續(xù)元素）
????????????pred.next?=?succ;
????????????//?插入位置的后續(xù)元素的上一個(gè)節(jié)點(diǎn)引用指向pred
????????????succ.prev?=?pred;
????????}
???????//?大小改變
????????size?+=?numNew;
???????//?修改次數(shù)增加
????????modCount++;
????????return?true;
????}
上面的代碼調(diào)用了node(index)，這個(gè)在前面查找的時(shí)候已經(jīng)說(shuō)過(guò)了，不再解釋。
4.2.5 addAll(int index, Collection c)
在指定位置批量插入節(jié)點(diǎn)：
????public?boolean?addAll(int?index,?Collection?c)?{
???????//?檢查索引合法性
????????checkPositionIndex(index);
???????//?將需要插入的集合轉(zhuǎn)換成為數(shù)組
????????Object[]?a?=?c.toArray();
???????//?數(shù)組的長(zhǎng)度
????????int?numNew?=?a.length;
???????//?為0則不需要插入
????????if?(numNew?==?0)
????????????return?false;
???????//?插入位置的前節(jié)點(diǎn)和后節(jié)點(diǎn)
????????Node?pred,?succ;
???????//?如果在最后插入
????????if?(index?==?size)?{
???????????//?后節(jié)點(diǎn)為空
????????????succ?=?null;
???????????//?前節(jié)點(diǎn)是最后一個(gè)
????????????pred?=?last;
????????}?else?{
???????????//?獲取插入位置的后節(jié)點(diǎn)
????????????succ?=?node(index);
???????????//?獲取前節(jié)點(diǎn)
????????????pred?=?succ.prev;
????????}
????
???????//?遍歷
????????for?(Object?o?:?a)?{
????????????@SuppressWarnings("unchecked")?E?e?=?(E)?o;
???????????//?初始化節(jié)點(diǎn)，前置節(jié)點(diǎn)是插入位置的前節(jié)點(diǎn)，后續(xù)節(jié)點(diǎn)為null
????????????Node?newNode?=?new?Node<>(pred,?e,?null);
???????????//?如果插入位置前一個(gè)節(jié)點(diǎn)是null，說(shuō)明插入位置是鏈表首
????????????if?(pred?==?null)
???????????????//?首節(jié)點(diǎn)就是新插入的節(jié)點(diǎn)
????????????????first?=?newNode;
????????????else
???????????????//?前節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
????????????????pred.next?=?newNode;
???????????//?更新插入位置的前一個(gè)節(jié)點(diǎn)
????????????pred?=?newNode;
????????}
???????//?如果插入位置的后一個(gè)節(jié)點(diǎn)為空，說(shuō)明插入位置是鏈表尾部
????????if?(succ?==?null)?{
???????????//?最后一個(gè)元素就是插入的元素
????????????last?=?pred;
????????}?else?{
???????????//?將插入的最后一個(gè)元素next指向succ
????????????pred.next?=?succ;
???????????//?succ的上一個(gè)元素指向prev
????????????succ.prev?=?pred;
????????}
???????//?大小更新
????????size?+=?numNew;
???????//?修改次數(shù)改變
????????modCount++;
???????//?返回成功
????????return?true;
????}
4.2.6 add(int index,E element)
將元素插入在指定位置,先判斷索引位置，如果索引位置是最后一個(gè)，那么直接調(diào)用在最后添加元素函數(shù)即可，否則需要調(diào)用另外一個(gè)函數(shù)，在某個(gè)元素前面插入：
????public?void?add(int?index,?E?element)?{
???????//?index校驗(yàn)
????????checkPositionIndex(index);
???????
???????//?索引等于鏈表大小
????????if?(index?==?size)
???????????//?直接在最后插入元素
????????????linkLast(element);
????????else
???????????//?在某個(gè)節(jié)點(diǎn)前插入元素
????????????linkBefore(element,?node(index));
????}
4.3 刪除元素
4.3.1 removeFirst()
刪除第一個(gè)節(jié)點(diǎn)，先獲取首節(jié)點(diǎn)，判斷第一個(gè)節(jié)點(diǎn)是不是為空，如果為空則證明沒有該節(jié)點(diǎn)，拋出異常，內(nèi)部調(diào)用的其實(shí)是unlinkFirst()。返回值是被移除的節(jié)點(diǎn)里面的數(shù)值。
????public?E?removeFirst()?{
????????final?Node?f?=?first;
????????if?(f?==?null)
????????????throw?new?NoSuchElementException();
????????return?unlinkFirst(f);
????}
??//?移除首節(jié)點(diǎn)
????private?E?unlinkFirst(Node?f) ?{
????????//?assert?f?==?first?&&?f?!=?null;
???????//?獲取里面的元素
????????final?E?element?=?f.item;
???????//?保存下一個(gè)節(jié)點(diǎn)
????????final?Node?next?=?f.next;
???????//?將之前的首節(jié)點(diǎn)前后節(jié)點(diǎn)引用置空，有利于GC
????????f.item?=?null;
????????f.next?=?null;?//?help?GC
???????//?首節(jié)點(diǎn)更新
????????first?=?next;
???????//?如果首節(jié)點(diǎn)是空的，那么鏈表沒有元素了，最后一個(gè)節(jié)點(diǎn)自然也是null
????????if?(next?==?null)
????????????last?=?null;
????????else
???????????//?否則當(dāng)前的第一個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)置null
????????????next.prev?=?null;
???????//?鏈表大小-1
????????size--;
???????//?修改次數(shù)增加
????????modCount++;
????????return?element;
????}
4.3.2 removeLast()
刪除最后一個(gè)節(jié)點(diǎn)，和上面的刪除首節(jié)點(diǎn)差不多，先取出最后一個(gè)節(jié)點(diǎn)，判斷是否為空，如果為空則拋出異常，否則會(huì)調(diào)用另一個(gè)解除連接的函數(shù)unLinkLast()。
????public?E?removeLast()?{
????????final?Node?l?=?last;
????????if?(l?==?null)
????????????throw?new?NoSuchElementException();
????????return?unlinkLast(l);
????}
????private?E?unlinkLast(Node?l) ?{
????????//?assert?l?==?last?&&?l?!=?null;
???????//?保存被移除的節(jié)點(diǎn)的item
????????final?E?element?=?l.item;
???????//?獲取上一個(gè)節(jié)點(diǎn)
????????final?Node?prev?=?l.prev;
???????//?前后引用置空，有利于垃圾回收
????????l.item?=?null;
????????l.prev?=?null;?//?help?GC
???????//?更新最后一個(gè)節(jié)點(diǎn)
????????last?=?prev;
???????//?如果前置節(jié)點(diǎn)為空，那么鏈表已經(jīng)沒有元素了
????????if?(prev?==?null)
????????????first?=?null;
????????else
???????????//?否則將上一個(gè)節(jié)點(diǎn)的next置null
????????????prev.next?=?null;
???????//?大小該表
????????size--;
???????//?修改次數(shù)增加
????????modCount++;
???????//?返回被移除的節(jié)點(diǎn)的item值
????????return?element;
????}
4.3.3 remove(Object o)
刪除某個(gè)元素分為兩種情況，元素為null和非null,直接遍歷判斷，里面真正刪除的方法其實(shí)是unlink(E e)，成功移除則返回true，注意這里只會(huì)移除掉第一個(gè)，后續(xù)要是還有該節(jié)點(diǎn)，不會(huì)移除。
????public?boolean?remove(Object?o)?{
???????//?元素為null
????????if?(o?==?null)?{
????????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????????if?(x.item?==?null)?{
????????????????????unlink(x);
????????????????????return?true;
????????????????}
????????????}
????????}?else?{
???????????//?元素不為null
????????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)?{
????????????????if?(o.equals(x.item))?{
???????????????????//?移除節(jié)點(diǎn)
????????????????????unlink(x);
????????????????????return?true;
????????????????}
????????????}
????????}
????????return?false;
????}
unLink(E e)方法如下：
????E?unlink(Node?x) ?{
????????//?assert?x?!=?null;
???????//?保存被移除節(jié)點(diǎn)的item
????????final?E?element?=?x.item;
???????//?下一個(gè)節(jié)點(diǎn)
????????final?Node?next?=?x.next;
???????//?上一個(gè)節(jié)點(diǎn)
????????final?Node?prev?=?x.prev;
???????//?如果前置節(jié)點(diǎn)為空，那么首節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)了
????????if?(prev?==?null)?{
????????????first?=?next;
????????}?else?{
???????????//?前一個(gè)節(jié)點(diǎn)的next置為下一個(gè)節(jié)點(diǎn)
????????????prev.next?=?next;
???????????//?之前的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)置null
????????????x.prev?=?null;
????????}
???????//?如果next是空的，那么上一個(gè)節(jié)點(diǎn)就是現(xiàn)在最后一個(gè)節(jié)點(diǎn)
????????if?(next?==?null)?{
????????????last?=?prev;
????????}?else?{
???????????//?next的上一個(gè)節(jié)點(diǎn)引用指向prev
????????????next.prev?=?prev;
???????????//?被刪除的元素的next置空
????????????x.next?=?null;
????????}
???????//?item置空
????????x.item?=?null;
???????//?大小改變
????????size--;
???????//?修改次數(shù)增加
????????modCount++;
???????//?返回被刪除的節(jié)點(diǎn)里面的item
????????return?element;
????}
4.3.4 clear()
移除里面所有的元素：
????public?void?clear()?{
????????//?Clearing?all?of?the?links?between?nodes?is?"unnecessary",?but:
????????//?-?helps?a?generational?GC?if?the?discarded?nodes?inhabit
????????//???more?than?one?generation
????????//?-?is?sure?to?free?memory?even?if?there?is?a?reachable?Iterator
????????for?(Node?x?=?first;?x?!=?null;?)?{
???????????//?保存下一個(gè)
????????????Node?next?=?x.next;
???????????//?當(dāng)前元素置空
????????????x.item?=?null;
????????????x.next?=?null;
????????????x.prev?=?null;
????????????x?=?next;
????????}
???????//?首節(jié)點(diǎn)和尾節(jié)點(diǎn)全部置null
????????first?=?last?=?null;
????????size?=?0;
????????modCount++;
????}
4.3.5 remove（int index）
移除指定索引的元素。先通過(guò)索引找到節(jié)點(diǎn)，再移除指定的節(jié)點(diǎn)
????public?E?remove(int?index)?{
???????//?檢查合法性
????????checkElementIndex(index);
???????//?先找到節(jié)點(diǎn)，再移除指定節(jié)點(diǎn)
????????return?unlink(node(index));
????}
4.4 更新元素
4.4.1 set(int index,E element)
更新指定索引的位置的元素,首先通過(guò)索引查找到該元素，然后修改item值，返回舊的item值。
????public?E?set(int?index,?E?element)?{
???????//?檢查索引是否合法
????????checkElementIndex(index);
???????//?通過(guò)索引查找到節(jié)點(diǎn)
????????Node?x?=?node(index);
???????//?保存舊的值
????????E?oldVal?=?x.item;
???????//?修改
????????x.item?=?element;
???????//?返回舊的元素
????????return?oldVal;
????}
5 queue相關(guān)的方法
因?yàn)?code style="font-size: 14px;overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(30, 107, 184);background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;">LinkedList也實(shí)現(xiàn)了queue接口，所以它肯定也實(shí)現(xiàn)了相關(guān)的方法，下面我們看看：
5.1 peek()
獲取隊(duì)列第一個(gè)元素：
????public?E?peek()?{
???????//?拿到第一個(gè)元素，final不可變
????????final?Node?f?=?first;
???????//?返回item值
????????return?(f?==?null)???null?:?f.item;
????}
5.2 element()
也是獲取隊(duì)列第一個(gè)元素，里面調(diào)用的是getFirst()。
????public?E?element()?{
????????return?getFirst();
????}
5.3 poll()
移除隊(duì)列第一個(gè)節(jié)點(diǎn)元素并返回，里面調(diào)用的其實(shí)是unlinkFirst()
????public?E?poll()?{
???????//?獲取到第一個(gè)元素
????????final?Node?f?=?first;
???????//?移除并返回
????????return?(f?==?null)???null?:?unlinkFirst(f);
????}
5.4 remove()
移除隊(duì)列第一個(gè)元素,里面調(diào)用的是removeFirst():
????public?E?remove()?{
????????return?removeFirst();
????}
5.5 offfer(E e)
在隊(duì)列后面增加元素：
????public?boolean?offer(E?e)?{
????????return?add(e);
????}
5.6 offerFirst(E e)
往隊(duì)列的前面插入元素，其實(shí)調(diào)用的是addFirst()
????public?boolean?offerFirst(E?e)?{
????????addFirst(e);
????????return?true;
????}
5.7 offerLast(E e)
往隊(duì)列的后面添加元素,其實(shí)調(diào)用的是addList()
????public?boolean?offerLast(E?e)?{
????????addLast(e);
????????return?true;
????}
5.8 peekFirst()
獲取第一個(gè)節(jié)點(diǎn)里面的元素:
????public?E?peekFirst()?{
????????final?Node?f?=?first;
????????return?(f?==?null)???null?:?f.item;
?????}
5.9 peekLast()
獲取最后一個(gè)節(jié)點(diǎn)的元素：
????public?E?peekLast()?{
????????final?Node?l?=?last;
????????return?(l?==?null)???null?:?l.item;
????}
5.10 pollFirst()
獲取第一個(gè)元素，并且移除它,使用的是unlinkFirst(E e)
????public?E?pollFirst()?{
????????final?Node?f?=?first;
????????return?(f?==?null)???null?:?unlinkFirst(f);
????}
5.11 pollLast（）
獲取隊(duì)列最后一個(gè)元素，并且移除它,調(diào)用的其實(shí)是unlinkLast(E e)
????public?E?pollLast()?{
????????final?Node?l?=?last;
????????return?(l?==?null)???null?:?unlinkLast(l);
????}
5.12 push(E e)
像是堆棧的特點(diǎn)，在前面添加元素：
????public?void?push(E?e)?{
????????addFirst(e);
????}
5.13 pop()
堆棧的特點(diǎn)，取出隊(duì)列首的第一個(gè)元素
????public?E?pop()?{
????????return?removeFirst();
????}
5.14 removeFirstOccurrence(Object o)
移除元素,從前往后第一次出現(xiàn)的地方移除掉：
????public?boolean?removeFirstOccurrence(Object?o)?{
????????return?remove(o);
????}
5.15 removeLastOccurrence（Object o）
移除元素，最后一次出現(xiàn)的地方移除掉,和前面分析的一樣，分為兩種情況，null和非null。
????public?boolean?removeLastOccurrence(Object?o)?{
???????//?元素為null
????????if?(o?==?null)?{
????????????for?(Node?x?=?last;?x?!=?null;?x?=?x.prev)?{
????????????????if?(x.item?==?null)?{
????????????????????unlink(x);
????????????????????return?true;
????????????????}
????????????}
????????}?else?{
???????????//?元素不是null
????????????for?(Node?x?=?last;?x?!=?null;?x?=?x.prev)?{
????????????????if?(o.equals(x.item))?{
????????????????????unlink(x);
????????????????????return?true;
????????????????}
????????????}
????????}
????????return?false;
????}
6.其他方法
是否包含某個(gè)元素,其實(shí)調(diào)用的是indexOf()方法，如果返回的索引不為-1，則包含：
????public?boolean?contains(Object?o)?{
????????return?indexOf(o)?!=?-1;
????}
返回大小：
????public?int?size()?{
????????return?size;
????}
是否為有效元素下標(biāo)索引，從0到size-1
????private?boolean?isElementIndex(int?index)?{
????????return?index?>=?0?&&?index?????}
是否為有效位置索引，從0到size
????private?boolean?isPositionIndex(int?index)?{
????????return?index?>=?0?&&?index?<=?size;
????}
獲取指定索引位置的ListIterator:
????public?ListIterator?listIterator(int?index)? {
???????//?檢查合法性
????????checkPositionIndex(index);
????????return?new?ListItr(index);
????}
獲取倒序的迭代器:
????public?Iterator?descendingIterator()? {
????????return?new?DescendingIterator();
????}
拷貝克隆函數(shù),一個(gè)是父類的克隆函數(shù)，另一個(gè)是重寫的克隆函數(shù)，這里比較特殊，因?yàn)?code style="font-size: 14px;overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(30, 107, 184);background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;">LinkedList是鏈表，本身只保存了第一個(gè)和最后一個(gè)的引用，所以拷貝的時(shí)候需要向里面添加元素的方式進(jìn)行拷貝。
????public?Object?clone()?{
????????LinkedList?clone?=?superClone();
????????//?Put?clone?into?"virgin"?state
????????clone.first?=?clone.last?=?null;
????????clone.size?=?0;
????????clone.modCount?=?0;
????????//?添加元素到拷貝的隊(duì)列中
????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)
????????????clone.add(x.item);
????????return?clone;
????}
????private?LinkedList?superClone()? {
????????try?{
????????????return?(LinkedList)?super.clone();
????????}?catch?(CloneNotSupportedException?e)?{
????????????throw?new?InternalError(e);
????????}
????}
轉(zhuǎn)換成為數(shù)組，通過(guò)循環(huán)實(shí)現(xiàn)
????public?Object[]?toArray()?{
????????Object[]?result?=?new?Object[size];
????????int?i?=?0;
???????//?循環(huán)實(shí)現(xiàn)
????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)
????????????result[i++]?=?x.item;
????????return?result;
????}
轉(zhuǎn)換成為指定類型的數(shù)組,和前面不同的是，這里初始化的時(shí)候使用類型反射創(chuàng)建(T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size)
????public??T[]?toArray(T[]?a)?{
????????if?(a.length?????????????a?=?(T[])java.lang.reflect.Array.newInstance(
????????????????????????????????a.getClass().getComponentType(),?size);
????????int?i?=?0;
????????Object[]?result?=?a;
????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)
????????????result[i++]?=?x.item;
????????if?(a.length?>?size)
????????????a[size]?=?null;
????????return?a;
????}
獲取可分割迭代器：
????public?Spliterator?spliterator()? {
????????return?new?LLSpliterator(this,?-1,?0);
????}
7.迭代器
里面定義了三種迭代器，都是以內(nèi)部類的方式實(shí)現(xiàn)，分別是：
ListItr：列表的經(jīng)典迭代器 DescendingIterator：倒序迭代器 LLSpliterator：可分割迭代器
7.1 ListItr
先來(lái)說(shuō)說(shuō)ListItr，這個(gè)迭代器主要是有next(),hashNext(),hasPrevious(),previous(),nextIndex(),previousIndex(),remove(),set(),add(),forEachRemaining()方法：
next()：獲取下一個(gè)元素hashNext():是否有下一個(gè)元素hasPrevious()：是否有上一個(gè)元素previous()：上一個(gè)元素nextIndex()：下一個(gè)索引位置previousIndex()：上一個(gè)索引位置remove()：刪除當(dāng)前索引位置的元素set()：更新元素add()：新增元素forEachRemaining()：遍歷剩下的元素
里面主要有集合重要的屬性：
lastReturned:上一次返回的元素next：下一個(gè)返回的元素nextIndex：下一個(gè)索引expectedModCount：期待修改的次數(shù)
????private?class?ListItr?implements?ListIterator<E>?{
???????//?上一個(gè)返回的元素
????????private?Node?lastReturned;
???????//?下一個(gè)元素
????????private?Node?next;
???????//?下一個(gè)索引
????????private?int?nextIndex;
???????//?期待的修改次數(shù)
????????private?int?expectedModCount?=?modCount;
???????
???????//?初始化
????????ListItr(int?index)?{
????????????//?根據(jù)索引位置更新下一個(gè)返回的節(jié)點(diǎn)
????????????next?=?(index?==?size)???null?:?node(index);
???????????//?更新索引
????????????nextIndex?=?index;
????????}
???????//?是否有下一個(gè)元素：索引是否小于size
????????public?boolean?hasNext()?{
????????????return?nextIndex?????????}
???????//?獲取下一個(gè)元素
????????public?E?next()?{
???????????//?檢查修改合法化
????????????checkForComodification();
???????????//?如果沒有下一個(gè)元素會(huì)拋異常，所以使用前需要先判斷
????????????if?(!hasNext())
????????????????throw?new?NoSuchElementException();
???????????//?上一次返回的元素更新
????????????lastReturned?=?next;
???????????//?更新下一次返回的元素
????????????next?=?next.next;
???????????//?更新索引
????????????nextIndex++;
???????????//?返回item
????????????return?lastReturned.item;
????????}
??????
???????//?是否有上一個(gè)：下一個(gè)返回的元素索引是不是大于0
????????public?boolean?hasPrevious()?{
????????????return?nextIndex?>?0;
????????}
???????//?返回上一個(gè)元素
????????public?E?previous()?{
???????????//?檢查
????????????checkForComodification();
???????????//?判斷是否有上一個(gè)元素??
???????????if?(!hasPrevious())
????????????????throw?new?NoSuchElementException();
???????????//?上一個(gè)返回的元素，需要更新
????????????lastReturned?=?next?=?(next?==?null)???last?:?next.prev;
????????????//?更新索引
???????????nextIndex--;
????????????return?lastReturned.item;
????????}
???????//?下一個(gè)索引
????????public?int?nextIndex()?{
????????????return?nextIndex;
????????}
???????//?上一個(gè)索引
????????public?int?previousIndex()?{
????????????return?nextIndex?-?1;
????????}
?
???????//?移除當(dāng)前位置的索引
????????public?void?remove()?{
???????????//?檢查修改合法性
????????????checkForComodification();
????????????if?(lastReturned?==?null)
????????????????throw?new?IllegalStateException();
??????//?獲取下一個(gè)元素
????????????Node?lastNext?=?lastReturned.next;
???????????//?移除上一個(gè)返回的元素
????????????unlink(lastReturned);
???????????//?如果下一個(gè)是上次返回的元素，那么下一個(gè)元素需要更新，因?yàn)樵撛匾呀?jīng)被移除了
????????????if?(next?==?lastReturned)
????????????????next?=?lastNext;
????????????else
???????????????//?更新索引
????????????????nextIndex--;
????????????lastReturned?=?null;
????????????expectedModCount++;
????????}
???????//?更新
????????public?void?set(E?e)?{
????????????if?(lastReturned?==?null)
????????????????throw?new?IllegalStateException();
????????????checkForComodification();
????????????lastReturned.item?=?e;
????????}
????????public?void?add(E?e)?{
????????????checkForComodification();
????????????lastReturned?=?null;
???????????//?如果下一個(gè)元素是空，那就是在隊(duì)尾添加元素
????????????if?(next?==?null)
????????????????linkLast(e);
????????????else
???????????????//?否則就是在next索引處添加元素
????????????????linkBefore(e,?next);
???????????//?更新索引
????????????nextIndex++;
????????????expectedModCount++;
????????}
????
???????//?遍歷剩下的元素
????????public?void?forEachRemaining(Consumersuper?E>?action)?{
????????????Objects.requireNonNull(action);
???????????//?使用循環(huán)，索引不斷后移，遍歷
????????????while?(modCount?==?expectedModCount?&&?nextIndex????????????????//?對(duì)每個(gè)節(jié)點(diǎn)元素執(zhí)行操作
????????????????action.accept(next.item);
????????????????lastReturned?=?next;
????????????????next?=?next.next;
????????????????nextIndex++;
????????????}
????????????checkForComodification();
????????}
????????final?void?checkForComodification()?{
????????????if?(modCount?!=?expectedModCount)
????????????????throw?new?ConcurrentModificationException();
????????}
????}
上面的迭代器沒有什么好說(shuō)的，就是往前面和后面遍歷的功能，以及增刪改的功能。
7.2 DescendingIterator
這個(gè)迭代器有點(diǎn)意思，也很簡(jiǎn)單，就是一個(gè)倒序的功能，功能實(shí)現(xiàn)也十分簡(jiǎn)單：
hasNext:是否有下一個(gè)元素，實(shí)際上是判斷上一個(gè)元素 next：獲取下一個(gè)元素，實(shí)際上是獲取前面一個(gè)元素 remove：移除元素
倒序就是別人從前往后，它偏偏從后往前遍歷，emmmmmmm
????private?class?DescendingIterator?implements?Iterator<E>?{
????????private?final?ListItr?itr?=?new?ListItr(size());
????????public?boolean?hasNext()?{
????????????return?itr.hasPrevious();
????????}
????????public?E?next()?{
????????????return?itr.previous();
????????}
????????public?void?remove()?{
????????????itr.remove();
????????}
????}
7.3 LLSpliterator
這個(gè)迭代器有點(diǎn)東西，感覺和其它的不太一樣，LLSpliterator是在使用node的next進(jìn)行迭代，下面分析一下：主要是為了將元素分為多份，然后再用多線程來(lái)處理。
值得注意的是：分割的時(shí)候，LinkedList不是1/2分割，而是每一次分割出來(lái)的大小都是遞增的，遞增的大小是BATCH_UNIT,但是返回的不是LLSpliterator，而是ArraySpliterator，每次都分割出更多的元素，轉(zhuǎn)成數(shù)組結(jié)構(gòu)，這也許是出自于性能考慮，比較指針遍歷太慢了，我猜的的...別打我
????static?final?class?LLSpliterator<E>?implements?Spliterator<E>?{
???????//?分割長(zhǎng)度增加單位
????????static?final?int?BATCH_UNIT?=?1?<10;??//?batch?array?size?increment
???????//?最大分割長(zhǎng)度
????????static?final?int?MAX_BATCH?=?1?<25;??//?max?batch?array?size;
????????final?LinkedList?list;?//?null?OK?unless?traversed
???????//?當(dāng)前節(jié)點(diǎn)
????????Node?current;??????//?current?node;?null?until?initialized
???????//?大小估算
????????int?est;??
???????//?期待修改的次數(shù)
????????int?expectedModCount;?//?initialized?when?est?set
???????//?分割長(zhǎng)度
????????int?batch;????????????//?batch?size?for?splits
????????LLSpliterator(LinkedList?list,?int?est,?int?expectedModCount)?{
????????????this.list?=?list;
????????????this.est?=?est;
????????????this.expectedModCount?=?expectedModCount;
????????}
????????final?int?getEst()?{
????????????int?s;?//?force?initialization
????????????final?LinkedList?lst;
????????????if?((s?=?est)?0)?{
????????????????if?((lst?=?list)?==?null)
????????????????????s?=?est?=?0;
????????????????else?{
????????????????????expectedModCount?=?lst.modCount;
????????????????????current?=?lst.first;
????????????????????s?=?est?=?lst.size;
????????????????}
????????????}
????????????return?s;
????????}
????//?估算大小
????????public?long?estimateSize()?{?return?(long)?getEst();?}
???????//?分割
????????public?Spliterator?trySplit()? {
????????????Node?p;
???????????//?獲取大小
????????????int?s?=?getEst();
???????????//?當(dāng)前節(jié)點(diǎn)不為空
????????????if?(s?>?1?&&?(p?=?current)?!=?null)?{
???????????????//?分割位置結(jié)束：分割位置+分割單位
????????????????int?n?=?batch?+?BATCH_UNIT;
???????????????//?如果大于大小，就限制最后的位置
????????????????if?(n?>?s)
????????????????????n?=?s;
???????????????//?最大的分割位置
????????????????if?(n?>?MAX_BATCH)
????????????????????n?=?MAX_BATCH;
???????????????//?數(shù)組
????????????????Object[]?a?=?new?Object[n];
????????????????int?j?=?0;
???????????????//?將當(dāng)前位置到n的位置循環(huán)，存放到a數(shù)組中
????????????????do?{?a[j++]?=?p.item;?}?while?((p?=?p.next)?!=?null?&&?j?????????????????current?=?p;
????????????????batch?=?j;
????????????????est?=?s?-?j;
???????????????//?ArraySpliterator每次分割成一半一半，而IteratorSpliterator算術(shù)遞增
????????????????return?Spliterators.spliterator(a,?0,?j,?Spliterator.ORDERED);
????????????}
????????????return?null;
????????}
???????//?對(duì)剩下的元素進(jìn)行處理
????????public?void?forEachRemaining(Consumersuper?E>?action)?{
????????????Node?p;?int?n;
????????????if?(action?==?null)?throw?new?NullPointerException();
????????????if?((n?=?getEst())?>?0?&&?(p?=?current)?!=?null)?{
????????????????current?=?null;
????????????????est?=?0;
????????????????do?{
????????????????????E?e?=?p.item;
????????????????????p?=?p.next;
????????????????????action.accept(e);
????????????????}?while?(p?!=?null?&&?--n?>?0);
????????????}
????????????if?(list.modCount?!=?expectedModCount)
????????????????throw?new?ConcurrentModificationException();
????????}
???????//?對(duì)后面一個(gè)元素進(jìn)行處理
????????public?boolean?tryAdvance(Consumersuper?E>?action)?{
????????????Node?p;
????????????if?(action?==?null)?throw?new?NullPointerException();
????????????if?(getEst()?>?0?&&?(p?=?current)?!=?null)?{
????????????????--est;
????????????????E?e?=?p.item;
????????????????current?=?p.next;
????????????????action.accept(e);
????????????????if?(list.modCount?!=?expectedModCount)
????????????????????throw?new?ConcurrentModificationException();
????????????????return?true;
????????????}
????????????return?false;
????????}
????????public?int?characteristics()?{
????????????return?Spliterator.ORDERED?|?Spliterator.SIZED?|?Spliterator.SUBSIZED;
????????}
????}
8.序列化和反序列化
序列化和反序列化的時(shí)候，需要重寫，因?yàn)槲覀儽４娴闹挥械谝粋€(gè)和最后一個(gè)節(jié)點(diǎn)的引用，我們序列化需要保存大小和引用，所以需要重寫，要不反序列化回來(lái)就找不到next，節(jié)點(diǎn)之間的關(guān)系就會(huì)丟失。
序列化的時(shí)候如下，寫入了size，以及遍歷的時(shí)候?qū)⒐?jié)點(diǎn)的item值寫入。
????private?void?writeObject(java.io.ObjectOutputStream?s)
????????throws?java.io.IOException?{
????????//?Write?out?any?hidden?serialization?magic
????????s.defaultWriteObject();
????????//?Write?out?size
????????s.writeInt(size);
????????//?Write?out?all?elements?in?the?proper?order.
????????for?(Node?x?=?first;?x?!=?null;?x?=?x.next)
????????????s.writeObject(x.item);
????}
反序列化的時(shí)候，讀入大小size以及每個(gè)節(jié)點(diǎn)里面的元素item
????private?void?readObject(java.io.ObjectInputStream?s)
????????throws?java.io.IOException,?ClassNotFoundException?{
????????//?默認(rèn)序列化
????????s.defaultReadObject();
????????//?大小
????????int?size?=?s.readInt();
????????//?按照順序讀入元素
????????for?(int?i?=?0;?i?????????????linkLast((E)s.readObject());
????}
9.總結(jié)一下
LinkedList底層是用鏈表實(shí)現(xiàn)的，而且是雙向鏈表，并且實(shí)現(xiàn)了Queue接口，可以當(dāng)成雙向隊(duì)列或者堆棧來(lái)使用。也正是因?yàn)槭擎湵韺?shí)現(xiàn)，所以刪除元素比較快，但是查找的時(shí)候相對(duì)較慢。當(dāng)然，也沒有什么擴(kuò)容，除非就是內(nèi)存不夠了。雙向鏈表，可以從頭往尾遍歷，也可以從尾部往前遍歷。 LinkedList繼承了AbstractSequentialList，AbstractSequentialList實(shí)現(xiàn)了get,set,add,remove等方法。序列化/反序列化的時(shí)候重寫了方法，才能達(dá)到序列化里面每一個(gè)節(jié)點(diǎn)元素的效果。 線程不安全
評(píng)論
圖片
表情