本文主要介绍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

链表头部增加节点示意图

我是小职，记得找我

✅ 解锁高薪工作

✅ 免费获取基础课程·答疑解惑·职业测评