在程式設計的世界中，資料結構扮演著至關重要的角色。它們幫助我們以有效率的方式組織和管理資料。
在本篇教程中，我們將深入探討單向鏈表和雙向鏈表這兩種基本資料結構。
鏈表是一種線性資料結構，與陣列不同，它不將資料儲存在連續的記憶體位置。鏈表中的每個元素都稱為節點，這些節點透過指標相互連接。鏈表中的第一個節點被稱為頭節點。
鏈表的大小是動態的，這意味著我們可以根據設備的可用記憶體來增加或減少節點的數量。
鏈表主要分為兩種型別。 讓我們逐一深入了解它們的詳細資訊。
#1. 單向鏈表
單向鏈表中的每個節點都包含一個指向鏈表中下一個節點的指標。因此，每個節點都需要儲存資料以及指向下一個節點的指標。
鏈表的最後一個節點的下一個指標會設定為 null，這表示鏈表的結束。
以下是一個鏈表的示意圖：
現在我們對單向鏈表有了基本的理解。 接下來，讓我們看看如何在 Python 中實作它。
單向鏈表的實作
1. 第一步是建立鏈表的節點。
如何建立呢？
在 Python 中，我們可以透過類別輕鬆建立節點。 類別中會包含節點的資料和指向下一個節點的指標。
以下是節點的程式碼：
class Node:
def __init__(self, data):
## 節點的資料
self.data = data
## 下一個節點的指標
self.next = None
我們可以使用上述類別建立包含任何型別資料的節點。 稍後我們將看到範例。
現在，我們有了節點。 接下來，我們必須建立一個包含多個節點的鏈表。 讓我們為鏈表建立另一個類別。
2. 建立一個名為 LinkedList 的類別，並將頭節點初始化為 None。 請參閱以下程式碼：
class LinkedList:
def __init__(self):
## 將頭節點初始化為 None
self.head = None
3. 我們有了 Node 和 LinkedList 類別。 我們如何將新的節點插入到鏈表中？ 一個簡單的答案是使用 LinkedList 類別中的方法。 是的，這樣做是可行的。 讓我們編寫一個方法來將新的節點插入到鏈表中。
要將新的節點插入到鏈表中，我們必須遵循幾個步驟。
讓我們看看這些步驟：
- 檢查頭節點是否為空。
- 如果頭節點為空，則將新節點指定為頭節點。
- 如果頭節點不為空，則找到鏈表的最後一個節點。
- 將新節點指定為最後一個節點的下一個指標。
讓我們看看在鏈表中插入新節點的程式碼：
class LinkedList:
####
def insert(self, new_node):
## 檢查頭節點是否為空
if self.head:
## 找到最後一個節點
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## 將新節點指定給最後一個節點的下一個指標
last_node.next = new_node
else:
## 頭節點為空
## 將節點指定給頭節點
self.head = new_node
太棒了！ 我們已經完成了將新節點插入鏈表的方法。 我們如何存取鏈表中的節點資料？
要存取鏈表中的資料，我們必須像在插入方法中尋找最後一個節點一樣，使用下一個指標來遍歷鏈表。 讓我們在 LinkedList 類別中編寫一個方法，來印出鏈表中所有節點的資料。
4. 依照以下步驟列印出鏈表中所有節點的資料：
- 使用頭節點初始化一個臨時變數。
- 編寫一個迴圈，重複直到我們到達鏈表的末端。
- 印出節點的資料。
- 移動到下一個指標。
以下是程式碼：
class LinkedList:
####
def display(self):
## 用於遍歷的變數
temp_node = self.head
## 重複直到到達鏈表的末端
while temp_node != None:
## 印出節點的資料
print(temp_node.data, end='->')
## 移動到下一個節點
temp_node = temp_node.next
print('Null')
呼！ 我們已經完成了使用必要方法建立鏈表。 讓我們透過使用一些資料實例化來測試鏈表。
我們可以使用 Node(1) 程式碼來建立節點。 讓我們看看完整的鏈表實作程式碼以及使用範例：
class Node:
def __init__(self, data):
## 節點的資料
self.data = data
## 下一個節點的指標
self.next = None
class LinkedList:
def __init__(self):
## 將頭節點初始化為 None
self.head = None
def insert(self, new_node):
## 檢查頭節點是否為空
if self.head:
## 找到最後一個節點
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## 將新節點指定給最後一個節點的下一個指標
last_node.next = new_node
else:
## 頭節點為空
## 將節點指定給頭節點
self.head = new_node
def display(self):
## 用於遍歷的變數
temp_node = self.head
## 重複直到到達鏈表的末端
while temp_node != None:
## 印出節點的資料
print(temp_node.data, end='->')
## 移動到下一個節點
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## 實例化鏈表
linked_list = LinkedList()
## 將資料插入到鏈表中
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
## 印出鏈表
linked_list.display()
執行上面的程式會得到如下結果：
1->2->3->4->5->6->7->Null
這就是鏈表的運作方式。 現在，您知道如何實作單向鏈表了。 有了單向鏈表的知識，您就可以輕鬆實作雙向鏈表。 讓我們深入本教程的下一部分。
#2. 雙向鏈表
雙向鏈表中的每個節點包含兩個指標：一個指向鏈表中前一個節點，另一個指向下一個節點。 因此，每個節點都需要儲存資料，以及兩個指標。
第一個節點的前一個指標為 null，最後一個節點的下一個指標為 null，這表示鏈表在兩側的結束。
以下是一個鏈表的示意圖：
雙向鏈表的實作步驟與單向鏈表類似。 再次解釋相同的事情對您來說可能會很無聊。 讓我們直接瀏覽程式碼，您會很快理解的。 開始吧！
雙向鏈表的實作
1. 建立一個雙向鏈表的節點，其中包含前一個節點的指標、資料和下一個節點的指標。
class Node:
def __init__(self, data):
## 前一個節點的指標
self.prev = None
## 節點的資料
self.data = data
## 下一個節點的指標
self.next = None
2. 雙向鏈表類別。
class LinkedList:
def __init__(self):
## 將頭節點初始化為 None
self.head = None
3. 將新節點插入到雙向鏈表的方法。
class LinkedList:
####
def insert(self, new_node):
## 檢查頭節點是否為空
if self.head:
## 找到最後一個節點
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## 將最後一個節點指定給新節點的前一個指標
new_node.prev = last_node
## 將新節點指定給最後一個節點的下一個指標
last_node.next = new_node
4. 雙向鏈表的資料顯示方法。
class LinkedList:
####
def display(self):
## 按正常順序印出資料
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## 使用前一個指標按相反順序印出資料
print("Reverse Order: ", end='')
## 找到最後一個節點
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
我們已經看到了雙向鏈表的程式碼。 但沒有使用雙向鏈表類別的程式碼。 這留給您來完成。 請使用類似於單向鏈表的方式來實作雙向鏈表類別。 玩得開心！ 🙂
結論
您可以根據鏈表找到許多問題。 但是，您必須了解在本教程中學到的鏈表基本實作。 希望您在學習新概念的過程中玩得開心。
快樂編碼！🙂