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 

链表头部增加节点示意图

云服务器

很赞哦!（1）