本文转载自微信公众号「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
链表头部增加节点示意图