溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
怎么在Python中實現一個單鏈表？針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
鏈表（Linked List）是由許多相同數據類型的數據項按照特定順序排列而成的線性表。
鏈表中個數據項在計算機內存中的位置是不連續且隨機的，數組在內存中是連續的。
鏈表數據的插入和刪除很方便，但查找數據效率低下，不能像數組一樣隨機讀取數據。
一個單向鏈表的節點由數據字段和指針組成，指針指向下一個元素所在內存地址
定義一個鏈表節點類,self.value實例屬性表示節點數據字段；self.next表示指針；初始化值為None
class Node(object): def __init__(self, value=None, next=None): self.value = value self.next = next
在單鏈表中第一個節點為頭(head)指針節點(即頭指針指向的節點為單鏈表第一個節點，后續簡稱頭指針節點)，從頭指針節點出發可以遍歷整個鏈表，進行元素查找，插入和刪除，非常重要。一般不移動head頭指針。
單鏈表中最后一個節點為尾節點，其指針為None，表示結束。
建立單鏈表我們首先需要創建頭指針節點（引入頭指針是為了方便操作單鏈表，對于頭指針節點，只有指針域指向鏈表第一個節點，不含實際值）
class linkedList(object): def __init__(self): self.head = Node() # 創建頭指針結點 self.length = 0 # 初始鏈表長度，頭指針節點不計入長度 def __len__(self): # 重寫特殊方法返回self.length return self.length
鏈表初始化之后，開始定義鏈表方法
鏈表頭部插入節點：
待插入節點指向原頭指針節點，頭指針重新指向待插入節點
首先需要將原頭指針結點，存放到臨時變量中(防止head指針變更時，指針斷裂導致數據丟失，鏈表中指針就是連接的紐帶，其中某個紐帶斷裂(即指針指向其他)則后續數據都將丟失)
將頭指針指向新插入節點
新插入節點指針指向原頭指針節點
長度+1
插入節點既是鏈表頭指針指向的節點也是尾節點(指向None)
調用Node()傳入待插入的值value創建待插入節點
判斷當前鏈表是否為空鏈表，鏈表為空：
鏈表不為空：
def head_insert(self, value): # 鏈表頭部插入 node = Node(value) if self.head.next == None: self.head.next = node node.next = None else: # 插入元素指針域指向原head元素 tmp_head = self.head.next # 原頭指針節點存儲到tmp_head self.head.next = node # 新head指針指向node node.next = tmp_head # 新插入節點指向原頭指針節點 self.length += 1
鏈表頭部刪除節點：
頭指針指針域(指針域存放下一節點的內存地址，即頭指針節點)指向頭指針，也就是說鏈表第一個節點變成了頭指針head，由于head不計入鏈表，所以就相當于刪除了第一個節點(有點繞)
同時返回刪除的值
依舊是先判斷鏈表是否為空，為空則返回False
鏈表不為空時：
def head_del(self): # 刪除頭結點,返回頭結點的值 if self.head.next == None: return False else: # 頭指針指針域指向自己 self.head = self.head.next self.length -= 1 return self.head.value
鏈表尾部添加節點：
首先通過while循環(循環條件為節點指針是否為None)找到當前鏈表的最后一個元素
然后將當前最后一個元素指向待插入節點
長度+1
創建待插入節點對象
判斷鏈表是否為空，為空則頭指針節點就是待插入節點，也是尾節點
鏈表不為空：
def append(self, value): # 鏈表尾部添加結點 # 創建新插入的結點對象 node = Node(value) if self.length == 0: self.head.next = node # 只有一個節點，指針指向自己 else: curnode = self.head.next # 變量curnode存放指針 while curnode.next != None: curnode = curnode.next curnode.next = node # 當為最后一個節點時，指針指向新插入節點 self.length += 1
指定位置后面插入節點：
首先定義一個變量表示當前節點，以及一個index索引比較數i
使用while循環，索引比較數i != index時，更新當前節點
找到索引位置節點后，首先讓插入節點指向索引位置節點的下一個節點
然后讓索引位置節點指向插入節點
鏈表長度+1
這里方法接受兩個位置參數，index插入位置和value插入值
依舊創建新節點對象
判斷是否為空
在鏈表不為空的條件下：
def insert(self, index, value): node = Node(value) if self.length == 0: self.head.next = node else: i = 0 cur_node = self.head.next while i != index: cur_node = cur_node.next i += 1 node.next = cur_node.next cur_node.next = node self.length += 1
給定值刪除該值節點：
設置一個前驅節點(當找到需要刪除的節點時，先讓前驅節點指向刪除節點的后繼節點)
for循環遍歷鏈表
找到符合條件的值就讓前驅節點指向，刪除節點的后繼節點，然后del刪除node，Flag更改為True
沒找到符合條件的值，就更新前驅節點，繼續遍歷
刪除鏈表中給定的值我們需要遍歷整個鏈表，因此需要創建一個可迭代對象
定義節點迭代方法
def iter_node(self): cur_node = self.head.next #當前節點 while cur_node.next != None: # 對除最后一個節點進行可迭代化處理 yield cur_node cur_node = curnode.next if cur_node.next == None: # 對尾節點進行可迭代化處理 yield cur_node
重寫特殊方法–iter–，用來聲明這個類是一個迭代器
def __iter__(self): # 遍歷列表節點 for node in self.iter_node(): yield node.value
首先定義一個Flag變量(默認為False)，用來表示刪除狀態
依舊判斷鏈表是否為空
鏈表不為空時：
def delete_node(self, value): Flag = False if self.length == 0: return False else: previous_node = self.head # 初始化前置節點為頭結點 for node in self.iter_node(): if node.value == value: previous_node.next = node.next # 前置節點指針指向當前節點的后繼節點 del node self.length -= 1 Flag = True else: previous_node = node # 更新前置節點的值 return Flag
完整代碼：
# 定義鏈表節點類
class Node(object):
def __init__(self, value=None, next=None):
self.value = value # 節點元素
self.next = next # 指針
# 單鏈表類
class LinkedList(object):
def __init__(self):
self.head = Node() # 創建頭結點
self.length = 0 # 初始化鏈表長度
def __len__(self):
return self.length
def __iter__(self): # 遍歷列表節點
for node in self.iter_node():
yield node.value
def iter_node(self):
curnode = self.head.next
while curnode.next != None:
yield curnode
curnode = curnode.next
if curnode.next == None:
yield curnode
def head_insert(self, value): # 鏈表頭部插入
node = Node(value)
if self.head.next == None:
self.head.next = node
node.next = None
else:
# 插入元素指針域指向原head元素
tmp_head = self.head.next # 原頭指針節點存儲到tmp_head
self.head.next = node # 新head指針指向node
node.next = tmp_head # 新插入節點指向原頭指針節點
self.length += 1
def head_del(self): # 刪除頭結點,返回頭結點的值
if self.head.next == None:
return False
else:
# 頭指針指針域指向自己
self.head = self.head.next
self.length -= 1
return self.head.value
def append(self, value): # 鏈表尾部添加結點
# 創建新插入的結點對象
node = Node(value)
if self.length == 0:
self.head.next = node # 只有一個節點，指針指向自己
else:
curnode = self.head.next # 變量curnode存放指針
while curnode.next != None:
curnode = curnode.next
curnode.next = node # 當為最后一個節點時，指針指向新插入節點
self.length += 1
# 這里的insert是指定值后面插入不是指定位置
def insert(self, index, value):
node = Node(value)
if self.length == 0:
self.head.next = node
self.length += 1
else:
for nd in self.iter_node():
if nd.value == index: # 如果nd節點值等于index，則插入到nd后
tmp_node = nd.next # 將nd的指針存放到中間變量
nd.next = node # nd節點指向插入節點
node.next = tmp_node # 插入節點指向原nd.next節點
self.length += 1
return True
return False
def replace(self, old_value, new_value):
index = 0
if self.length == 0:
return False
else:
for node in self.iter_node():
if node == old_value:
node.value = new_value
index += 1
if index != 0:
return index # 替換節點數量(存在節點值相同情況)
else:
return False # 替換失敗，未找到替換值
def delete_node(self, value):
Flag = False
if self.length == 0:
return False
else:
previous_node = self.head # 初始化前置節點為頭結點
for node in self.iter_node():
if node.value == value:
previous_node.next = node.next # 前置節點指針指向當前節點的后繼節點
del node
self.length -= 1
Flag = True
else:
previous_node = node # 更新前置節點的值
return Flag
# 測試
l = LinkedList()
l.append(1)
l.append(2)
l.append(7)
l.append(5)
l.append(6)
l.append(7)
l.head_insert(3)
print("當前鏈表長度：%s" %l.length)
#print("刪除頭結點為：%d"% l.head_del())
print("當前鏈表長度：%s" %l.length)
i = 1
#l.delete_node(7)
for node in l:
print("第%d個鏈表節點的值: %d"%(i, node))
i += 1
運行結果：
當前鏈表長度：7
當前鏈表長度：7
第1個鏈表節點的值: 3
第2個鏈表節點的值: 1
第3個鏈表節點的值: 2
第4個鏈表節點的值: 7
第5個鏈表節點的值: 5
第6個鏈表節點的值: 6
第7個鏈表節點的值: 7
關于怎么在Python中實現一個單鏈表問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
