五分鐘搞懂鏈表實現：Python數據結構與算法
作者：子午Python
鏈表的主要優勢在于插入和刪除操作的效率高，不需要移動其他元素。不過，鏈表的隨機訪問速度比數組慢，因為需要從頭節點開始遍歷。
鏈表是一種由節點組成的線性數據結構，每個節點包含一個數據元素和一個指向下一個節點的指針。
1.鏈表的基本概念
(1)節點定義
鏈表中的每一個元素都是一個節點，每個節點通常包含兩部分：數據和下一個節點的引用。
class Node:
def __init__(self, data):
self.data = data # 節點存儲的數據
self.next = None # 默認下一個節點為空(2)鏈表定義
鏈表通常有一個頭節點來表示鏈表的開始。尾節點是鏈表中的最后一個節點，它的下一個節點引用為None。
class LinkedList:
def __init__(self):
self.head = None # 初始鏈表為空2.向鏈表中添加元素
(1)在鏈表的開頭添加元素
def add_first(self, data):
new_node = Node(data) # 創建新的節點
new_node.next = self.head # 將新節點指向當前的頭節點
self.head = new_node # 更新頭節點為新節點
LinkedList.add_first = add_first(2)在鏈表的結尾添加元素
def add_last(self, data):
new_node = Node(data)
if self.head is None: # 若鏈表為空，則直接將新節點設置為頭節點
self.head = new_node
return
last_node = self.head # 遍歷到鏈表的尾部
while last_node.next:
last_node = last_node.next
last_node.next = new_node # 在鏈表尾部添加新節點
LinkedList.add_last = add_last3.從鏈表中刪除元素
(1)刪除鏈表的第一個元素
def remove_first(self):
if self.head:
self.head = self.head.next # 更新頭節點為下一個節點
LinkedList.remove_first = remove_first(2)刪除鏈表的最后一個元素
def remove_last(self):
if self.head is None: # 若鏈表為空，直接返回
return
if self.head.next is None: # 若鏈表只有一個元素，將頭節點設置為空
self.head = None
return
second_to_last = self.head # 找到倒數第二個節點
while second_to_last.next.next:
second_to_last = second_to_last.next
second_to_last.next = None # 將倒數第二個節點的next設置為空，從而刪除最后一個節點
LinkedList.remove_last = remove_last4.遍歷鏈表
def print_list(self):
current_node = self.head # 從頭節點開始遍歷
while current_node:
print(current_node.data, end=" -> ")
current_node = current_node.next # 移動到下一個節點
print("None")
LinkedList.print_list = print_list5.查找鏈表中的元素
def search(self, target):
current_node = self.head # 從頭節點開始遍歷
while current_node:
if current_node.data == target: # 若找到目標數據，返回True
return True
current_node = current_node.next # 移動到下一個節點
return False # 遍歷完鏈表后，未找到目標數據，返回False
LinkedList.search = search6.實戰案例：反轉鏈表 一個常見的面試問題是如何反轉鏈表。我們可以使用迭代的方法來解決這個問題。
def reverse(self):
prev = None # 上一個節點
current = self.head # 當前節點
while current:
next_node = current.next # 記錄下一個節點
current.next = prev # 將當前節點指向上一個節點
prev = current # 更新上一個節點為當前節點
current = next_node # 移動到下一個節點
self.head = prev # 更新頭節點
LinkedList.reverse = reverse
# 使用示例
ll = LinkedList()
ll.add_last(1)
ll.add_last(2)
ll.add_last(3)
ll.print_list() # 輸出：1 -> 2 -> 3 -> None
ll.reverse()
ll.print_list() # 輸出：3 -> 2 -> 1 -> None小結
鏈表提供了一種在內存中存儲有序元素的方法，它的主要優勢在于插入和刪除操作的效率高，不需要移動其他元素。不過，鏈表的隨機訪問速度比數組慢，因為需要從頭節點開始遍歷。理解鏈表的結構和常用操作是計算機科學基礎，也經常用于面試中。
責任編輯：趙寧寧
來源：
子午Python
