{{ selected_gold.title }}

  • ¥ {{ selected_gold.original_price }}
  • ¥ {{ selected_gold.price }}
点击阅读
  • {{ selected_gold.number_of_order }} 人订阅
    • {{ selected_gold.total_likers_count }}
    由 {{ selected_gold.creator_name }} 编辑

    {{ title }}

    请登录购买（{{ selected_gold.price }}元），即可解锁剩余教程
    点击购买
    • Air
    • 2020年12月19日

    双向链表

    双向链表与单向链表很类似，唯一的区别是双向链表中的每个节点均能访问前一个(pre)和后一个(next)节点。因此，双向链表能够在表尾增加新的节点，也能删除表尾节点；同理，你也能轻松地在表头新增或删除节点。除此之外，你还能反向遍历整个链表。

    本文将通过以下几方面来介绍双向链表：

    • 定义
    • 实现和操作
    • 空间复杂度和时间复杂度

    定义

    In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').

    以上定义说明了，双向链表的节点不仅包含了数据部分，而且还包含了之前上一个节点和下一个节点的部分，比单向链表的节点多出了指向上一个节点的部分，相应地，也花费了更多的内存。如下图所示：

    组成双向链表的操作如下所示：

    1. add_to_tail，从表尾新增一个节点
    2. remove_from_tail，从表尾删除一个节点
    3. add_to_head，从表头新增一个节点
    4. remove_from_head，从表头删除一个节点
    5. empty，判断双向链表是否为空链表
    6. print_all，遍历双向链表

    实现和操作

    class DoublyLinkedListNode:
    def __init__(self, val):
        self.pre = None
        self.next = None
        self.value = val

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    def add_to_tail(self, val):
        new_node = DoublyLinkedListNode(val)
        if self.empty():
            self.tail = self.head = new_node
        else:
            new_node.pre = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.count += 1

    def remove_from_tail(self):
        val = self.tail.value
        self.count -= 1
        if self.empty():
            self.head = self.tail = None
        else:
            self.tail.pre.next = None
        return val

    def add_to_head(self, val):
        new_node = DoublyLinkedListNode(val)
        if self.empty():
            self.tail = self.head = new_node
        else:
            new_node.next = self.head
            self.head.pre = new_node
            self.head = new_node

    def remove_from_head(self):
        val = self.head.value
        self.head = self.head.next
        self.count -= 1
        if self.empty():
            self.tail = None
        else:
            self.head.pre = None
        return val

    def empty(self):
        return self.count == 0

    def print_all(self, reverse = False):
        current_node = self.head
        next_node = lambda x : x.next
        if reverse:
            current_node = self.tail
            next_node = lambda x : x.pre
        while current_node:
            print(current_node.value)
            current_node = next_node(current_node)

    使用方式如下所示：

    • 创建双向链表
    double_linked_list = DoublyLinkedList()
double_linked_list.add_to_tail(1)
double_linked_list.add_to_tail(10)
double_linked_list.add_to_tail(90)
double_linked_list.add_to_tail(100)
double_linked_list.add_to_tail(2)
    • 从表头开始遍历
    print('traverse from head')
double_linked_list.print_all()

    输出结果如下所示：

    traverse from head
1
10
90
100
2
    • 从表尾开始遍历
    print('traverse from tail')
double_linked_list.print_all(True)

    输出结果如下所示：

    traverse from tail
2
100
90
10
1

    空间复杂度和时间复杂度

    接下来，让我们看看以上定义的每一种方法，它们的空间复杂度和时间复杂度是多少。

    • add_to_tail，从表尾新增一个节点，它的空间复杂度是O(1)，而时间复杂度是O(1)
    • remove_from_tail，从表尾删除一个节点，它的空间复杂度是O(1)，而时间复杂度是O(1)
    • add_to_head，从表头新增一个节点，它的空间复杂度是O(1)，而时间复杂度是O(1)
    • remove_from_head，从表头删除一个节点，它的空间复杂度是O(1)，而时间复杂度是O(1)
    • empty，判断双向链表是否为空链表，它的空间复杂度是O(1)，而时间复杂度是O(1)
    • print_all可以顺序或反向遍历整个链表，它的空间复杂度是O(1)，而时间复杂度是O(n)

    从以上分析可知，除了遍历的时间复杂度与链表的节点个数成正比，其它操作的时间复杂度均是O(1)。另外，双向链表可以在表头或表尾增加或删除节点，因此，这种特性非常适合双端队列。