[Data Structures] Linked List 鍊結串列

寫過程式的朋友一定知道什麼是陣列，在Java裡以[]表示，如果想使用一組長度為10的字串陣列就需宣告為

String[] intArray = new String[10]; 

再將值塞入陣列中，但是有個不方便的地方是必須先宣告陣列的長度才能使用，但有時沒辦法先知道陣列的長度，所以使用collection類別，像是list, set 等...



Linked List跟這個什麼關係，我認為linked list是集合不需宣告長度的關鍵。

單向鏈結串列：




假設 有個物件，擁有兩個屬性 value, next，在next的屬性中參考到下個物件的位址，這樣就能設定成一個串列，不需預先設定長度也能使用，可是這裡你可能會說，物件只知道下個物件，如何知道整個串列的長度，這時我們需要iterator來幫助我們走訪集合，也能幫我們計算長度。

Linked List如果需要新增，刪除元素 只要修改next的參考就能插入或刪除元素，但是如果想刪除串列中最後一個元素，需要花比較多的時間，因為必須先找到最後一個元素再修改next參考，這時我們就需要雙向鏈結串列。


雙向鏈結串列：



雙向鏈結串列，多了一個previous參考，可直接從尾端做搜尋，加快修改、刪除的速度。

Youtube.com參考