岳氏礦泉水

泉源思緒，細品人生

0%

資料結構與演算法筆記 | 鏈結串列 (Linked List)

發表於 更新於 分類於 ， Disqus：
文章字數： 3.5k 所需閱讀時間 ≈ 18 分鐘

鏈結串列是一種線性資料結構，利用節點 (node) 將資料串起來，其中每個節點包含：

  • 值 (value)：也就是儲存的資料
  • 引用 (reference)：此處的引用是指向下一個節點的參考

至於為何要使用鏈結串列，原因在於新增或刪除元素時，若用陣列儲存資料，需要搬移元素，耗時又費力。但若以鏈結串列儲存資料，僅需知道元素的索引，以及下一個節點指向何者，即可對資料進行操作。

陣列 鏈結串列
儲存位置 連續記憶體區塊 分散在記憶體各處
插入刪除 慢，需要移動其他元素 快，只需改變指標
隨機存取 快（可用索引） 慢，要一個一個走過去
空間大小 固定或需重建 動態增加

建立鏈結串列

假設我們想要建立以下的鏈結串列：

            
            graph LR
  N1((1)) --> N2((3))
  N2 --> N3((5))
  N3 --> N4((7))
  N4 --> N5((9))
  N5 --> X[None]

必須拆分為兩步驟：

  1. 建立節點：定義每個節點的資訊，包含值與引用
  2. 建立鏈結串列：根據節點的定義，串起每個節點形成串列

建立節點

首先必須先寫出每個節點的定義：

1
2
3
4
class ListNode:
    def __init__(self, val: int):
        self.val = val                      # 節點值
        self.next: ListNode | None = None   # 指向下一個節點的引用

初始化各個節點：

1
2
3
4
5
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(5)
n3 = ListNode(7)
n4 = ListNode(9)

建立鏈結串列

根據初始化的節點，需要建立節點之間的引用：

1
2
3
4
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

建立完成後，可以嘗試走訪整條串列：

1
2
3
4
curr = n0
while curr is not None:   # 若為 None 表示走到底
    print(curr.val)
    curr = curr.next      # 當前值變成下一節點

操作鏈結串列

操作鏈結串列之前，必須先瞭解如何建立串列：

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

新增節點

新增節點的方式其實十分直觀。假設我們想要在 $n_{0}$ 與 $n_{1}$ 間新增一個節點 $p$，步驟是：

  • 先將 $n_{1}$ 設定為 $n_{0}$ 的下一個節點
  • 設定 $n_{1}$ 為 $p$ 的下一個節點
  • 指定 $n_{0}$ 的下一個節點為 $p$

簡單來說，就是將 $n_{1}$ 的下個節點設定為 $p$，並且重新指定 $n_{0}$ 的下個節點為 $p$，此時就可串聯成 n0 -> p -> n1。

1
2
3
4
def insert(self, n0: ListNode, p: ListNode) -> None:
    n1 = n0.next
    p.next = n1
    n0.next = p

刪除節點

刪除節點的方法與新增節點類似，只不過是反向操作，也就是斷開 $n_{0}$ 與 $p$ 的連結，重新將 $n_{0}$ 與 $n_{1}$ 連起來。雖然 $p$ 還是指向 $n_{1}$，但由於已經斷開 $n_{0}$ 與 $p$ 的連結，因此無法訪問到 $p$。

1
2
3
4
def remove(self, n0: ListNode) -> None:
    p = n0.next
    n1 = p.next
    n0.next = n1

訪問節點

不同於陣列，若要訪問鏈結串列的節點，需要從頭至尾遍歷，直至找到目標節點，對於索引 $i$ 的節點，需要走 $i - 1$ 輪，時間複雜度為 $\mathcal{O}(n)$。

1
2
3
4
5
6
7
def access(self, index: int) -> ListNode | None:
    curr = self.head
    for _ in range(index):
        if not curr:
            return None
        curr = curr.next
    return curr

如果想要遍歷整個串列，可以使用與訪問類似的作法，並將訪問過的節點全部蒐集在一個容器中（以 list 處理較為方便），最後印出。

1
2
3
4
5
6
7
def traverse(self) -> str:
    curr = self.head
    nodes = []
    while curr:
        nodes.append(curr.val)
        curr = curr.next
    return " -> ".join(str(v) for v in nodes)

查詢節點

1
2
3
4
5
6
7
8
9
def find(self, target: int) -> int:
    curr = self.head
    index = 0
    while curr:
        if curr.val == target:
            return index
        curr = curr.next
        index += 1
    return -1

鏈結串列完整實作

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
33
34
35
36
37
38
39
class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert(self, n0: ListNode, p: ListNode) -> None:
        n1 = n0.next
        p.next = n1
        n0.next = p
    
    def remove(self, n0: ListNode) -> None:
        p = n0.next
        n1 = p.next
        n0.next = n1

    def access(self, index: int) -> ListNode | None:
        curr = self.head
        for _ in range(index):
            if not curr:
                return None
            curr = curr.next
        return curr
    
    def find(self, target: int) -> int:
        curr = self.head
        index = 0
        while curr:
            if curr.val == target:
                return index
            curr = curr.next
            index += 1
        return -1
    
    def traverse(self) -> str:
        curr = self.head
        nodes = []
        while curr:
            nodes.append(curr.val)
            curr = curr.next
        return " -> ".join(str(v) for v in nodes)

練習題

給一個單向鏈結串列的 head，請反轉整條串列，並回傳新的頭節點。

1
2
3
輸入: 1 → 2 → 3 → 4 → 5
輸出: 5
原因: 5 → 4 → 3 → 2 → 1
解答 
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        curr = head
        prev = None
        
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

給一個單向鏈結串列，請找出它的「中間節點」並回傳。若有偶數個節點，回傳第二個中間節點（從 0 開始算）。

1
2
3
4
5
輸入: 1 → 2 → 3 → 4 → 5
輸出: 3

輸入: 1 → 2 → 3 → 4 → 5 → 6
輸出: 4
解答 
1
2
3
4
5
6
7
8
9
class Solution:
    def middleNode(self, head: ListNode | None) -> ListNode | None:
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

這題比較有趣的是需要用到快慢指標 (slow-fast pointer)的概念。我們需要建立兩個指標，slow 與 fast，並且設 slow 一次僅走一步，fast 則走兩步，$t$ 回合後，

  • slow 走了 $t$ 步，落在 $n_{t}$
  • fast 走了 $2t$ 步，落在 $n_{2t}$

因此考慮兩種情況：

$L$ 為奇數

令 $L = 2n + 1$，那麼 $t$ 回合後：

$$
2t = L - 1 \Rightarrow t = \dfrac{L - 1}{2}
$$

節點恰好落在中間節點 $n_{\frac{L - 1}{2}}$。

$L$ 為偶數

令 $L = 2n$，那麼 $t$ 回合後：

$$
2t = L \Rightarrow t = \dfrac{L}{2}
$$

節點恰好落在第 $n + 1$ 個節點 $n_{\frac{L}{2}}$。

因此結論為：
$$
\texttt{slow} =
\begin{cases}
n_{\frac{L-1}{2}}, &\quad\text{if } L \text{ is odd}\\
n_{\frac{L}{2}}, &\quad\text{if } L \text{ is even}
\end{cases}
$$