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