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