前言
前面一篇我們分析了ArrayList的源碼奉件，這一篇分享的是LinkedList县貌。我們都知道它的底層是由鏈表實(shí)現(xiàn)的煤痕，所以我們要明白什么是鏈表祟敛？
一馆铁、LinkedList簡介
1.1、LinkedList概述
LinkedList是一種可以在任何位置進(jìn)行高效地插入和移除操作的有序序列，它是基于雙向鏈表實(shí)現(xiàn)的勋桶。
LinkedList 是一個(gè)繼承于AbstractSequentialList的雙向鏈表。它也可以被當(dāng)作堆棧鹃锈、隊(duì)列或雙端隊(duì)列進(jìn)行操作盆驹。
LinkedList 實(shí)現(xiàn) List 接口玖瘸，能對(duì)它進(jìn)行隊(duì)列操作蔑匣。
LinkedList 實(shí)現(xiàn) Deque 接口，即能將LinkedList當(dāng)作雙端隊(duì)列使用侨把。
LinkedList 實(shí)現(xiàn)了Cloneable接口骇笔，即覆蓋了函數(shù)clone()旭旭，能克隆稍味。
LinkedList 實(shí)現(xiàn)java.io.Serializable接口掂碱，這意味著LinkedList支持序列化但狭，能通過序列化去傳輸唱歧。
LinkedList 是非同步的。
1.2非剃、LinkedList的數(shù)據(jù)結(jié)構(gòu)
1）基礎(chǔ)知識(shí)補(bǔ)充
1.1）單向鏈表：
element：用來存放元素
next：用來指向下一個(gè)節(jié)點(diǎn)元素
通過每個(gè)結(jié)點(diǎn)的指針指向下一個(gè)結(jié)點(diǎn)從而鏈接起來的結(jié)構(gòu)，最后一個(gè)節(jié)點(diǎn)的next指向null他挎。
1.2）單向循環(huán)鏈表
element、next 跟前面一樣
在單向鏈表的最后一個(gè)節(jié)點(diǎn)的next會(huì)指向頭節(jié)點(diǎn)，而不是指向null脓鹃，這樣存成一個(gè)環(huán)
1.3）雙向鏈表
element：存放元素
pre：用來指向前一個(gè)元素
next：指向后一個(gè)元素
雙向鏈表是包含兩個(gè)指針的逸尖，pre指向前一個(gè)節(jié)點(diǎn)，next指向后一個(gè)節(jié)點(diǎn)瘸右，但是第一個(gè)節(jié)點(diǎn)head的pre指向null娇跟，最后一個(gè)節(jié)點(diǎn)的tail指向null。
1.4）雙向循環(huán)鏈表
element太颤、pre苞俘、next 跟前面的一樣
第一個(gè)節(jié)點(diǎn)的pre指向最后一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的next指向第一個(gè)節(jié)點(diǎn)龄章，也形成一個(gè)“環(huán)”吃谣。
2）LinkedList的數(shù)據(jù)結(jié)構(gòu)
如上圖所示，LinkedList底層使用的雙向鏈表結(jié)構(gòu)做裙，有一個(gè)頭結(jié)點(diǎn)和一個(gè)尾結(jié)點(diǎn)岗憋，雙向鏈表意味著我們可以從頭開始正向遍歷，或者是從尾開始逆向遍歷锚贱，并且可以針對(duì)頭部和尾部進(jìn)行相應(yīng)的操作仔戈。
1.3、LinkedList的特性
在我們平常中我們只知道一些常識(shí)性的特點(diǎn)：
1）是通過鏈表實(shí)現(xiàn)的拧廊，
2）如果在頻繁的插入杂穷，或者刪除數(shù)據(jù)時(shí)，就用linkedList性能會(huì)更好卦绣。
那我們通過API去查看它的一些特性
1）Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).
這告訴我們，linkedList是一個(gè)雙向鏈表飞蚓，并且實(shí)現(xiàn)了List和Deque接口中所有的列表操作滤港，并且能存儲(chǔ)任何元素，包括null，
這里我們可以知道linkedList除了可以當(dāng)鏈表使用溅漾，還可以當(dāng)作隊(duì)列使用山叮，并能進(jìn)行相應(yīng)的操作。
2）All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
這個(gè)告訴我們添履，linkedList在執(zhí)行任何操作的時(shí)候屁倔，都必須先遍歷此列表來靠近通過index查找我們所需要的的值。通俗點(diǎn)講暮胧，這就告訴了我們這個(gè)是順序存取锐借，
每次操作必須先按開始到結(jié)束的順序遍歷，隨機(jī)存取往衷，就是arrayList钞翔，能夠通過index。隨便訪問其中的任意位置的數(shù)據(jù)席舍，這就是隨機(jī)列表的意思布轿。
3）api中接下來講的一大堆，就是說明linkedList是一個(gè)非線程安全的(異步)来颤，其中在操作Interator時(shí)汰扭，如果改變列表結(jié)構(gòu)(add\delete等)，會(huì)發(fā)生fail-fast福铅。
通過API再次總結(jié)一下LinkedList的特性：
1）異步萝毛，也就是非線程安全
2）雙向鏈表。由于實(shí)現(xiàn)了list和Deque接口本讥，能夠當(dāng)作隊(duì)列來使用珊泳。
鏈表：查詢效率不高，但是插入和刪除這種操作性能好拷沸。
3）是順序存取結(jié)構(gòu)（注意和隨機(jī)存取結(jié)構(gòu)兩個(gè)概念搞清楚）
二色查、LinkedList源碼分析
2.1、LinkedList的繼承結(jié)構(gòu)以及層次關(guān)系
分析：
我們可以看到撞芍，linkedList在最底層秧了，說明他的功能最為強(qiáng)大，并且細(xì)心的還會(huì)發(fā)現(xiàn)序无，arrayList只有四層验毡，這里多了一層AbstractSequentialList的抽象類，為什么呢帝嗡？
通過API我們會(huì)發(fā)現(xiàn)：
1）減少實(shí)現(xiàn)順序存染ā（例如LinkedList）這種類的工作，通俗的講就是方便哟玷，抽象出類似LinkedList這種類的一些共同的方法
2）既然有了上面這句話狮辽，那么以后如果自己想實(shí)現(xiàn)順序存取這種特性的類(就是鏈表形式)，那么就繼承這個(gè)AbstractSequentialList抽象類，
如果想像數(shù)組那樣的隨機(jī)存取的類喉脖，那么就去實(shí)現(xiàn)AbstracList抽象類椰苟。
3）這樣的分層，就很符合我們抽象的概念树叽，越在高處的類舆蝴，就越抽象，往在底層的類题诵，就越有自己獨(dú)特的個(gè)性洁仗。自己要慢慢領(lǐng)會(huì)這種思想。
4）LinkedList的類繼承結(jié)構(gòu)很有意思仇轻，我們著重要看是Deque接口京痢，Deque接口表示是一個(gè)雙端隊(duì)列，
那么也意味著LinkedList是雙端隊(duì)列的一種實(shí)現(xiàn)篷店，所以祭椰，基于雙端隊(duì)列的操作在LinkedList中全部有效。
public abstract class AbstractSequentialList<E>
extends AbstractList<E>
//這里第一段就解釋了這個(gè)類的作用疲陕，這個(gè)類為實(shí)現(xiàn)list接口提供了一些重要的方法方淤，
//盡最大努力去減少實(shí)現(xiàn)這個(gè)“順序存取”的特性的數(shù)據(jù)存儲(chǔ)(例如鏈表)的什么鬼，對(duì)于
//隨機(jī)存取數(shù)據(jù)(例如數(shù)組)的類應(yīng)該優(yōu)先使用AbstractList
//從上面就可以大概知道蹄殃，AbstractSwquentialList這個(gè)類是為了減少LinkedList這種順//序存取的類的代碼復(fù)雜度而抽象的一個(gè)類携茂，
This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a "sequential access" data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class. //這一段大概講的就是這個(gè)AbstractSequentialList這個(gè)類和AbstractList這個(gè)類是完全//相反的。比如get诅岩、add這個(gè)方法的實(shí)現(xiàn)
This class is the opposite of the AbstractList class in the sense that it implements the "random access" methods (get(int index), set(int index, E element), add(int index, E element) and remove(int index)) on top of the list's list iterator, instead of the other way around.
//這里就是講一些我們自己要繼承該類讳苦，該做些什么事情，一些規(guī)范吩谦。
To implement a list the programmer needs only to extend this class and provide implementations for the listIterator and size methods. For an unmodifiable list, the programmer need only implement the list iterator's hasNext, next, hasPrevious, previous and index methods.
For a modifiable list the programmer should additionally implement the list iterator's set method. For a variable-size list the programmer should additionally implement the list iterator's remove and add methods.
The programmer should generally provide a void (no argument) and collection constructor, as per the recommendation in the Collection interface specification.
實(shí)現(xiàn)接口分析：
1）List接口：列表鸳谜，add、set式廷、等一些對(duì)列表進(jìn)行操作的方法
2）Deque接口：有隊(duì)列的各種特性咐扭，
3）Cloneable接口：能夠復(fù)制，使用那個(gè)copy方法滑废。
4）Serializable接口：能夠序列化蝗肪。
5）應(yīng)該注意到?jīng)]有RandomAccess：那么就推薦使用iterator，在其中就有一個(gè)foreach蠕趁，增強(qiáng)的for循環(huán)薛闪，其中原理也就是iterator，我們?cè)谑褂玫臅r(shí)候俺陋，使用foreach或者iterator都可以逛绵。
2.2怀各、類的屬性
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{ // 實(shí)際元素個(gè)數(shù)
transient int size = 0; // 頭結(jié)點(diǎn)
transient Node<E> first; // 尾結(jié)點(diǎn)
transient Node<E> last;
}
LinkedList的屬性非常簡單，一個(gè)頭結(jié)點(diǎn)术浪、一個(gè)尾結(jié)點(diǎn)、一個(gè)表示鏈表中實(shí)際元素個(gè)數(shù)的變量寿酌。注意胰苏，頭結(jié)點(diǎn)、尾結(jié)點(diǎn)都有transient關(guān)鍵字修飾醇疼，這也意味著在序列化時(shí)該域是不會(huì)序列化的硕并。
2.3、LinkedList的構(gòu)造方法
兩個(gè)構(gòu)造方法(兩個(gè)構(gòu)造方法都是規(guī)范規(guī)定需要寫的）
1）空參構(gòu)造函數(shù)
/**
* Constructs an empty list. */
public LinkedList() {
}
2）有參構(gòu)造函數(shù)
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null */
//將集合c中的各個(gè)元素構(gòu)建成LinkedList鏈表秧荆。
public LinkedList(Collection<? extends E> c) {
// 調(diào)用無參構(gòu)造函數(shù)
this();
// 添加集合中所有的元素
addAll(c);
}
說明：會(huì)調(diào)用無參構(gòu)造函數(shù)倔毙，并且會(huì)把集合中所有的元素添加到LinkedList中。
2.4乙濒、內(nèi)部類（Node）
//根據(jù)前面介紹雙向鏈表就知道這個(gè)代表什么了陕赃，linkedList的奧秘就在這里。
private static class Node<E> {
E item; // 數(shù)據(jù)域（當(dāng)前節(jié)點(diǎn)的值）
Node<E> next; // 后繼（指向當(dāng)前一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)）
Node<E> prev; // 前驅(qū)（指向當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)） // 構(gòu)造函數(shù)颁股，賦值前驅(qū)后繼
Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev;
}
}
說明：內(nèi)部類Node就是實(shí)際的結(jié)點(diǎn)么库，用于存放實(shí)際元素的地方。
2.5甘有、核心方法
2.5.1诉儒、add()方法
1）add(E)
public boolean add(E e) { // 添加到末尾
linkLast(e);return true;
}
說明：add函數(shù)用于向LinkedList中添加一個(gè)元素，并且添加到鏈表尾部亏掀。具體添加到尾部的邏輯是由linkLast函數(shù)完成的忱反。
分析：
LinkLast(XXXXX)
/**
* Links e as last element. */
void linkLast(E e) {
final Node<E> l = last; //臨時(shí)節(jié)點(diǎn)l(L的小寫)保存last，也就是l指向了最后一個(gè)節(jié)點(diǎn)
final Node<E> newNode = new Node<>(l, e, null);//將e封裝為節(jié)點(diǎn)滤愕，并且e.prev指向了最后一個(gè)節(jié)點(diǎn)
last = newNode;//newNode成為了最后一個(gè)節(jié)點(diǎn)温算，所以last指向了它
if (l == null) //判斷是不是一開始鏈表中就什么都沒有，如果沒有该互，則newNode就成為了第一個(gè)節(jié)點(diǎn)米者，first和last都要指向它
first = newNode; else //正常的在最后一個(gè)節(jié)點(diǎn)后追加，那么原先的最后一個(gè)節(jié)點(diǎn)的next就要指向現(xiàn)在真正的最后一個(gè)節(jié)點(diǎn)宇智，原先的最后一個(gè)節(jié)點(diǎn)就變成了倒數(shù)第二個(gè)節(jié)點(diǎn)
l.next = newNode;
size++;//添加一個(gè)節(jié)點(diǎn)蔓搞，size自增
modCount++;
}
說明：對(duì)于添加一個(gè)元素至鏈表中會(huì)調(diào)用add方法 -> linkLast方法。
舉例一：
List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.add(6);
首先調(diào)用無參構(gòu)造函數(shù)随橘，之后添加元素5喂分，之后再添加元素6。具體的示意圖如下：
上圖的表明了在執(zhí)行每一條語句后机蔗，鏈表對(duì)應(yīng)的狀態(tài)蒲祈。
2.5.2甘萧、addAll方法
addAll有兩個(gè)重載函數(shù)，addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型梆掸，我們平時(shí)習(xí)慣調(diào)用的addAll(Collection<? extends E>)型會(huì)轉(zhuǎn)化為addAll(int, Collection<? extends E>)型扬卷。
1）addAll(c);
public boolean addAll(Collection<? extends E> c) {//繼續(xù)往下看
return addAll(size, c);
}
2）addAll(size，c)：這個(gè)方法酸钦，能包含三種情況下的添加怪得，我們這里分析的只是構(gòu)造方法，空鏈表的情況(情況一)看的時(shí)候只需要按照不同的情況分析下去就行了卑硫。
//真正核心的地方就是這里了徒恋，記得我們傳過來的是size，c
public boolean addAll(int index, Collection<? extends E> c) { //檢查index這個(gè)是否為合理欢伏。這個(gè)很簡單入挣，自己點(diǎn)進(jìn)去看下就明白了。
checkPositionIndex(index); //將集合c轉(zhuǎn)換為Object數(shù)組 a
Object[] a = c.toArray(); //數(shù)組a的長度numNew硝拧，也就是由多少個(gè)元素
int numNew = a.length; if (numNew == 0) //集合c是個(gè)空的径筏，直接返回false，什么也不做河爹。
return false; //集合c是非空的匠璧，定義兩個(gè)節(jié)點(diǎn)(內(nèi)部類)，每個(gè)節(jié)點(diǎn)都有三個(gè)屬性咸这，item夷恍、next、prev媳维。注意：不要管這兩個(gè)什么含義酿雪，就是用來做臨時(shí)存儲(chǔ)節(jié)點(diǎn)的。這個(gè)Node看下面一步的源碼分析侄刽，Node就是linkedList的最核心的實(shí)現(xiàn)指黎，可以直接先跳下一個(gè)去看Node的分析
Node<E> pred, succ; //構(gòu)造方法中傳過來的就是index==size
if (index == size) { //linkedList中三個(gè)屬性：size、first州丹、last醋安。 size：鏈表中的元素個(gè)數(shù)。 first：頭節(jié)點(diǎn) last：尾節(jié)點(diǎn)墓毒，就兩種情況能進(jìn)來這里 //情況一吓揪、：構(gòu)造方法創(chuàng)建的一個(gè)空的鏈表，那么size=0所计，last柠辞、和first都為null。linkedList中是空的主胧。什么節(jié)點(diǎn)都沒有叭首。succ=null习勤、pred=last=null //情況二、：鏈表中有節(jié)點(diǎn)焙格，size就不是為0图毕，first和last都分別指向第一個(gè)節(jié)點(diǎn)，和最后一個(gè)節(jié)點(diǎn)眷唉，在最后一個(gè)節(jié)點(diǎn)之后追加元素吴旋，就得記錄一下最后一個(gè)節(jié)點(diǎn)是什么，所以把last保存到pred臨時(shí)節(jié)點(diǎn)中厢破。
succ = null;
pred = last;
} else { //情況三、index治拿！=size摩泪，說明不是前面兩種情況，而是在鏈表中間插入元素劫谅，那么就得知道index上的節(jié)點(diǎn)是誰见坑，保存到succ臨時(shí)節(jié)點(diǎn)中，然后將succ的前一個(gè)節(jié)點(diǎn)保存到pred中捏检，這樣保存了這兩個(gè)節(jié)點(diǎn)荞驴，就能夠準(zhǔn)確的插入節(jié)點(diǎn)了 //舉個(gè)簡單的例子，有2個(gè)位置贯城，1熊楼、2、如果想插數(shù)據(jù)到第二個(gè)位置能犯，雙向鏈表中鲫骗，就需要知道第一個(gè)位置是誰，原位置也就是第二個(gè)位置上是誰踩晶，然后才能將自己插到第二個(gè)位置上执泰。如果這里還不明白通惫，先看一下文章開頭對(duì)于各種鏈表的刪除枚抵，add操作是怎么實(shí)現(xiàn)的夭拌。
succ = node(index);
pred = succ.prev;
} //前面的準(zhǔn)備工作做完了突倍，將遍歷數(shù)組a中的元素谋国，封裝為一個(gè)個(gè)節(jié)點(diǎn)唆垃。
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o; //pred就是之前所構(gòu)建好的肛真，可能為null蜒程、也可能不為null税弃，為null的話就是屬于情況一纪岁、不為null則可能是情況二、或者情況三
Node<E> newNode = new Node<>(pred, e, null); //如果pred==null则果，說明是情況一幔翰，構(gòu)造方法漩氨，是剛創(chuàng)建的一個(gè)空鏈表，此時(shí)的newNode就當(dāng)作第一個(gè)節(jié)點(diǎn)遗增，所以把newNode給first頭節(jié)點(diǎn)
if (pred == null)
first = newNode; else
//如果pred叫惊！=null，說明可能是情況2或者情況3做修，如果是情況2霍狰，pred就是last，那么在最后一個(gè)節(jié)點(diǎn)之后追加到newNode饰及，如果是情況3蔗坯，在中間插入，pred為原index節(jié)點(diǎn)之前的一個(gè)節(jié)點(diǎn)燎含，將它的next指向插入的節(jié)點(diǎn)宾濒，也是對(duì)的
pred.next = newNode; //然后將pred換成newNode，注意屏箍，這個(gè)不在else之中绘梦，請(qǐng)看清楚了。
pred = newNode;
} if (succ == null) { //如果succ==null赴魁，說明是情況一或者情況二卸奉，
情況一、構(gòu)造方法颖御，也就是剛創(chuàng)建的一個(gè)空鏈表榄棵，pred已經(jīng)是newNode了，last=newNode郎嫁，所以linkedList的first秉继、last都指向第一個(gè)節(jié)點(diǎn)。
情況二泽铛、在最后節(jié)后之后追加節(jié)點(diǎn)尚辑，那么原先的last就應(yīng)該指向現(xiàn)在的最后一個(gè)節(jié)點(diǎn)了，就是newNode盔腔。
last = pred;
} else { //如果succ杠茬！=null，說明可能是情況三弛随、在中間插入節(jié)點(diǎn)瓢喉，舉例說明這幾個(gè)參數(shù)的意義，有1舀透、2兩個(gè)節(jié)點(diǎn)栓票，現(xiàn)在想在第二個(gè)位置插入節(jié)點(diǎn)newNode，根據(jù)前面的代碼，pred=newNode走贪，succ=2佛猛，并且1.next=newNode，
1已經(jīng)構(gòu)建好了坠狡，pred.next=succ继找，相當(dāng)于在newNode.next = 2； succ.prev = pred逃沿，相當(dāng)于 2.prev = newNode婴渡， 這樣一來，這種指向關(guān)系就完成了凯亮。first和last不用變边臼，因?yàn)轭^節(jié)點(diǎn)和尾節(jié)點(diǎn)沒變
pred.next = succ; //。假消。
succ.prev = pred;
} //增加了幾個(gè)元素硼瓣，就把 size = size +numNew 就可以了
size += numNew;
modCount++; return true;
}
說明：參數(shù)中的index表示在索引下標(biāo)為index的結(jié)點(diǎn)（實(shí)際上是第index + 1個(gè)結(jié)點(diǎn)）的前面插入。
在addAll函數(shù)中置谦，addAll函數(shù)中還會(huì)調(diào)用到node函數(shù)，get函數(shù)也會(huì)調(diào)用到node函數(shù)亿傅，此函數(shù)是根據(jù)索引下標(biāo)找到該結(jié)點(diǎn)并返回媒峡，具體代碼如下：
Node<E> node(int index) { // 判斷插入的位置在鏈表前半段或者是后半段
if (index < (size >> 1)) { // 插入位置在前半段
Node<E> x = first; for (int i = 0; i < index; i++) // 從頭結(jié)點(diǎn)開始正向遍歷
x = x.next; return x; // 返回該結(jié)點(diǎn)
} else { // 插入位置在后半段
Node<E> x = last; for (int i = size - 1; i > index; i--) // 從尾結(jié)點(diǎn)開始反向遍歷
x = x.prev; return x; // 返回該結(jié)點(diǎn)
}
}
說明：在根據(jù)索引查找結(jié)點(diǎn)時(shí)，會(huì)有一個(gè)小優(yōu)化葵擎，結(jié)點(diǎn)在前半段則從頭開始遍歷谅阿，在后半段則從尾開始遍歷，這樣就保證了只需要遍歷最多一半結(jié)點(diǎn)就可以找到指定索引的結(jié)點(diǎn)酬滤。
舉例說明調(diào)用addAll函數(shù)后的鏈表狀態(tài)：
List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.addAll(0, Arrays.asList(2, 3, 4, 5));
上述代碼內(nèi)部的鏈表結(jié)構(gòu)如下：
addAll()中的一個(gè)問題：
在addAll函數(shù)中签餐，傳入一個(gè)集合參數(shù)和插入位置，然后將集合轉(zhuǎn)化為數(shù)組盯串，然后再遍歷數(shù)組氯檐，挨個(gè)添加數(shù)組的元素，但是問題來了体捏，為什么要先轉(zhuǎn)化為數(shù)組再進(jìn)行遍歷冠摄，而不是直接遍歷集合呢？
從效果上兩者是完全等價(jià)的几缭，都可以達(dá)到遍歷的效果河泳。關(guān)于為什么要轉(zhuǎn)化為數(shù)組的問題，我的思考如下：1. 如果直接遍歷集合的話年栓，那么在遍歷過程中需要插入元素拆挥，在堆上分配內(nèi)存空間，修改指針域某抓，
這個(gè)過程中就會(huì)一直占用著這個(gè)集合纸兔，考慮正確同步的話惰瓜，其他線程只能一直等待。2. 如果轉(zhuǎn)化為數(shù)組食拜，只需要遍歷集合鸵熟，而遍歷集合過程中不需要額外的操作，
所以占用的時(shí)間相對(duì)是較短的负甸，這樣就利于其他線程盡快的使用這個(gè)集合流强。說白了，就是有利于提高多線程訪問該集合的效率呻待，盡可能短時(shí)間的阻塞打月。
2.5.3、remove(Object o)
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element */
//首先通過看上面的注釋蚕捉，我們可以知道奏篙，如果我們要移除的值在鏈表中存在多個(gè)一樣的值，那么我們會(huì)移除index最小的那個(gè)迫淹，也就是最先找到的那個(gè)值秘通，如果不存在這個(gè)值，那么什么也不做
public boolean remove(Object o) { //這里可以看到敛熬，linkedList也能存儲(chǔ)null
if (o == null) { //循環(huán)遍歷鏈表肺稀，直到找到null值，然后使用unlink移除該值应民。下面的這個(gè)else中也一樣
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;
}
unlink(xxxx)
/**
* Unlinks non-null node x. */
//不能傳一個(gè)null值過话原，注意，看之前要注意之前的next诲锹、prev這些都是誰繁仁。
E unlink(Node<E> x) { // assert x != null; //拿到節(jié)點(diǎn)x的三個(gè)屬性
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev; //這里開始往下就進(jìn)行移除該元素之后的操作，也就是把指向哪個(gè)節(jié)點(diǎn)搞定归园。
if (prev == null) { //說明移除的節(jié)點(diǎn)是頭節(jié)點(diǎn)黄虱，則first頭節(jié)點(diǎn)應(yīng)該指向下一個(gè)節(jié)點(diǎn)
first = next;
} else { //不是頭節(jié)點(diǎn)，prev.next=next：有1庸诱、2悬钳、3，將1.next指向3
prev.next = next; //然后解除x節(jié)點(diǎn)的前指向偶翅。
x.prev = null;
} if (next == null) { //說明移除的節(jié)點(diǎn)是尾節(jié)點(diǎn)
last = prev;
} else { //不是尾節(jié)點(diǎn)默勾，有1、2聚谁、3母剥，將3.prev指向1\. 然后將2.next=解除指向。
next.prev = prev;
x.next = null;
} //x的前后指向都為null了，也把item為null环疼，讓gc回收它
x.item = null;
size--; //移除一個(gè)節(jié)點(diǎn)习霹，size自減
modCount++; return element; //由于一開始已經(jīng)保存了x的值到element，所以返回炫隶。
}
2.5.4淋叶、get(index)
get(index)查詢?cè)氐姆椒?/p>
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc} */
//這里沒有什么，重點(diǎn)還是在node(index)中
public E get(int index) {
checkElementIndex(index); return node(index).item;
}
node(index)
/**
* Returns the (non-null) Node at the specified element index. */
//這里查詢使用的是先從中間分一半查找
Node<E> node(int index) { // assert isElementIndex(index); //"<<":*2的幾次方 “>>”:/2的幾次方伪阶，例如：size<<1：size*2的1次方煞檩， //這個(gè)if中就是查詢前半部分
if (index < (size >> 1)) {//index<size/2
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;
}
}
2.5.5栅贴、indexOf(Object o)
//這個(gè)很簡單斟湃，就是通過實(shí)體元素來查找到該元素在鏈表中的位置。跟remove中的代碼類似檐薯，只是返回類型不一樣凝赛。
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;
}
三、LinkedList的迭代器
在LinkedList中除了有一個(gè)Node的內(nèi)部類外坛缕，應(yīng)該還能看到另外兩個(gè)內(nèi)部類墓猎，那就是ListItr，還有一個(gè)是DescendingIterator赚楚。
3.1陶衅、ListItr內(nèi)部類
看一下他的繼承結(jié)構(gòu)，發(fā)現(xiàn)只繼承了一個(gè)ListIterator直晨，到ListIterator中一看：
看到方法名之后，就發(fā)現(xiàn)不止有向后迭代的方法膨俐，還有向前迭代的方法勇皇，所以我們就知道了這個(gè)ListItr這個(gè)內(nèi)部類干嘛用的了，就是能讓linkedList不光能像后迭代焚刺，也能向前迭代敛摘。
看一下ListItr中的方法，可以發(fā)現(xiàn)乳愉，在迭代的過程中兄淫，還能移除、修改蔓姚、添加值得操作捕虽。
3.2、DescendingIterator內(nèi)部類
/**
* Adapter to provide descending iterators via ListItr.previous */ 看一下這個(gè)類坡脐，還是調(diào)用的ListItr泄私，作用是封裝一下Itr中幾個(gè)方法，讓使用者以正常的思維去寫代碼，例如晌端，在從后往前遍歷的時(shí)候捅暴，也是跟從前往后遍歷一樣，使用next等操作咧纠，而不用使用特殊的previous蓬痒。 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();
}
}
四、總結(jié)
1）linkedList本質(zhì)上是一個(gè)雙向鏈表漆羔，通過一個(gè)Node內(nèi)部類實(shí)現(xiàn)的這種鏈表結(jié)構(gòu)梧奢。
2）能存儲(chǔ)null值。
3）跟arrayList相比較钧椰，就真正的知道了粹断，LinkedList在刪除和增加等操作上性能好，而ArrayList在查詢的性能上好嫡霞。
4）從源碼中看瓶埋，它不存在容量不足的情況。
5）linkedList不光能夠向前迭代诊沪，還能像后迭代养筒，并且在迭代的過程中，可以修改值端姚、添加值晕粪、還能移除值。
6）linkedList不光能當(dāng)鏈表渐裸，還能當(dāng)隊(duì)列使用巫湘，這個(gè)就是因?yàn)閷?shí)現(xiàn)了Deque接口。
