資料結構 單向鏈結串列 singly linked list

資料結構的單向鏈結串列筆記。

單向鏈結串列(Singly linked list)為線性串列資料結構，特點是：

資料是有順序的。

非連續的記憶體空間儲存資料。

每個資料元素除了資料本身還存有下一個資料元素的位址（指標(pointer)）即鏈結(linked)。

單向鏈結串列的一個資料元素又稱為節點(node)，每個節點由資料欄位(data)及指標欄位(pointer)組成。資料欄位存有資料，指標欄位則存有下個節點的指標。第一個節點的指標稱為head，即為單向鏈結串列的頭，然後透過儲存的指標可以一直往下找到下個結點，此即為單向鏈結串列。

Singly Linked List

┌────┐
│head│
└─┬──┘
  │
  ▼
┌────┬────┐    ┌────┬────┐    ┌────┬────┐
│data│next├───►│data│next├───►│data│null│
└────┴────┘    └────┴────┘    └────┴────┘
   node1          node2          node3

下面圖示說明單向鏈結串列的操作。

建立

建立一個指向第一個節點的head。第一個節點資料及指標欄位為null，即最後一個節點，。

┌────┐
│head│
└─┬──┘
  │
  ▼
┌────┬────┐
│null│null│
└────┴────┘
   node1

插入

在原本的第2個節點和第3個節點插入一個新結點。新結點的指標指向原本第3個節點，原本第2個節點的指標指向新節點。

┌────┐
│head│
└─┬──┘
  │
  ▼
┌────┬────┐    ┌────┬────┐              ┌────┬────┐
│ A  │next├───►│ B  │next├──┐ ──X── ┌──►│ C  │null│
└────┴────┘    └────┴────┘  │       │   └────┴────┘
   node1          node2     ▼       │      node4
                           ┌────┬───┴┐
                           │ D  │next│ (new node)
                           └────┴────┘
                              node3

刪除

把原本的第2個節點刪除。第1個節點的指標改為指向第3個節點

┌────┐
│head│
└─┬──┘
  │
  ▼
┌────┬────┐    ┌────┬────┐    ┌────┬────┐
│ A  │next├─X─►│ B  │next├─X─►│ C  │null│
└────┴───┬┘    └────┴────┘    └────┴────┘
   node1 │        node2        ▲ node2
         │       (deleted)     │
         │                     │
         └─────────────────────┘

• 大話資料結構-程杰(ISBN 978-986-6072-11-6)
• Golang 單向鏈結串列實作
• Java LinkedList 簡介
• 資料結構 環狀單向鏈結串列