Aloha！又是我少女人妻 Uerica ，今天中秋節大家吃肉了嗎！傳說中后羿的狗狗偷吃了嫦娥吃剩的靈藥，就跟嫦娥一樣一起飛到月亮上，然後把嫦娥跟月亮都吃掉了！恩...狗狗這麼貪吃也合理啦。

連結串列 (Linked List)

好的～今天要來聊一下鏈結串列在記憶體中是如何儲存資料的吧！連結串列與陣列 (Array) 一樣是線性資料結構，但一般的程式語言在宣告陣列時，需要先規定記憶體儲存空間的大小（陣列長度），所以如果不知道資料會增長到多大，常常會碰到不知道如何規定資料大小，或是記憶體預留過多空間，造成空間浪費等情況，此部份在介紹陣列的資料結構會有更詳細的說明。但 JavaScript 所提供的陣列方法並沒有一般語言來得嚴謹，原因是底層作用不太一樣，這部分之後再寫一篇與大家說明瞜～

連結串列定義與特性

連結串列是由多個節點 (node) 所組成，節點之間會用指標 (pointer) 來做連結，所謂的指標就是紀錄指向的另一個節點在記憶體中的位置，如果沒有下一個節點則為 null。而每個節點中會紀錄需要被存取的資料元素。

節點 (node) 中存取的資料：

• 資料元素 (：需要被存取的一筆資料
• 指標：指向的節點在記憶體中的位置

而連結串列的特性是便於插入或刪除節點，但在存取數據時，一筆資料元素的存取會佔較多記憶體空間也較為費時。不過因為擁有指標，所以不用像陣列一樣連續式的儲存在記憶體內，而是可以分散在不同地方。

• 優點
  • 便於資料元素插入、刪除
  • 非佔用連續記憶體空間，無須先定義資料大小與長度
• 缺點
  • 由於節點是被分散在記憶體各個角落，且要依照指標才能找到下一個節點，所以只能用順序存取 (sequential access) 的方式。
  • 在增加一個資料元素時，因除了寫入資料元素在節點外還需要寫入指向的指標，所以增加一個節點比起陣列單純增加資料元素佔較多記憶體空間。

連結串列是由一連串結點所組成

實際在記憶體中會是這個樣子，無需連續儲存

常見的基本操作

插入新節點

連結串列若要插入新節點(如圖示的 Node New 要插入 Node A 與 Node B 之間)，只需改變 Node A 指標指向的位置，以及在 Node New 寫入Node B 位置即可。

將 Node New 插入 Node A 與 Node B 之間

只需改寫或增加下一個 node 的位置

刪除節點

承上圖，假設現在我們要刪除 Node B ，則將 Node New 的指標指向 Node C 的位置即可。

此時 Node B 已無法存取，可刪除或持續保留在記憶體中，這邊也可發現若有兩個 Node 指向同一個 Node 是可行的，這也是連結串列中資料可共享的優勢。

連結串列類型

單向連結串列（Singly Linked List)

單向連結串列，也是最基本的連結串列，每個節點的指標指向下一個節點，存取時只能使用順序存取的方式從頭開始依序往下讀取。

雙向連結串列（Doubly Linked List）

雙向連結串列與單向不同的是，每個節點都有指向上一個節點與下一個節點的指標，所以在存取時可從任一節點開始。

迴圈連結串列（Circularly Linked List）

迴圈連結串列與雙向連結串列類似，但迴圈連結串列頭尾節點的指標會再指向對方並連成一個環。

關於連結串列的時間複雜度

由於連結串列屬於線性關係，所以在資料存取需要 O(n) 的時間複雜度，不過插入與刪除通常只需要 O(1) 的時間複雜度。

參考資料：

Linked list Javascript實作及Leet code題目解析

JavaScript 學演算法（五）- 鏈結串列 Linked list

維基百科 - 連結串列

資料結構: Pointer 指標與Link-link實作 youtube影片

感謝各位閱讀！最近寫文章很少陪狗狗玩，再不帶她出門遛遛我可能也會被吃了！哈哈哈哈，明天見啦掰掰～