LinkedList - 資料結構簡介

LinkedList(鏈結串列) 是一種線性資料集合結構，但其資料集合順序卻不一定按線性的順序儲存資料。

LinkedList(鏈結串列) 資料儲存方式是資料節點方式儲存。

每個資料節點會紀錄以下內容:

1. 該節點的資料內容參照
2. 指向下個資料節點的指標

LinkedList(鏈結串列) 則是多個 Node 所鏈結在一起的結構如下：

優點是當資料個數是動態加入節點速度快，因為只需要改變指標。

缺點是除了資料本身需要而外紀錄下一個資料節點的指標，所以記憶體消耗大。

如果都是放入 LinkedList 最前方，則其插入資料只需要 O(1)

但如果要放入特定位置的節點或是搜尋特定節點則需要花 O(n)

上面所述是節點只紀錄下一個節點位置的 LinkedList(鏈結串列) 又稱為單向鏈結串列，由於只知道下一個位置所以只能往單向尋找。

而為了改善這個問題，把結點中多紀錄一個前一個位置的指標，這類LinkedList(鏈結串列) 又稱為雙向鏈結串列。可以同時往前或是往後找尋資料。但代價就是要多紀錄一個指標。

應用

因為 LinkedList(鏈結串列) 在動態新增資料速度快

所以可以被拿來實作 Stack(堆疊) 或是 Queue(佇列) 等等處理資料流的結構。