DSA 連結串列型別
連結串列型別
連結串列有三種基本形式
- 單向連結串列
- 雙向連結串列
- 迴圈連結串列
單向連結串列是最簡單的連結串列型別。它佔用的記憶體空間較少，因為每個節點只有一個指向下一個節點的地址，如下圖所示。
雙向連結串列的節點同時包含指向前一個節點和下一個節點的地址，如下圖所示，因此佔用的記憶體更多。但雙向連結串列適合需要雙向遍歷列表的場景。
迴圈連結串列類似於單向或雙向連結串列，但第一個節點（“頭”）和最後一個節點（“尾”）相互連線。
在單向或雙向連結串列中，我們可以透過檢查連結是否為 null 來找到列表的開始和結束。但對於迴圈連結串列，在某些應用程式中需要更復雜的程式碼來顯式檢查開始和結束節點。
迴圈連結串列適用於需要連續迴圈遍歷的列表。
下圖是一個單向迴圈連結串列的例子
下圖是一個雙向迴圈連結串列的例子
注意：您需要的連結串列型別取決於您要解決的問題。
連結串列實現
以下是基本實現的
- 單向連結串列
- 雙向連結串列
- 迴圈單向連結串列
- 迴圈雙向連結串列
下一頁將介紹連結串列可以執行的不同操作。
1. 單向連結串列實現
以下是此單向連結串列的實現
示例
Python 中的基本單向連結串列
(這是與上一頁底部相同的示例。)
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")2. 雙向連結串列實現
以下是此雙向連結串列的實現
示例
Python 中的基本雙向連結串列
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
print("\nTraversing forward:")
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
print("\nTraversing backward:")
currentNode = node4
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
print("null")3. 迴圈單向連結串列實現
以下是此迴圈單向連結串列的實現
示例
Python 中的基本迴圈單向連結串列
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1
currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("...")第 14 行：這使得單向列表成為迴圈的。
第 17 行：程式透過此方式知道何時停止，以便它只遍歷列表一次。
4. 迴圈雙向連結串列實現
以下是此迴圈雙向連結串列的實現
示例
Python 中的基本迴圈雙向連結串列
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node1.prev = node4
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
node4.next = node1
print("\nTraversing forward:")
currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("...")
print("\nTraversing backward:")
currentNode = node4
startNode = node4
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
print("...")第 13 行和第 22 行：這些連結使雙向連結串列成為迴圈的。
第 26 行：程式透過此方式知道何時停止，以便它只遍歷列表一次。
