尾部添加元素如下所示:

指定位置插入元素如下所示:

上面的對的可以比照下面的圖片看，node2節點相當于上圖中的cur節點，如下所示:

代碼等價于:

node.next = cur ? ? ? ?<===> node.next = node2
node.prev = cur.prev ? <===> node.prev = node1
cur.prev.next = node ? <===> node1.next = node
cur.prev = node ? ? ? ?<===> node2.prev = node

刪除元素如下所示:

結合下圖查看，如下所示:

具體代碼如下所示:

# -*-coding=utf-8-*- class Node(object):"""結點"""def __init__(self,item):self.elem = itemself.next = Noneself.prev = None class DoubleLinkList(object):"""雙鏈表"""def __init__(self,node=None):self.__head = Nonedef is_empty(self):"""鏈表是否為空"""return self.__head is Nonedef length(self):"""鏈表長度"""#cur游標，用來移動遍歷節點cur = self.__head#count 記錄數量count = 0while cur != None:count+=1cur = cur.nextreturn countdef travel(self):"""遍歷整個鏈表"""cur = self.__headwhile cur != None:print(cur.elem,end=" ")cur = cur.nextprint("")def add(self,item):"""鏈表頭部添加元素，頭插法"""node = Node(item)#先寫箭頭指向右邊的代碼，node節點先寫next方向的，再寫prev方向的node.next = self.__headself.__head = node#最后寫箭頭指向左邊的代碼node.next.prev = nodedef append(self,item):"""鏈表尾部添加元素，尾插法"""node = Node(item)if self.is_empty():self.__head = nodeelse:cur = self.__headwhile cur.next != None:cur = cur.nextcur.next = nodenode.prev = curdef insert(self, pos, item):"""鏈表指定位置添加元素:param pos 從0開始"""# 若指定位置pos為第一個元素之前，則執行頭部插入if pos <= 0: # 頭插法self.add(item)# 若指定位置超過鏈表尾部，則執行尾部插入elif pos > (self.length() - 1): # 尾插法self.append(item)# 找到指定位置else:# pre用來指向指定位置pos的前一個位置pos-1，初始從頭節點開始移動到指定位置cur = self.__headcount = 0while count < pos:count += 1cur = cur.next# 當循環退出后,cur指向pos位置node = Node(item)node.next = curnode.prev = cur.prevcur.prev.next = nodecur.prev = nodedef remove(self, item):"""刪除節點"""cur = self.__headwhile cur != None:# 找到了指定元素if cur.elem == item:# 先判斷此節點是否是頭節點# 頭節點 # 如果第一個就是刪除的節點if cur == self.__head:# 將頭指針指向頭節點的后一個節點self.__head = cur.nextif cur.next:#判斷鏈表是否只有一個節點cur.next.prev = Noneelse:cur.prev.next = cur.nextif cur.next:cur.next.prev = cur.prevbreak # 刪除后再退出循環,需要一個總的break退出else:# 繼續按鏈表后移節點cur = cur.nextdef search(self, item):"""查找節點是否存在""""""鏈表查找節點是否存在，并返回True或者False"""cur = self.__headwhile cur != None:if cur.elem == item:return Trueelse:cur = cur.nextreturn False if __name__ == "__main__":# node = Node(100)ll = DoubleLinkList()print(ll.is_empty()) # Trueprint(ll.length()) # 0ll.append(1)print(ll.is_empty()) # Falseprint(ll.length()) # 1ll.append(2)ll.add(8)ll.append(3)ll.append(4)ll.append(5)ll.append(6)# 8 1 2 3 4 5 6ll.insert(-1, 9)ll.travel() # 9 8 1 2 3 4 5 6ll.insert(3, 100)ll.travel() # 9 8 1 100 2 3 4 5 6ll.insert(10, 200)ll.travel() # 9 8 1 100 2 3 4 5 6 200ll.remove(100)ll.travel() # 9 8 1 2 3 4 5 6 200ll.remove(9)ll.travel() # 8 1 2 3 4 5 6 200ll.remove(200)ll.travel() # 8 1 2 3 4 5 6

參考:來源網上

https://www.cnblogs.com/Se7eN-HOU/p/11103891.html

?

?

總結

以上是生活随笔為你收集整理的python算法与数据结构-双向链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。