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

时间：2022-08-07 08:58:45|栏目：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，然后将待插结点插入 current 之前；另一种方法是找到待插入位置结点的前驱结点 prev，然后待插结点插入 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 函数调用对象上的 __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)

程序输出结果如下：