介紹

Linked List 鏈結串列是一種常見且基礎的資料結構，我們可以基於 Linked List 去建立 Queue、Stack 等資料結構。關於Stack與Queue可以參考這篇文章LeetCode 課前預習 - 掌握 Stack 和 Queue 大全。

Linked List 的種類

  • single linked list: 只能訪問下一個節點
  • double linked list: 可以訪問上一個和下一個節點
  • circular linked list: 最後一個節點指向第一個節點

linked list 一個很重要的概念是這個 list 的* Node.next 是儲存下一個 Node 在實際記憶體中的位置*，而不是儲存下一個 Node 的值。

結構

節點

一個linked list主要由節點Node組成，每個節點包含兩個部分：

  1. data: 用來存放節點的數據
  2. next: 用來指向下一個節點，是一個指標 pointer，pointer 會指向下一個節點，而最後一個節點的 pointer 則是指向 Null。
1
2
3
4
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

這時我們可以透過 new 來建立節點:

1
2
3
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

串起來

那麼，我們該如何將這些節點連接起來呢?先透過改變物件的 next 屬性試試，結果變成巢狀物件了

1
2
node1.next = node2
node2.next = node3

遍歷

雖然變成巢狀的物件，但確實每個節點的next都為下一個節點物件，我們可以寫一個函式去模擬 linked list

1
2
3
4
5
6
7
8
9
10
11
def print_linked_list(head):
    current = head
    result = "root -> " 
    while current:
        result += str(current.data) + " -> "
        current = current.next # 這裡會是重點，每個節點的 next 儲存下一個節點的實際記憶體位置
    result += "None"
    print(result)

# 最後，就可以印出類似 linked list 的字串
# root -> 2 -> 4 -> 6 -> None

操作

如何存取第一個節點？

  • 知道第一個節點的位置很重要，因為我們可以從第一個節點開始遍歷整個linked list。
  • 通常我們會使用一個head指標來指向第一個節點，這樣我們就可以從head開始遍歷整個linked list。

主要操作
接著要介紹的是針對 linked list 進行一些操作的一些方法，起初我們先建立兩個建構子，一個用於創造節點物件，一個創造linked list並先寫好幾個方法的名字在裡面。這些方法裡面包涵：

  • length: 回傳 linked list 的長度
  • is_empty: 判斷 linked list 是否為空
  • get: 取得特定 index 的節點
  • remove: 移除特定 index 的節點
  • add_at_index: 在特定 index 新增節點
  • __str__: 用來印出 linked list 的字串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def length(self):
        pass

    def is_empty(self):
        pass

    def get(self, index):
        pass

    def remove(self, index):
        pass

    def add_at_index(self, index):
        pass

    def __str__(self):
        current = self.head
        result = "root -> " 
        while current:
            result += str(current.data) + " -> "
            current = current.next
        result += "None"
        print(result)

length O(n)

主要邏輯就是碰到一個節點就 count+1，移動到下一個節點再 count+1，直到遇到 null 為止

1
2
3
4
5
6
7
def length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

is_empty O(1)

如果 head 為 None，那麼 linked list 就是空的

1
2
def is_empty(self):
    return self.head is None

get by index

這個方法主要是取得特定 index 的節點，我們可以透過迴圈去找到特定 index 的節點，如果找到就回傳該節點，否則回傳 None。

1
2
3
4
5
6
7
def get(self, index):
    if index < 0 or index >= self.length():
        raise IndexError("Index out of bounds")
    current = self.head 
    for _ in range(index):
        current = current.next
    return current

remove by index O(n)

這個方法主要是移除特定 index 的節點，我們可以透過迴圈找到特定 index 的節點，然後將該節點的 next 指向下下個節點，這樣就可以移除該節點。
但是需要注意的是如果移除 index 為 0 的節點，我們需要將 head 指向下一個節點，這樣就可以移除第一個節點。

1
2
3
4
5
6
7
8
9
10
11
def remove(self, index):
    if index < 0 or index >= self.length():
        raise IndexError("Index out of bounds")
    if index == 0:
        self.head = self.head.next # 若是要移除第一個節點，需要將 head 指向下一個節點
    else:
        current = self.head
        # 開始透過迴圈找到特定 index 的節點
        for _ in range(index - 1):
            current = current.next # 找到最後 current.next 就是要移除的節點
        current.next = current.next.next # 把 current.next 指向下下個節點

add by index O(n)

主要是新增一個新的節點到特定的 index，也是要注意是否新增的 index 是 0，如果是 0 的話，我們需要將 head 指向新的節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def add_at_index(self, index, data):
    if index < 0 or index > self.length():
        raise IndexError("Index out of bounds")
    # 建立新 node 
    new_node = Node(data)
    # 塞在第一個位置
    if index == 0:
        new_node.next = self.head
        self.head = new_node
    # 塞在其他位置
    else:
        current = self.head
        # 開始透過迴圈找到特定 index 的節點
        for _ in range(index - 1): # index - 1 就是要塞的前一個位置
            current = current.next
        new_node.next = current.next
        current.next = new_node

總結

使用 Linked List 的主要重點是：

  1. 用For loop遍歷：你會發現，add, get, length, remove 這些方法都是透過迴圈去找到特定 index 的節點，然後進行操作。
  2. Index 合理性：跟 index 有關的，都要先檢查 index 的合理性 if index < 0 or index >= self.length():
  3. Head 的考量：在 remove, add 的時候，要考量到是否會更動到第一個節點。
  4. 判斷index是否超過長度：需要特別注意的是 add 因為可能要塞在最後 所以 index 可以等於 length，但是 remove 和 get 不行，因為 remove 是要移除節點，所以 index 不能等於 length。
  5. for loop 的 range 到底要不要 -1：這邊你可以想像，像是add或是remove時，我們都需要目標index的前一個節點才能進行操作，所以在這邊要-1。
    1. get: 你要找到的是 index 的節點，所以不用-1
    2. remove: 你要找到的是 index 要移除目標的前一個節點，所以要-1
    3. add: 你要找的是 index 要塞的前一個節點，所以要-1

時間複雜度

  • get：O(n)
  • remove：O(n)
  • length：O(n)
  • is_empty：O(1)
  • add_at_index：O(n)

比較

Linked List vs Array 這兩者的關鍵差別？

  • array 會根據儲存的data的bytes跟上一個節點來決定下一個節點的位置，他是一個連續的記憶體空間，
  • linked list: 每個節點會儲存下一個節點的位置，因此不需要連續的記憶體空間。

Linked List 與 Queue 和 Stack 的關係
以下是對比Linked List、Queue和Stack的表格，這個表格簡明地比較了Linked List、Queue和Stack的定義、結構、操作、時間複雜度、優缺點及使用情境，幫助理解它們之間的相似和差異：

特性 Linked List Queue Stack
定義 一連串節點，每個節點包含資料和指向下一個節點的指針 先進先出（FIFO）資料結構 後進先出（LIFO）資料結構
結構 單向鏈表、雙向鏈表或循環鏈表 單向鏈表或陣列，通常有指向頭和尾的指針 單向鏈表或陣列，通常在頭部操作
插入 可以在任意位置插入 只能在隊尾插入（enqueue） 只能在堆疊頂部插入（push）
刪除 可以在任意位置刪除 只能在隊首刪除（dequeue） 只能在堆疊頂部刪除（pop）
訪問 隨機訪問，需從頭節點開始依次訪問 只能訪問隊首元素（peek） 只能訪問堆疊頂部元素（peek）
時間複雜度 插入/刪除：O(1)（在給定位置） 入隊/出隊：O(1) 壓入/彈出：O(1)
缺點 隨機訪問效率低，需額外的指針空間 只能在固定一端插入和刪除，隨機訪問不方便 只能在固定一端插入和刪除，隨機訪問不方便
使用情境 需要頻繁插入、刪除中間元素的情境 按順序處理資料，如排隊系統 逆序處理資料，如函數調用堆疊

Reference