Python雙向鏈表插入節(jié)點(diǎn)方式
更新時間：2023年06月13日 09:17:29 作者：城俊BLOG
這篇文章主要介紹了Python雙向鏈表插入節(jié)點(diǎn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
Python雙向鏈表插入節(jié)點(diǎn)
# 定義一個鏈表節(jié)點(diǎn) class Node(): def __init__(self,data=None): self.val = data self.pre = None self.next = None # 定義雙向鏈表 class biLinkedList(): def __init__(self): self.head = None # 獲取鏈表長度 def length(self): curr = self.head count = 0 while curr != None: count += 1 curr = curr.next return count # 插入節(jié)點(diǎn) def insert(self,index,data): node = Node(data) # 在頭部插入 if index <= 0: # 如果鏈表為空 if self.head == None: self.head = node else: node.next = self.head # 節(jié)點(diǎn)下一個指向head self.head.pre = node # head的上一個指向node self.head = node # head指向node # 在尾部插入 elif index > self.length-1: if self.head == None: self.head = node else: # 將指針移動到鏈表尾部 curr = self.head while curr.next != None: curr = curr.next curr.next = node # 尾節(jié)點(diǎn)的下一個指向節(jié)點(diǎn) node.prev = curr # 節(jié)點(diǎn)的上一個指向尾節(jié)點(diǎn) # 在中間插入 else: curr = self.head count = 0 # 將指針移動到要插入位置的前一個位置 while count < index-1: count += 1 curr = curr.next node.pre = curr # 節(jié)點(diǎn)的上一個指向當(dāng)前 node.next = curr.next # 節(jié)點(diǎn)的下一個指向當(dāng)前下一個 curr.next.pre = node # 當(dāng)前的下一個的上一個指向節(jié)點(diǎn) curr.next = node # 當(dāng)前的下一個指向節(jié)點(diǎn) # https://jackkuo666.github.io/Data_Structure_with_Python_book/chapter3/section3.html # https://blog.csdn.net/qq490691606/article/details/49948263 (insert不能實(shí)現(xiàn)在尾部插入節(jié)點(diǎn))
Python實(shí)現(xiàn)鏈表---雙向鏈表
分析
雙向鏈表
add方法：向鏈表的頭部添加一個節(jié)點(diǎn) data
append方法：向鏈表的尾部添加一個節(jié)點(diǎn)， 值為data
insert方法：向指定位置添加節(jié)點(diǎn)，值為data
remove方法：刪除鏈表中第一個值為data的節(jié)點(diǎn)
代碼
class Node: # 鏈表的節(jié)點(diǎn)類
def __init__(self, data, _prev=None, _next=None):
self.prev = _prev #指針域 指向的是當(dāng)前節(jié)點(diǎn)的前一個節(jié)點(diǎn)
self.data = data # 數(shù)據(jù)域
self.next = _next # 指針域 指向的是當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)
class DoubleLinkList:
def __init__(self):
self.head = None # 頭結(jié)點(diǎn)
self._length = 0 # 長度
def is_empty(self):
#鏈表是否為空
return self._length == 0
def length(self):
# 鏈表長度
return self._length
def nodes_list(self):
# 返回鏈表中的所有節(jié)點(diǎn)的值組成的列表
ls = []
cur = self.head
while cur != None: # cur = None時找到尾結(jié)點(diǎn)
ls.append(cur.data)
cur = cur.next # 鏈表不為空時繼續(xù)向后
return ls # 返回鏈表
def add(self, data):
# 向鏈表的頭部添加一個節(jié)點(diǎn) data
node = Node(data) # 新建一個節(jié)點(diǎn)
if self.is_empty():#鏈表為空
self.head = node
else:#鏈表不為空
self.head.prev = node #1 讓鏈表中原本得頭結(jié)點(diǎn)prev指向新建節(jié)點(diǎn)
# 如果鏈表為空時self.head = None 無法調(diào)用None.prev
node.next = self.head # 2讓node指向當(dāng)前鏈表中的頭結(jié)點(diǎn)
self.head = node # 3再讓鏈表的head指向當(dāng)前node節(jié)點(diǎn)
self._length += 1 # 添加節(jié)點(diǎn) 鏈表長度+1
def append(self, data):
# 向鏈表的尾部添加一個節(jié)點(diǎn)， 值為data
# 新建一個節(jié)點(diǎn)node, 值為data
node = Node(data)
if self.head != None: # 鏈表不為空 有元素
cur = self.head
# 鏈表為空時，self.head 為None 無法執(zhí)行循環(huán)中的.next while cur.next != None: #cur.next = None時找到尾結(jié)點(diǎn)
# 找到鏈表的尾節(jié)點(diǎn)
# 從頭結(jié)點(diǎn)開始，遍歷鏈表中所有的結(jié)點(diǎn)
# 每次判斷當(dāng)前節(jié)點(diǎn)的next是否為空
# 為空說明當(dāng)前節(jié)點(diǎn)就是尾結(jié)點(diǎn)
# 不為空時，通過當(dāng)前節(jié)點(diǎn)得next去訪問下一個節(jié)點(diǎn)
while cur.next != None: # cur.next = None時找到尾結(jié)點(diǎn)cur
cur = cur.next
# 讓當(dāng)前的尾節(jié)點(diǎn)得指針域指向node
node.prev = cur #讓node的prev指向原本的尾節(jié)點(diǎn)
cur.next = node # 讓原本的尾節(jié)點(diǎn)的next去指向新建的節(jié)點(diǎn)
# 添加完畢，鏈表的長度+1
else: # 空鏈表
self.head = node
self._length += 1
def insert(self, pos, data):
# 向指定位置添加節(jié)點(diǎn)，值為data
# 異常情況 超出邊界
if pos <= 0:
self.add(data)
elif pos >= self._length:
self.append(data)
else:
node = Node(data) # 1
cur = self.head
n = 0 # 2找鏈表中索引為pos-1的節(jié)點(diǎn)（0,1,2）， cur = cur.next 執(zhí)行pos-1步
while n < pos - 1:
cur = cur.next
n = n + 1
# 到這里cur指向的是索引為pos-1 的節(jié)點(diǎn)
# 1新的節(jié)點(diǎn)node的prev指向索引為pos -1的節(jié)點(diǎn)
node.prev = cur
# 2鏈表中原本索引為pos的節(jié)點(diǎn)prev指向新的節(jié)點(diǎn)node
cur.next.prev = node
# 3新的節(jié)點(diǎn)node的next指向鏈表中原本索引為pos的節(jié)點(diǎn)
node.next = cur.next # cur.next 為pos的節(jié)點(diǎn)
# 4讓索引為pos-1的節(jié)點(diǎn)得next指向node
cur.next = node
self._length += 1 # 5 長度+1
def remove(self, data):
# 刪除鏈表中第一個值為data的節(jié)點(diǎn)
cur = self.head
while cur:
if cur.data == data:#找到要刪的節(jié)點(diǎn)
# 如果前驅(qū)節(jié)點(diǎn)為空， 說明我們要刪除的節(jié)點(diǎn)是第一個節(jié)點(diǎn)
if cur == self.head:#刪的是第一個結(jié)點(diǎn)
self.head = cur.next # 指向第二個節(jié)點(diǎn)
self.head.prev = None
else: # 要刪除的不是第一個節(jié)點(diǎn)
cur.prev.next = cur.next #要刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)的next指向要刪除節(jié)點(diǎn)的后一個節(jié)點(diǎn)
#如要刪除的節(jié)點(diǎn)為最后一個節(jié)點(diǎn)，只需執(zhí)行這一步
if cur.next != None:#判斷cur.next是否存在
cur.next.prev = cur.prev #要刪除節(jié)點(diǎn)的下一節(jié)點(diǎn)的prev指向要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
self._length -= 1
return 0 # 找到
cur = cur.next # 繼續(xù)向后
return -1 # 沒有找到
def modify(self, pos, data):
# 修改鏈表中指定位置的節(jié)點(diǎn)
if pos < 0 or pos >= self._length:
print("位置不正確") # 位置不正確
else:
cur = self.head
n = 0 # 找鏈表中索引為pos的節(jié)點(diǎn)（0,1,2）， cur = cur.next 執(zhí)行pos-1步
while n < pos:
cur = cur.next
n = n + 1
cur.data = data
def search(self, data):
# 查找鏈表中是否有節(jié)點(diǎn)的值為data
cur = self.head
while cur:
if cur.data == data:
return True # 找到
cur = cur.next # 繼續(xù)向后
return False # 沒有找到
if __name__ == "__main__":
l1 = DoubleLinkList() # 新建一個鏈表類
print(l1.nodes_list())
l1.add(1)
print(l1.nodes_list())
l1.add(2)
print(l1.nodes_list())
l1.append(3)
print(l1.nodes_list())
l1.insert(1, 7)
print(l1.nodes_list())
l1.insert(5, 5)
print("插入")
print(l1.nodes_list())
l1.remove(2)
print(l1.nodes_list())
l1.modify(0, 0)
print(l1.nodes_list())
print("查找")
print(l1.search(5))結(jié)果
總結(jié)
以上為個人經(jīng)驗(yàn)，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
PyTorch開源圖像分類工具箱MMClassification詳解
MMClassification是一款基于PyTorch的開源圖像分類工具箱，集成了常用的圖像分類網(wǎng)絡(luò)，將數(shù)據(jù)加載，模型骨架，訓(xùn)練調(diào)參，流程等封裝為模塊調(diào)用，便于在模型間進(jìn)行轉(zhuǎn)換和比較，也高效簡潔的實(shí)現(xiàn)了參數(shù)調(diào)整2022-09-09
python-parser.parse_args()解析參數(shù)問題
這篇文章主要介紹了python-parser.parse_args()解析參數(shù)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要介紹了Pipenv一鍵搭建python虛擬環(huán)境的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-05-05
python -m pip install 和 pip in
python -m pip install <package> 使用了 -m 參數(shù)來確保以 Python 模塊的形式運(yùn)行 pip，適用于確保在不同的環(huán)境中正確使用 pip，這篇文章主要介紹了python -m pip install 和 pip install 的區(qū)別,需要的朋友可以參考下2023-07-07
Python開發(fā)必備知識內(nèi)存管理與垃圾回收
Python是一種高級編程語言,因其簡潔而強(qiáng)大而備受歡迎,然而如其他編程語言一樣,Python也面臨著內(nèi)存管理的挑戰(zhàn),在Python中,垃圾回收是一項(xiàng)關(guān)鍵任務(wù),用于自動釋放不再使用的內(nèi)存,以避免內(nèi)存泄漏,本文將介紹Python中的垃圾回收機(jī)制,以及如何通過優(yōu)化代碼來提高性能2023-11-11
pandas 按日期范圍篩選數(shù)據(jù)的實(shí)現(xiàn)
這篇文章主要介紹了pandas 按日期范圍篩選數(shù)據(jù)的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
Python灰度變換中灰度切割分析實(shí)現(xiàn)
灰度變換是指根據(jù)某種目標(biāo)條件按一定變換關(guān)系逐點(diǎn)改變源圖像中每個像素灰度值的方法。目的是改善畫質(zhì)，使圖像顯示效果更加清晰。圖像的灰度變換處理是圖像增強(qiáng)處理技術(shù)中的一種非?；A(chǔ)、直接的空間域圖像處理方法，也是圖像數(shù)字化軟件和圖像顯示軟件的一個重要組成部分2022-10-10
pandas的排序、分組groupby及cumsum累計求和方式
這篇文章主要介紹了pandas的排序、分組groupby及cumsum累計求和方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-05-05
python爬蟲入門教程--利用requests構(gòu)建知乎API（三）
這篇文章主要給大家介紹了關(guān)于python爬蟲入門之利用requests構(gòu)建知乎API的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧。2017-05-05
這篇文章主要為大家介紹了Python自然語言處理停用詞過濾實(shí)例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-01-01