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