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