DSA 連結串列操作
連結串列操作
我們可以對連結串列進行的一些基本操作是：
- 遍歷
- 刪除節點
- 插入節點
- 排序
為簡單起見，下面的操作將使用單向連結串列來解釋。
遍歷連結串列
遍歷連結串列意味著透過跟蹤從一個節點到下一個節點的連結來遍歷連結串列。
遍歷連結串列通常是為了搜尋特定節點，讀取或修改節點的內容，刪除節點，或在該節點之前或之後插入節點。
要遍歷單向連結串列，我們從連結串列的第一個節點（頭節點）開始，然後跟蹤該節點的下一個連結，再跟蹤下一個節點的下一個連結，依此類推，直到下一個地址為 null，如下面的動畫所示。
下面的程式碼將打印出遍歷連結串列時的節點值，與上面的動畫相同。
示例
Python 中單向連結串列的遍歷
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
traverseAndPrint(node1)查詢連結串列中的最小值
讓我們透過遍歷單向連結串列並檢查每個值來查詢其中的最小值。
查詢連結串列中的最小值與我們在陣列中查詢最小值的方式非常相似，只是我們需要跟蹤下一個連結才能到達下一個節點。
原則上，查詢連結串列中的最小值的工作方式如下：
最小值：
要查詢最小值，我們需要像前面的程式碼那樣遍歷連結串列。但除了遍歷連結串列之外，當我們找到一個值更小的節點時，我們還必須更新當前最小值。
在下面的程式碼中，查詢最小值的演算法被移入一個名為 findLowestValue 的函式中。
示例
Python 中單向連結串列查詢最小值
class Node:
def __init__(self, data):
self.data = data
self.next = None
def findLowestValue(head):
minValue = head.data
currentNode = head.next
while currentNode:
if currentNode.data < minValue:
minValue = currentNode.data
currentNode = currentNode.next
return minValue
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("The lowest value in the linked list is:", findLowestValue(node1))上面標記的行是演算法的核心。初始最小值被設定為第一個節點的值。然後，如果找到更小的值，則會更新最小值變數。
執行示例 »刪除連結串列中的節點
在這種情況下，我們擁有想要刪除的節點的連結（或指標或地址）。
在刪除節點之前，必須連線其兩側的節點，以免連結串列斷裂。
因此，在刪除節點之前，我們需要獲取前一個節點的下一個指標，並將前一個節點連線到新的下一個節點，然後再刪除中間的節點。
在單向連結串列中，就像我們這裡處理的，要獲取前一個節點的下一個指標，實際上需要從頭開始遍歷連結串列，因為無法從要刪除的節點向後移動。
下面的模擬顯示了我們要刪除的節點，以及在不破壞連結串列的情況下如何必須先遍歷連結串列才能正確連線連結串列，然後再刪除節點。
此外，最好在刪除節點之前，先將其下一個指標連線到刪除節點之後的節點。這是為了避免“懸空”指標，即即使只是短暫地指向空值。
在下面的程式碼中，刪除節點的演算法被移入一個名為 deleteSpecificNode 的函式中。
示例
Python 中單向連結串列刪除特定節點
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
def deleteSpecificNode(head, nodeToDelete):
if head == nodeToDelete:
return head.next
currentNode = head
while currentNode.next and currentNode.next != nodeToDelete:
currentNode = currentNode.next
if currentNode.next is None:
return head
currentNode.next = currentNode.next.next
return head
node1 = Node(7)
node2 = Node(11)
node3 = Node(3)
node4 = Node(2)
node5 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print("Before deletion:")
traverseAndPrint(node1)
# Delete node4
node1 = deleteSpecificNode(node1, node4)
print("\nAfter deletion:")
traverseAndPrint(node1)在上面的 deleteSpecificNode 函式中，返回值是連結串列的新頭部。例如，如果要刪除的節點是第一個節點，則返回的新頭部將是下一個節點。
插入連結串列中的節點
將節點插入連結串列與刪除節點非常相似，因為在兩種情況下，我們都需要處理下一個指標，以確保不會破壞連結串列。
要在連結串列中插入節點，我們首先需要建立節點，然後在插入它的位置，我們需要調整指標，以便前一個節點指向新節點，新節點指向正確的下一個節點。
下面的模擬顯示了插入新節點時連結是如何調整的。
- 建立新節點
- 節點 1 連線到新節點
- 新節點連線到下一個節點
示例
Python 中單向連結串列插入節點
class Node:
def __init__(self, data):
self.data = data
self.next = None
def traverseAndPrint(head):
currentNode = head
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
def insertNodeAtPosition(head, newNode, position):
if position == 1:
newNode.next = head
return newNode
currentNode = head
for _ in range(position - 2):
if currentNode is None:
break
currentNode = currentNode.next
newNode.next = currentNode.next
currentNode.next = newNode
return head
node1 = Node(7)
node2 = Node(3)
node3 = Node(2)
node4 = Node(9)
node1.next = node2
node2.next = node3
node3.next = node4
print("Original list:")
traverseAndPrint(node1)
# Insert a new node with value 97 at position 2
newNode = Node(97)
node1 = insertNodeAtPosition(node1, newNode, 2)
print("\nAfter insertion:")
traverseAndPrint(node1)在上面的 insertNodeAtPosition 函式中，返回值是連結串列的新頭部。例如，如果節點插入到連結串列的開頭，返回的新頭部將是新節點。
其他連結串列操作
我們上面只介紹了三個基本的連結串列操作：遍歷（或搜尋）、節點刪除和節點插入。
還有很多其他操作可以對連結串列進行，例如排序。
在本教程的前面，我們已經介紹了許多排序演算法，並且也可以在連結串列上執行其中許多排序演算法。以選擇排序為例。在選擇排序中，我們找到最小值，將其刪除，然後將其插入到開頭。我們也可以對連結串列執行相同的操作，對嗎？我們剛剛已經看過如何遍歷連結串列、如何刪除節點以及如何插入節點。
注意：我們不能使用計數排序、基數排序或快速排序等排序演算法對連結串列進行排序，因為它們使用索引直接基於位置修改陣列元素。
連結串列與陣列
這些是連結串列的一些關鍵屬性，與陣列相比：
- 連結串列不像陣列那樣在記憶體中分配固定大小，因此當固定記憶體空間滿時，連結串列不需要將整個連結串列移動到更大的記憶體空間，而陣列則必須這樣做。
- 連結串列節點在記憶體中不是一個接一個（連續）排列的，因此當插入或刪除節點時，連結串列節點不必在記憶體中向上或向下移動。
- 連結串列節點需要更多的記憶體來儲存一個或多個指向其他節點的連結。陣列元素不需要那麼多記憶體，因為陣列元素不包含指向其他元素的連結。
- 連結串列操作通常比類似的陣列操作更難程式設計，並且需要更多的程式碼行，因為程式語言對陣列有更好的內建支援。
- 我們必須遍歷連結串列才能找到特定位置的節點，但對於陣列，我們可以透過編寫 myArray[5] 直接訪問元素。
注意：在 Java 或 Python 等程式語言中使用陣列時，儘管我們不需要編寫程式碼來處理陣列記憶體空間已滿的情況，並且在刪除或插入元素時不需要在記憶體中向上或向下移動元素，但這些操作仍在後臺發生，並可能在對時間要求嚴格的應用程式中引起問題。
連結串列操作的時間複雜度
在此，我們討論連結串列操作的時間複雜度，並將其與本教程前面討論的陣列演算法的時間複雜度進行比較。
請記住，時間複雜度只是說明演算法根據大量資料 \(n\) 所需的運算元，而不能告訴我們特定演算法實現的精確時間。
這意味著，即使線性搜尋對於陣列和連結串列的時間複雜度相同：\(O(n)\)，也不意味著它們花費的時間相同。演算法執行的確切時間取決於程式語言、計算機硬體、陣列與連結串列操作所需時間的差異以及許多其他因素。
線性搜尋對於連結串列的工作方式與對於陣列相同。遍歷一個無序值列表，從頭節點開始，直到找到具有特定值的節點。時間複雜度為 \(O(n)\)。
二分搜尋不適用於連結串列，因為該演算法基於直接跳轉到不同的陣列元素，而這在連結串列中是不可能的。
排序演算法與陣列的時間複雜度相同，這些演算法已在本教程前面進行了說明。但請記住，基於直接按索引訪問陣列元素的排序演算法不適用於連結串列。
