資結筆記｜鏈結串列（linked list）

發佈於資結

2025/03/31 更新2025/03/31 發佈閱讀 8 分鐘

基本觀念

鏈結串列（linked list）表面上也是一串數列，但與陣列不同的地方是，陣列的資料元素是在記憶體的連續空間，鏈結串列的資料是散落在記憶體的各處。而我們會將存放資料的地方稱為節點，每個節點包含2個區塊，一個區塊是資料區用來存放數據，另一個區塊是指標區用來指向下一個節點元素。

下列是一個鏈結串列含有3個節點，要存放的內容為dog、cat、fish，我們來看看這個鏈結串列的外觀，如下圖，

而實際上，因為鏈結串列是分散在記憶體的各處，所以有可能不是連續排列的，如下圖。但透過指標，可以將分散在各處的資料連結在一起。

資料讀取

鏈結串列讀取資料使用的是循序讀取（sequential access），必須得從頭開始讀取資料。以上面的鏈結陣列舉例，假設要讀取FISH，得先經過DOG->CAT->FISH，按照順序才能取得FISH的資料，因為要跑完整個串列，所以時間複雜度為O(n)。

新增＆刪除節點元素

在新增節點時，不需要搬動整個串列的資料，只需要將前一個元素的指標指向新元素，並將新元素的指標指向原本的下一個元素。例如我要將APPLE插入CAT和FISH中間，只要先將CAT指向APPLE(CAT->APPLE)，然後再將APPLE指向FISH(APPL->FISH)，即可形成DOG->CAT->APPLE->FISH，新的鏈結串列。

刪除節點也是同樣的道理，只要將欲刪除的節點的前一個節點的指標，指向下一個節點，讓這個鏈結串列無法走到想刪除的節點，就算完成刪除節點的動作了。

循環鏈結串列

在鏈結串列中有頭尾的觀念，搜尋時必須從頭至尾，但如果我們將最尾端的節點指向第一個節點，使它成為一個循環，就稱為循環鏈結串列。見下圖，這樣設計的好處是不管目前指標示指向哪一個節點，都可以搜尋整個串列，不會因為指到到尾巴而中止。

陣列與鏈結串列時間複雜度比較

由上述表格可知，不同的資料結構有各自的優缺點，會影響不同操作的時間複雜度，因此未來在設計程式時，可以根據需求決定要使用哪一種資料結構。

鏈結串列程式實作

推薦大家一個實作程式碼可以使用的工具python tutor，不用特別安裝可以及時修改，還可以看到視覺化的資料結構，推薦初學者使用。

建立鏈結串列

class Node():
    def __init__ (self, data=None):
        self.data = data                    #資料data
        self.next = None                    #指標pointer
        

p1 = Node(7)                                #節點1
p2 = Node(9)                                #節點2
p3 = Node(11)                               #節點3

p1.next = p2                                #節點1指向節點2
p2.next = p3                                #節點2指向節點3

# 設定頭節點
head = p1

# 輸出鏈結串列的內容
ptr = head
while ptr:
    print(ptr.data, end=" -> ")
    ptr = ptr.next
print("None")                       #移動指標到下一個節點

可以從上面的程式碼看到Node類別有兩個屬性，data是用來儲存節點的資料，next是用來儲存指標，指標會指向下一個節點。第一個節點為頭節點用head設定，如果陣列結束了就指向None，執行結果如下圖，

插入新節點在開頭

假設我要將一筆資料5插入這個鏈結串列成為新的頭節點，只需要新增一個節點（p0）並指向原本的頭節點（p1），並將新建的節點（p0）指定為新的頭節點。

class Node:
    def __init__(self, data=None):
        self.data = data  # 節點儲存的資料
        self.next = None  # 下一個節點的指標（預設為 None）

# 創建初始的鏈結串列節點
p1 = Node(7)  # 節點1
p2 = Node(9)  # 節點2
p3 = Node(11) # 節點3

# 串接節點
p1.next = p2  # 節點1指向節點2
p2.next = p3  # 節點2指向節點3

# 新增節點到鏈結串列的最前面
p0 = Node(5)  # 新的節點
p0.next = p1  # 新節點指向原本的第一個節點

# 設定新的頭節點
head = p0

# 輸出鏈結串列的內容
ptr = head
while ptr:
    print(ptr.data, end=" -> ")
    ptr = ptr.next
print("None")

執行結果如下圖，

插入新節點在中間

假設我要再新增一筆資料8在節點p1和p2中間，只需要新增一個節點（p4），將p1指向p4，再將p4指向P2則可以完成。

class Node:
    def __init__(self, data=None):
        self.data = data  # 節點儲存的資料
        self.next = None  # 下一個節點的指標（預設為 None）

# 創建初始的鏈結串列節點
p0 = Node(5) 
p1 = Node(7)  # 節點1
p2 = Node(9)  # 節點2
p3 = Node(11) # 節點3

# 新增節點在鏈結串列中間
p4 = Node(8)  # 節點4 

# 串接節點
p0.next = p1
p1.next = p4  # 節點1指向節點4
p2.next = p3  
p4.next = p2  # 節點4指向節點2
# 設定頭節點

head = p0

# 輸出鏈結串列的內容

ptr = head

while ptr:

print(ptr.data, end=" -> ")

ptr = ptr.next

print("None")

建立循環鏈結串列

我們要建立一個循環連結只需將p3再指向p0即可，但輸出的時候要加入一個檢查機制，如果回到頭節點了則停止輸出，以避免無窮迴圈。

class Node:
    def __init__(self, data=None):
        self.data = data  # 節點儲存的資料
        self.next = None  # 下一個節點的指標（預設為 None）

# 創建初始的鏈結串列節點
p0 = Node(5)  # 節點0
p1 = Node(7)  # 節點1
p2 = Node(9)  # 節點2
p3 = Node(11) # 節點3

# 新增節點在鏈結串列中間
p4 = Node(8)  # 節點4

# 串接節點
p0.next = p1      # 節點0指向節點1
p1.next = p4      # 節點1指向節點4
p4.next = p2      # 節點4指向節點2
p2.next = p3      # 節點2指向節點3
p3.next = p0      # 節點3指向節點0，形成循環鏈結串列

# 設定頭節點
head = p0

# 輸出循環鏈結串列的內容

ptr = head
while True:
    print(ptr.data, end=" -> ")
    ptr = ptr.next
    if ptr == head:  # 如果回到頭節點，停止遍歷
        break
print(ptr.data, "(回到頭節點)")