Python數據結構之雙鏈表
作者：一只小小鳥鳥
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。
本文轉載自微信公眾號「python與大數據分析」，作者一只小小鳥鳥。轉載本文請聯系python與大數據分析公眾號。
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。
雙鏈表和單鏈表在查找和遍歷上沒什么區別，在新增節點、添加節點、刪除節點上需要注意前后節點的修改，比單鏈表會復雜一些，一不小心就繞暈了。
方法和單鏈表是一致的。
isempty(self) 鏈表是否為空
length(self) 鏈表長度
travel(self) 遍歷整個鏈表
add(self,item) 鏈表頭部添加元素
append(self,item) 鏈表尾部添加元素
insert(self,item,index) 指定位置添加元素
deletebyitem(self,item) 根據數據項刪除節點
deletebyindex(self,index) 根據索引位置刪除節點
search(self,item) 根據數據項查找節點是否存在
update(self,index,item) 暫無實現
getitem(self,index) 獲取索引位置對應的數據項
getindex(self,item) 獲取數據項對應的索引位置
如下：
- #!/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()
調試了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
鏈表頭部增加節點示意圖
責任編輯：武曉燕
來源：
python與大數據分析
