建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
Python數(shù)據(jù)結(jié)構(gòu)之雙鏈表
本文轉(zhuǎn)載自微信公眾號「python與大數(shù)據(jù)分析」，作者一只小小鳥鳥。轉(zhuǎn)載本文請聯(lián)系python與大數(shù)據(jù)分析公眾號。
創(chuàng)新互聯(lián)是一家專注于成都網(wǎng)站設(shè)計、做網(wǎng)站、成都外貿(mào)網(wǎng)站建設(shè)公司與策劃設(shè)計,二七網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)10余年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:二七等地區(qū)。二七做網(wǎng)站價格咨詢:18980820575
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。
雙鏈表和單鏈表在查找和遍歷上沒什么區(qū)別，在新增節(jié)點、添加節(jié)點、刪除節(jié)點上需要注意前后節(jié)點的修改，比單鏈表會復雜一些，一不小心就繞暈了。
方法和單鏈表是一致的。
isempty(self) 鏈表是否為空
length(self) 鏈表長度
travel(self) 遍歷整個鏈表
add(self,item) 鏈表頭部添加元素
append(self,item) 鏈表尾部添加元素
insert(self,item,index) 指定位置添加元素
deletebyitem(self,item) 根據(jù)數(shù)據(jù)項刪除節(jié)點
deletebyindex(self,index) 根據(jù)索引位置刪除節(jié)點
search(self,item) 根據(jù)數(shù)據(jù)項查找節(jié)點是否存在
update(self,index,item) 暫無實現(xiàn)
getitem(self,index) 獲取索引位置對應(yīng)的數(shù)據(jù)項
getindex(self,item) 獲取數(shù)據(jù)項對應(yīng)的索引位置
如下：
- #!/usr/bin/env python
- # -*- coding: UTF-8 -*-
- # _ooOoo_
- # o8888888o
- # 88" . "88
- # ( | - _ - | )
- # O\ = /O
- # ____/`---'\____
- # .' \\| |// `.
- # / \\|||:|||// \
- # / _|||||-:- |||||- \
- # | | \\\ - /// | |
- # | \_| ''\---/'' | _/ |
- # \ .-\__ `-` ___/-. /
- # ___`. .' /--.--\ `. . __
- # ."" '< `.___\_<|>_/___.' >'"".
- # | | : `- \`.;`\ _ /`;.`/ - ` : | |
- # \ \ `-. \_ __\ /__ _/ .-` / /
- # ==`-.____`-.___\_____/___.-`____.-'==
- # `=---='
- '''
- @Project ：pythonalgorithms
- @File ：doublelinklist.py
- @Author ：不勝人生一場醉
- @Date ：2021/7/13 23:00
- '''
- class Node(object):
- def __init__(self, data):
- self.prev = None
- self.data = data
- self.next = None
- class DoubleLinkList(object):
- def __init__(self):
- self.header = None
- self.currentnum = 0
- def isempty(self):
- return self.header == None
- def travel(self):
- tempnode = self.header
- while tempnode != None:
- print("{}".format(tempnode.data), end=" ")
- tempnode = tempnode.next
- print("\r")
- def add(self, item):
- node = Node(item)
- if self.isempty():
- self.header = node
- self.currentnum += 1
- return
- node.next = self.header
- self.header.prev = node
- self.header = node
- self.currentnum += 1
- def append(self, item):
- if self.isempty():
- self.add(item)
- self.currentnum += 1
- return
- tempnode = self.header
- while tempnode.next is not None:
- tempnode = tempnode.next
- node = Node(item)
- node.prev = tempnode
- tempnode.next = node
- self.currentnum += 1
- def length(self):
- length = 0
- tempnode = self.header
- while tempnode is not None:
- length += 1
- tempnode = tempnode.next
- return length
- def search(self, item):
- tempnode = self.header
- while tempnode != None:
- if tempnode.data == item:
- return True
- else:
- tempnode = tempnode.next
- return False
- def update(self, index, item):
- pass
- def getitem(self, index):
- if index > self.currentnum or index <= 0:
- raise IndexError("{} is not find in Linklist".format(index))
- tempnode = self.header
- i = 1
- while i < index:
- tempnode = tempnode.next
- i += 1
- if tempnode.next == None:
- return -1
- else:
- return tempnode.data
- def getindex(self, item):
- tempnode = self.header
- i = 0
- flag = False
- while tempnode != None:
- i += 1
- if tempnode.data == item:
- flag = True
- return i
- else:
- tempnode = tempnode.next
- if flag == False:
- return 0
- def insert(self, item, index):
- tempnode = self.header
- if index > self.currentnum + 1 or index <= 0:
- raise IndexError("{} is not find in Linklist".format(index))
- # 指定位置為第一個即在頭部插入
- if index == 1:
- self.add(item)
- elif index > self.currentnum - 1:
- self.append(item)
- else:
- node = Node(item)
- for i in range(1, index - 1):
- tempnode = tempnode.next
- node.next = tempnode.next
- node.prev = tempnode
- tempnode.next.prev = node
- tempnode.next = node
- self.currentnum += 1
- def deletebyitem(self, item):
- tempnode = self.header
- while tempnode != None:
- if tempnode.data == item:
- self.currentnum -= 1
- if tempnode == self.header:
- self.header = self.header.next
- if tempnode.next:
- tempnode.next.prev = None
- return
- if tempnode.next is None:
- tempnode.prev.next = tempnode.next
- return
- tempnode.prev.next = tempnode.next
- tempnode.next.prev = tempnode.prev
- return
- tempnode = tempnode.next
- def deletebyindex(self, index):
- if index > self.currentnum or index <= 0:
- raise IndexError("{} is not find in Linklist".format(index))
- i = 1
- tempnode = self.header
- if index == 1:
- self.header = tempnode.next
- if tempnode.next:
- tempnode.prev = None
- self.currentnum -= 1
- return
- while tempnode.next and i < index:
- tempnode = tempnode.next
- i += 1
- if tempnode.next is None:
- tempnode.prev.next = tempnode.next
- self.currentnum -= 1
- return
- if i == index:
- tempnode.prev.next = tempnode.next
- tempnode.next.prev = tempnode.prev
- self.currentnum -= 1
- if __name__ == '__main__':
- a = DoubleLinkList()
- a.add(1) # 1
- a.travel()
- a.add(2)
- a.travel()
- a.append(4)
- a.travel()
- a.append(3)
- a.travel()
- print(a.length())
- print(a.search(1))
- print(a.getindex(4))
- print(a.getindex(5))
- print(a.getitem(2))
- # print(a.getitem(5))
- # IndexError: 5 is not find in Linklist
- a.insert(5, 1)
- a.travel()
- a.insert(6, 5)
- a.travel()
- a.insert(7, 2)
- a.travel()
- a.deletebyitem(7)
- a.travel()
- a.deletebyitem(6)
- a.travel()
- a.deletebyitem(5)
- a.travel()
- a.deletebyindex(2)
- a.travel()
- a.deletebyindex(3)
- a.travel()
- a.deletebyindex(1)
- a.travel()
調(diào)試了2、3個小時的bug，才跑通。
運行如下：
- C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/doublelinklist.py
- 1
- 2 1
- 2 1 4
- 2 1 4 3
- 4
- True
- 3
- 0
- 1
- 5 2 1 4 3
- 5 2 1 4 6 3
- 5 7 2 1 4 6 3
- 5 2 1 4 6 3
- 5 2 1 4 3
- 2 1 4 3
- 2 4 3
- 2 4
- 4
- Process finished with exit code 0
鏈表頭部增加節(jié)點示意圖
當前題目：Python數(shù)據(jù)結(jié)構(gòu)之雙鏈表
本文鏈接：http://www.dlmjj.cn/article/djgdsoe.html
