? ? LinkedList是另外一種常見的list實(shí)現(xiàn)類，底層基于鏈表實(shí)現(xiàn)，不僅實(shí)現(xiàn)了List接口，還是實(shí)現(xiàn)了Deque接口，所以說LinkedList也是一種隊(duì)列。LinkedList是雙向鏈表，它的插入刪除效率較高，但是查詢效率較低（雖然有一定的優(yōu)化）。first、last表示列表的首尾節(jié)點(diǎn)，容量大小用size表示。下面就具體講講LinkedList的源碼。
1.Node節(jié)點(diǎn)信息
? ? Node的構(gòu)造方法已經(jīng)使node節(jié)點(diǎn)插入了鏈表，但此時(shí)整個(gè)鏈表還不是雙向鏈表。還需要將node前驅(qū)的后繼(node.prev.next=node)、后繼的前驅(qū)(node.next.prev=node)指向node，如此，整個(gè)鏈表構(gòu)成了雙向鏈表。
2.構(gòu)造函數(shù)
? ? ? LinkedList有兩個(gè)構(gòu)造函數(shù)。傳入Collection對(duì)象的構(gòu)造函數(shù)調(diào)用了addAll(size, c)。
? ? ? addAll(index, c)首先會(huì)檢查index和c，檢查通過后用succ保存后繼節(jié)點(diǎn)，然后再pred、succ之間插入c的元素并且不停的跟新pred節(jié)點(diǎn)，如果pred為空，表示是從首節(jié)點(diǎn)插入，所以需要讓first指向newNode；否則使pred的后繼指向newNode。所有元素插入到隊(duì)列后，如果succ為空，則last指向pred節(jié)點(diǎn)；否則關(guān)聯(lián)pred與succ，即使succ的前驅(qū)指向pred，succ的后繼執(zhí)行pred。最后修改size和modCount。
3.重要方法
? ? ① linkFirst方法。此方法使構(gòu)造一個(gè)新節(jié)點(diǎn)并使first指向新節(jié)點(diǎn)。先把first備份，在利用構(gòu)造函數(shù)構(gòu)造新的首節(jié)點(diǎn)。如果原來first為空，表示鏈表為空，則把last指向newNode；否則是原首節(jié)點(diǎn)的前驅(qū)執(zhí)行newNode；最后修改size和monCount。
? ? ② linkLast方法。類似linkFirst方法，此方法構(gòu)造一個(gè)新節(jié)點(diǎn)，并使last指向新節(jié)點(diǎn)。先用l備份last，在創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并使last指向新節(jié)點(diǎn)。如果last為空，意味著原鏈表為空，需要把first指向新節(jié)點(diǎn)；否則使l的后繼指向新節(jié)點(diǎn)。
? ? ③ linkBefore方法。此方法在succ節(jié)點(diǎn)之前插入一個(gè)新節(jié)點(diǎn)。這里有一個(gè)條件，那就是succ不能為空。先利用pred記錄原succ的前驅(qū)。在創(chuàng)建一個(gè)新節(jié)點(diǎn)。succ的前驅(qū)指向新節(jié)點(diǎn)，再根據(jù)pred是否為空判斷到底把first指向新節(jié)點(diǎn)還是把pred的后繼指向新節(jié)點(diǎn)。
? ? ④ unlinkFirst方法。此方法刪除首節(jié)點(diǎn)f。先用next保存f的后繼，在使f的引用指向空（f是首節(jié)點(diǎn)所以不用置空f的前驅(qū)），使next指向first。如果next為空，則鏈表現(xiàn)在沒有元素，所有l(wèi)ast也為空，否則把next.prev也置空，使jvm回收原first的資源。
? ? ⑤ unlinkLast方法。刪除非空尾節(jié)點(diǎn)l。類似unlinkFirst方法。先保存前驅(qū)，在置空l，接著把前驅(qū)賦值給last。最后根據(jù)前驅(qū)是否為空判斷鏈表是否有元素，根據(jù)結(jié)果把first賦空或者把現(xiàn)在last的后繼賦空。
? ? ⑥ unlink方法。此方法刪除節(jié)點(diǎn)x。主要使x的前驅(qū)和后繼直接關(guān)聯(lián)上即可。這里要說明的如果前驅(qū)為空，沒必要再次使x.prev = null。最后還要修改size和modCount。詳細(xì)過程請(qǐng)看代碼。
? ? ⑦ node方法。此方法得到指定index序號(hào)的元素節(jié)點(diǎn)。如果index小于0.5*size，從前往后遍歷尋找序號(hào)為index的節(jié)點(diǎn)；否則，從后向前遍歷尋找node。
? ? ⑧contains與indexOf方法。如同ArrayList，contains也是利用indexOf判斷元素是否存在。indexOf方法返回元素第一次出現(xiàn)的位置，如果不存在則返回-1.
? ? LinkedList剩下的方法（包括queue接口的方法）主要就是利用size、first、last以及上訴提到的幾個(gè)方法實(shí)現(xiàn)。很簡(jiǎn)潔。
? ? clear方法清空元素。
