Python雙向鏈表插入節(jié)點(diǎn)方式
更新時(shí)間：2023年06月13日 09:17:29 作者：城俊BLOG
這篇文章主要介紹了Python雙向鏈表插入節(jié)點(diǎn)方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
Python雙向鏈表插入節(jié)點(diǎn)
# 定義一個(gè)鏈表節(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)下一個(gè)指向head self.head.pre = node # head的上一個(gè)指向node self.head = node # head指向node # 在尾部插入 elif index > self.length-1: if self.head == None: self.head = node else: # 將指針移動(dòng)到鏈表尾部 curr = self.head while curr.next != None: curr = curr.next curr.next = node # 尾節(jié)點(diǎn)的下一個(gè)指向節(jié)點(diǎn) node.prev = curr # 節(jié)點(diǎn)的上一個(gè)指向尾節(jié)點(diǎn) # 在中間插入 else: curr = self.head count = 0 # 將指針移動(dòng)到要插入位置的前一個(gè)位置 while count < index-1: count += 1 curr = curr.next node.pre = curr # 節(jié)點(diǎn)的上一個(gè)指向當(dāng)前 node.next = curr.next # 節(jié)點(diǎn)的下一個(gè)指向當(dāng)前下一個(gè) curr.next.pre = node # 當(dāng)前的下一個(gè)的上一個(gè)指向節(jié)點(diǎn) curr.next = node # 當(dāng)前的下一個(gè)指向節(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方法：向鏈表的頭部添加一個(gè)節(jié)點(diǎn) data
append方法：向鏈表的尾部添加一個(gè)節(jié)點(diǎn)， 值為data
insert方法：向指定位置添加節(jié)點(diǎn)，值為data
remove方法：刪除鏈表中第一個(gè)值為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)的前一個(gè)節(jié)點(diǎn)
self.data = data # 數(shù)據(jù)域
self.next = _next # 指針域 指向的是當(dāng)前節(jié)點(diǎn)的下一個(gè)節(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時(shí)找到尾結(jié)點(diǎn)
ls.append(cur.data)
cur = cur.next # 鏈表不為空時(shí)繼續(xù)向后
return ls # 返回鏈表
def add(self, data):
# 向鏈表的頭部添加一個(gè)節(jié)點(diǎn) data
node = Node(data) # 新建一個(gè)節(jié)點(diǎn)
if self.is_empty():#鏈表為空
self.head = node
else:#鏈表不為空
self.head.prev = node #1 讓鏈表中原本得頭結(jié)點(diǎn)prev指向新建節(jié)點(diǎn)
# 如果鏈表為空時(shí)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):
# 向鏈表的尾部添加一個(gè)節(jié)點(diǎn)， 值為data
# 新建一個(gè)節(jié)點(diǎn)node, 值為data
node = Node(data)
if self.head != None: # 鏈表不為空 有元素
cur = self.head
# 鏈表為空時(shí)，self.head 為None 無法執(zhí)行循環(huán)中的.next while cur.next != None: #cur.next = None時(shí)找到尾結(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)
# 不為空時(shí)，通過當(dāng)前節(jié)點(diǎn)得next去訪問下一個(gè)節(jié)點(diǎn)
while cur.next != None: # cur.next = None時(shí)找到尾結(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):
# 刪除鏈表中第一個(gè)值為data的節(jié)點(diǎn)
cur = self.head
while cur:
if cur.data == data:#找到要?jiǎng)h的節(jié)點(diǎn)
# 如果前驅(qū)節(jié)點(diǎn)為空， 說明我們要?jiǎng)h除的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)
if cur == self.head:#刪的是第一個(gè)結(jié)點(diǎn)
self.head = cur.next # 指向第二個(gè)節(jié)點(diǎn)
self.head.prev = None
else: # 要?jiǎng)h除的不是第一個(gè)節(jié)點(diǎn)
cur.prev.next = cur.next #要?jiǎng)h除節(jié)點(diǎn)的前一節(jié)點(diǎn)的next指向要?jiǎng)h除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
#如要?jiǎng)h除的節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)，只需執(zhí)行這一步
if cur.next != None:#判斷cur.next是否存在
cur.next.prev = cur.prev #要?jiǎng)h除節(jié)點(diǎn)的下一節(jié)點(diǎn)的prev指向要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(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() # 新建一個(gè)鏈表類
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é)
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
Python隊(duì)列RabbitMQ 使用方法實(shí)例記錄
這篇文章主要介紹了Python隊(duì)列RabbitMQ 使用方法,結(jié)合實(shí)例形式分析了Python隊(duì)列RabbitMQ創(chuàng)建隊(duì)列發(fā)送消息與創(chuàng)建消費(fèi)者消費(fèi)信息相關(guān)操作技巧,需要的朋友可以參考下2019-08-08
PyQt5實(shí)現(xiàn)將Matplotlib圖像嵌入到Scoll Area中顯示滾動(dòng)條效果
我想知道是否有一種方法可以在matplotlib上顯示滾動(dòng)條(水平或垂直),顯示包含多個(gè)子槽(sublot2grid)的頁面(plt.show).下面就通過本文給大家分享PyQt5實(shí)現(xiàn)將Matplotlib圖像嵌入到Scoll Area中顯示滾動(dòng)條效果，對(duì)PyQt5 Matplotlib圖像嵌入相關(guān)知識(shí)感興趣的的朋友一起看看吧2021-05-05
這篇文章主要介紹了python 元組和列表的區(qū)別，幫助大家更好的理解和學(xué)習(xí)python 數(shù)據(jù)類型的相關(guān)知識(shí)，感興趣的朋友可以了解下2020-11-11
Python讀取多格式Excel并實(shí)現(xiàn)跨表匹配合并的完整示例
在數(shù)據(jù)處理中,經(jīng)常會(huì)遇到這樣一個(gè)需求：一份是主數(shù)據(jù)表,另一份是學(xué)生/員工/客戶的完整信息表, 需要按姓名匹配,把完整信息補(bǔ)充到主表中,聽起來簡單,但實(shí)際操作中常會(huì)踩坑,本文就分享一次真實(shí)項(xiàng)目中的解決方案,需要的朋友可以參考下2025-11-11
這篇文章主要介紹了Python 字符串去除空格的五種方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
使用Python分析文本數(shù)據(jù)的詞頻并詞云圖可視化
這篇文章主要給大家介紹了關(guān)于如何使用Python分析文本數(shù)據(jù)的詞頻并詞云圖可視化,文章中有詳細(xì)的圖文介紹和代碼示例,對(duì)我們的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2023-09-09
Django應(yīng)用程序入口WSGIHandler源碼解析
這篇文章主要介紹了Django應(yīng)用程序入口WSGIHandler源碼解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-08-08
python實(shí)現(xiàn)巡檢系統(tǒng)(solaris)示例
這篇文章主要介紹了python實(shí)現(xiàn)巡檢系統(tǒng)(solaris)示例,需要的朋友可以參考下2014-04-04
本文詳細(xì)介紹了多種生成Markdown文件的方法,包括基礎(chǔ)方法、使用模板引擎、專業(yè)庫生成以及從數(shù)據(jù)結(jié)構(gòu)生成,每種方法都有具體的使用示例和總結(jié),旨在幫助讀者掌握不同場景下的Markdown生成技巧,需要的朋友可以參考下2025-12-12
Python中的自定義函數(shù)學(xué)習(xí)筆記
這篇文章主要介紹了Python中的自定義函數(shù)學(xué)習(xí)筆記,本文講解了定義函數(shù)、callable函數(shù)、help函數(shù)等內(nèi)容,需要的朋友可以參考下2014-09-09