對LinkedList源碼的一些個人理解
- 2020 年 6 月 5 日
- 筆記
由於轉行的原因，最近打算開始好好學習，昨天看到了部分的LinkedList源碼，並且看了一點數據結構的影片，現總結部分自己的心得體會，以供後期給現在的自己拍磚~
雙向鏈表每一個元素都有數據本身加指向前一個元素的屬性與指向後一個元素的屬性。
下面對Java中LinkedList部分源碼進行個人理解的分享：
LinkedList定義大小和頭尾節點，構造方法。
定義Node節點，節點有三個屬性，元素和前後指向。
添加：
125：在頭節點之前新增元素的方法
126：將首節點賦值給f變數
127：用構造函數新創建一個節點，名為newNode，他的前節點為空，後節點為首節點
128：將新添加的節點賦值給first，成為新的頭節點
129-132：判斷原來頭節點是否為空，如果為空則表明這個節點即是尾節點也是頭節點，如果不為空則將原來首節點的前一個節點指向新節點。就是將新節點插入最前面變為新的首節點。
133：容量+1
134：變化+1
140-150：在尾節點新增元素，與頭節點方法類似。
506：在給定位置添加元素的方法
507：調用檢查索引位置方法，實則為檢查傳入索引是否越界，越界為>size或者<0
508-510:判斷索引和容量大小是否相等，如果相等則在鏈表尾部插入元素。
511-513：如果大小不相等，則調用linkBefore方法插入元素，其中有node(index)方法。
558-562：檢查索引是否越界，如果越界了則拋出索引越界異常，異常資訊在outOfBoundMsg中
540-542：檢查索引是否大於等於0且小於等於list的容量
549-551:異常資訊的定義，輸出索引和容量
node(index)方法：獲取指定位置的node（非空）元素，返回指定位置index的元素。
569：判斷索引是否小於容量的一半，如果索引小於容量的一半，則從頭節點往後進行遍歷。
570：將頭節點賦值給x
571-573：從頭節點往後遍歷，直到找到索引對應的節點並返回。
574-580：如果索引大於容量的一半，則從尾部進行遍歷，將指向前一個的元素賦值給x並返回
在succ前插入一個新的節點，該方法需要傳入兩個參數，第一個參數為想要插入的新的元素，第二個參數為原有節點，將第一個插入第二個之前~：
157：將原有節點的向前指向的地址賦值給pred
158：利用構造函數新創建一個newNode節點，該節點的前指向為succ原有的前指向地址，該節點的後指向為succ，可以理解為在原有的succ前面插入了一個新的元素
159：將succ的前指向地址設置為新插入的元素
160-161：如果succ的前指向為空，那麼很顯然新插入的元素就為首元素
162-163：如果不為空，那麼將succ原來的前面元素的next屬性設置為新元素，這樣就插入新元素成功。
164：容量+1
165：變化+1
addAll方法：將集合插入LIST鏈表當中
addAll的具體實現：傳入索引和集合兩個參數，將集合在指定的位置插入
406：檢查索引是否越界，具體實現在上面
408：將集合C轉換為一個數組a
409：將數組a的長度賦值給numNew
410-411：如果數組長度為0，則返回false
413：聲明插入節點的前後兩個節點
414-416：判斷索引是否等於容量，如果等於那麼插入位置的後節點就為空，前節點為最後一個節點
417-421：如果不等於容量，就將後節點賦值為index的元素，前節點賦值為後節點的前節點
422-424：遍歷a數組，將元素存儲到o裡面再放入e中，然後新建節點對象，放入newNode中
425-430：如果插入位置為鏈表頭，那麼將其放入鏈表頭部位置。
432-433：如果插入位置為尾端，則將尾部節點重置。
434-437：如果不在尾端，將鏈表連起來
439-441：容量增加，變化增加。
offer方法，默認在尾部插入新元素
默認在頭部插入新元素
默認在尾部插入新元素
檢索：
該方法通過索引獲取元素並返回該元素
首先檢查索引是否越界，然後通過node方法返回指定索引的元素
獲取首節點元素的方法
將首節點元素賦值給f變數，然後對f進行判斷，為空則拋出異常，不為空返回f元素
element方法也是調用獲取首元素的方法。
peek方法也是返回首節點，只是不拋出異常而已。
getLast和peekLast都是獲取最後一個元素，區別為一個拋出異常，一個不拋出異常。
從頭結點向尾結點遍歷，並返回第一個匹配的索引
從尾結點向頭結點遍歷，並返回最後一個匹配的索引。
判斷對象是否在鏈表中，實際為調用indexOf方法進行循環遍歷前後節點來判斷
刪除：
從鏈表中刪除一個指定的對象
356-362：判斷需要刪除的元素是否為null，如果為null，則從前往後遍歷，將所有的為null的元素進行unlink操作，並返回true
363-370：如果刪除的元素不為Null,那麼也從前往後遍歷，將所有的元素進行unlink操作，並返回true
unlink該方法為刪除指定元素的方法
211-213：聲明element為需要刪除的元素，next為需要刪除的元素的後指向，prev為需要刪除元素的前指向
215-217：如果需要刪除的元素的前指向為空，那麼需要刪除的元素就為首節點，將第二個元素賦值給首節點即可，這樣鏈表中就沒有原先的x也就是原先的首節點了，實現了刪除節點的效果。
218-220：如果需要刪除元素的前指向不為空，就將需要刪除的節點的後指向賦值給需要刪除的節點的前面的元素的後指向，然後將需要刪除元素的前指向設置為空，這樣就可以把需要刪除的元素分割出來，和其他的鏈表元素沒有連線關係，實現了刪除節點的效果。
222-224：如果需要刪除的元素的後指向為空，那麼需要刪除的元素就為尾節點，將原先倒數第二個元素賦值給尾節點即可，這樣鏈表中就沒有原先的x也就是原先的尾節點了，實現了刪除節點的效果。
225-227：如果需要刪除的元素的後指向不為空，那麼將需要刪除的元素的前指向賦值給需要刪除的後一個元素的前指向且將刪除元素的後指向設置為空。這樣就實現了刪除節點的效果。
229-233：將需要刪除的元素設置為空，容量減一，變化+1，返回這個元素。
該方法刪除指定索引的元素
524-527：判斷索引是否越界，調用unlink方法進行刪除。
以上三個都是刪除元素的方法，默認刪除頭結點
該方法為刪除尾結點的方法
個人小理解：LinkedList是基於雙向鏈表，其內部的實現源於對雙向鏈表的操作，所以適用於頻繁增加、刪除的情況，俗稱增刪快，在鏈表的頭尾添加或者刪除元素的時候，通過源碼就可以看出直接就在鏈表頭尾改了個指向，效率很高，但是在增刪位於鏈表中間的元素時，就需要進行遍歷，看插入節點的位置距離頭尾節點的長度進行遍歷，越往中間越耗時。查詢的時候會調用node方法進行從頭尾遍歷，進行查詢，而ArrayList有索引，故相較於ArrayList來說，LinkedList的查詢速度不夠快。
