Python数据结构之双向链表详解

小满

发布时间：2026-10-15| 4人浏览过

原创

本文深入解析Python中双向链表的实现原理与核心操作。详细讲解双向链表结点结构、优缺点分析，并逐步演示初始化、长度获取、元素读取、插入删除及查找等基础操作的代码实现。此外，还展示了如何利用双向链表基本操作构建合并链表等复杂算法，帮助开发者掌握线性表的高级应用技巧。

0. 学习目标

单链表仅通过指向直接后继的指针来确立结点间的逻辑关系，这使得从任一结点查找后继变得便捷，但查找前驱则相对困难。双向链表正是为了解决这一痛点而设计，它利用两个指针来表征结点间的逻辑关联。在前一节讨论单链表及其操作的基础上，本节将重点聚焦于双向链表的定义及其各类操作的实现细节。

通过本节学习，应掌握以下内容：

双向链表的基本概念及其优缺点

双向链表基本操作的实现

利用双向链表的基本操作实现复杂算法

1. 双向链表简介

1.1 双向链表介绍

双向链表（doubly linked list）在结构上与单链表相似，同样基于结点和指针的概念，属于顺序表的链式存储结构。两者的核心区别在于：双向链表为每个结点增加了一个指向直接前驱的指针域，从而形成前驱链和后继链两条不同方向的链接，因此被称为双向链表或双链表。

1.2 双向链表结点类

在双向链表中，通过已知结点查找其直接前驱与查找直接后继具有同等的便捷性。与单链表类似，双向链表可分为带头结点和不带头结点两种形式，本节仅针对带头结点的双向链表进行探讨。其结点示意图显示，每个结点包含两个指针：指向直接后继的 next 和指向直接前驱的 previous。

用 Python 实现双向链表结点类如下：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.previous = None

    def __str__(self):
        return str(self.data)

其中，previous 变量指向直接前驱结点，next 变量保留对直接后继结点的引用，data 变量用于存储实际数据。此外，重载了 __str__ 方法，以便于打印结点对象时的直观展示。

1.3 双向链表优缺点

双向链表的主要优势在于支持双向遍历。给定链表中的任意节点，可以直接访问其前驱结点，无需从头开始遍历整个链表。这极大地简化了如删除结点等需要频繁访问前驱的操作。

然而，双向链表也存在以下主要缺点：

每个结点需要额外存储一个前驱指针，导致空间占用增加；
在插入或删除结点时，涉及更多的指针修改操作，增加了时间开销。

2. 双向链表实现

类似于单链表，接下来我们将实现一个带有头结点的双向链表类，并使用头指针来标识链表的起始位置。若对单链表尚不熟悉，可参考《单链表及其操作实现》相关介绍以获取背景知识。

2.1 双向链表的初始化

双向链表的初始化过程旨在建立一个空的带头结点的链表。此时，表长 length 初始化为 0，链表中仅包含一个头结点，没有元素结点。

class DoublyLinkedList:
    def __init__(self, data=None):
        self.length = 0
        # 初始化头结点
        head_node = Node()
        self.head = head_node

创建 DoublyLinkedList 对象的时间复杂度为 O(1)。

NOTE：若熟悉继承机制，可令 DoublyLinkedList 继承自《单链表及其操作实现》中实现的 SinglyLinkedList，这将大幅简化双向链表的代码实现。

2.2 获取双向链表长度

求取双向链表长度只需重载 __len__ 方法，直接返回对象内部的 length 值，因此该操作的时间复杂度为 O(1)。

    def __len__(self):
        return self.length

2.3 读取指定位置元素

双向链表中读取指定位置元素的算法与单链表完全一致，仅需通过后继链依次访问各结点即可。因此，其操作复杂度同样为 O(n)。接下来，我们将重载 __getitem__ 操作来实现读取链表指定位置元素的功能；同时，为确保索引在合法范围内，若索引越界将引发 IndexError 异常。

    def __getitem__(self, index):
        if index > self.length - 1 or index < 0:
            raise IndexError("DoublyLinkedList assignment index out of range")
        else:
            count = -1
            current = self.head
            while count < index:
                current = current.next
                count += 1
            return current.data

类似地，我们也可以实现修改指定位置元素的操作，只需重载 __setitem__ 操作，其时间复杂度同样为 O(n)。

  def __setitem__(self, index, value):
        if index > self.length - 1 or index < 0:
            raise IndexError("DoublyLinkedList assignment index out of range")
        else:
            count = -1
            current = self.head
            while count < index:
                current = current.next
                count += 1

            current.data = value

2.4 查找指定元素

与单链表相同，查找指定元素时需设置一个跟踪链表结点的指针 current，使其顺着 next 域依次指向每个结点。每指向一个结点，便判断其值是否等于指定值 value；若相等，则返回该结点的索引；否则继续向后搜索。若链表中不存在该元素，则引发 ValueError 异常，其时间复杂度为 O(n)。

    def locate(self, value):
        count = -1
        current = self.head
        while current != None and current.data != value:
            count += 1
            current = current.next
        if current and current.data == value:
            return count
        else:
            raise ValueError("{} is not in sequential list".format(value))

2.5 在指定位置插入新元素

在指定位置插入新元素主要有两种策略：一是找到待插入位置的结点 current，将新结点插入其之前；二是找到待插入位置的前驱结点 prev，将新结点插入其之后。两种方法的操作细节略有差异，本节以第二种方法为例进行说明，第一种方法的具体推导留给读者自行完成。

由于 prev 指向待插入位置的后继结点，若插入位置为列表末尾，因 prev.next = None，无法通过 prev.next.previous 访问前驱；而在链表中间部位，prev.next.previous 等于 prev。因此，插入链表中间位置与链表末尾的操作逻辑存在差异。

(1) 在双向链表的末尾插入一个结点的步骤如下：

遍历列表直至最后一个结点，并创建新结点；
将新结点的 previous 指针指向链表的最后一个结点；
更新原链表最后一个结点的 next 指针，使其指向新结点。

(2) 在双链表中间插入结点与单链表类似，但需要更多的步骤来修改指针：

首先遍历链表至插入位置的前驱结点 prev，并创建新结点；
将新结点的 next 指针指向要插入位置的下一个节点，同时将新结点的 previous 指针指向 prev；
将插入位置后继节点的 previous 指针指向新节点，并将 prev 结点的 next 指针指向新节点。

算法实现如下所示：

    def insert(self, index, data):
        count = 0
        prev = self.head
        # 判断插入位置的合法性
        if index > self.length or index < 0:
            raise IndexError("DoublyLinkedList assignment index out of range")
        else:
            new_node = Node(data)
            while count < index:
                prev = prev.next
                count += 1
            new_node.previous = prev
            self.length += 1
            if prev.next:
                # 链表中间插入结点
                new_node.next = prev.next
                prev.next.previous = new_node
                prev.next = new_node
            else:
                # 链尾插入结点
                prev.next = new_node

2.6 删除指定位置元素

删除指定位置元素时，只需找到相应位置的结点 current，修改相关指针后删除该结点即可。需要注意的是，除了将 current 的前驱结点的 next 指针指向 current 的后继节点外，若删除的不是链尾元素，还需将 current 的后继节点的 previous 指针指向 current 的前驱结点。

算法实现如下所示：

    def get_node(self, index):
        """辅助函数，用于根据位置返回结点"""
        if index > self.length - 1 or index < 0:
            raise IndexError("SinglyLinkedList assignment index out of range")
        count = -1
        current = self.head
        while count < index:
            current = current.next
            count += 1
        return current
    def __delitem__(self, index):
        """删除指定位置元素"""
        if index > self.length - 1 or index < 0:
            raise IndexError("SinglyLinkedList assignment index out of range")
        else:
            current = self.get_node(index)
            if current:
                current.previous.next = current.next
            # 如果删除的并非最后一个结点
            if current.next:
                current.next.previous = current.previous
            self.length -= 1
            del current

在插入和删除操作中，均需先确定操作位置，再执行具体的插入或删除动作，因此两者的时间复杂度均为 O(n)。

2.7 其它一些有用的操作

2.7.1 链表元素输出操作

为了便于打印，可将双向链表转换为字符串。通过调用对象上的 __str__ 方法，可以生成适合打印的字符串表示形式。

    def __str__(self):
        s = "["
        current = self.head.next
        count = 0
        while current != None:
            count += 1
            s += str(current)
            current = current.next
            if count < self.length:
                s += '<-->'
        s += "]"
        return s

2.7.2 删除指定元素

与删除指定位置元素略有不同，删除指定元素要求在链表中移除第一个具有与给定值相同数据元素的结点。尽管修改指针的操作类似，但其时间复杂度同样为 O(n)。

    def del_value(self, value):
        current = self.head
        while current:
            if current.data == value:
                current.previous.next = current.next
                if current.next:
                    current.next.previous = current.previous
                self.length -= 1 
                del current
                return
            else:
                current = current.next
        raise ValueError("The value provided is not present!")

2.7.3 在链表尾部追加新元素

为了便捷地在链表尾部追加新元素，可以实现 append 函数。

    def append(self, data):
        new_node = Node(data)
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.previous = current
        self.length += 1

此算法的时间复杂度为 O(n)。若需频繁在链表尾部追加元素，可通过增加尾指针 tail 来追踪链表的最后一个元素。利用尾指针在链表尾部追加新元素，可将时间复杂度降至 O(1)。

3. 双向链表应用

接下来，我们将首先测试上述实现的双向链表，以验证各项操作的有效性，随后利用这些基本操作来实现更为复杂的算法。

3.1 双向链表应用示例

首先初始化一个链表 dllist，并在其中追加若干元素。

dllist = DoublyLinkedList()
# 在链表末尾追加元素
dllist.append('apple')
dllist.append('banana')
dllist.append('orange')
# 在指定位置插入元素
dllist.insert(0, 'grape')
dllist.insert(4, 'lemon')

我们可以直接打印链表中的数据元素、链表长度等信息。

print('双向链表 sllist 为：', dllist)
print('双向链表 sllist 长度为：', len(dllist))
print('双向链表 sllist 第0个元素为：', dllist[0])
# 修改数据元素
dllist[0] = 'pear'
del(dllist[3])
print('双向修改链表 sllist 数据后：', dllist)

以上代码输出如下：

双向链表 dllist 为： [grape<-->apple<-->banana<-->orange<-->lemon] 双向链表 dllist 长度为： 5 双向链表 dllist 第0个元素为： grape 修改双向链表 dllist 数据后： [pear<-->apple<-->banana<-->lemon]

接下来，我们将演示在指定位置添加/删除元素、以及如何查找指定元素等操作。

# 修改数据元素
dllist[0] = 'pear'
print('修改双向链表 dllist 数据后：', dllist)
dllist.insert(0, 'watermelon')
print('在位置 0 添加 watermelon 后双向链表链表 ddlist 数据：', dllist)
del(dllist[3])
print('删除位置 3 处元素后双向链表 ddlist 数据：', dllist)
dllist.append('lemon')
print('在尾部追加元素 lemon 后双向链表 ddlist 数据：', dllist)
dllist.del_value('lemon')
print('删除 lemon 后双向链表 dllist 数据：', dllist)
print('watermelon 在双向链表 dllist 中的索引为：', dllist.locate('orange'))

以上代码输出如下：

修改双向链表 dllist 数据后： [pear<-->apple<-->banana<-->orange<-->lemon] 在位置 0 添加 watermelon 后双向链表链表 ddlist 数据： [watermelon<-->pear<-->apple<-->banana<-->orange<-->lemon] 删除位置 3 后双向链表 ddlist 数据： [watermelon<-->pear<-->apple<-->orange<-->lemon] 在尾部追加元素 lemon 后双向链表 ddlist 数据： [watermelon<-->pear<-->apple<-->orange<-->lemon<-->lemon] 删除 lemon 后双向链表 dllist 数据： [watermelon<-->pear<-->apple<-->orange<-->lemon] watermelon 在双向链表 dllist 中的索引为： 3

3.2 利用双向链表基本操作实现复杂操作

[1] 利用双向链表的基本操作，合并两个双向链表。

def merge(dllist1, dllist2):
    current = dllist1.head
    while current.next:
        current = current.next
    if dllist2.head.next:
        tmp = dllist2.head.next
        current.next = tmp
        tmp.previous = current
    dllist1.length += len(dllist2)
    return dllist1
# 算法测试
dllist1 = DoublyLinkedList()
dllist2 = DoublyLinkedList()
for i in range(5):
    dllist1.append(i)
    dllist2.append((i+1)*5)
print('双向链表 dllist1：', dllist1)
print('双向链表 dllist2：', dllist2)
dllist = merge(dllist1, dllist2)
print('链表合并结果：', dllist)

程序输出结果如下：