{{ 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日

    单向链表

    单项链表是许多高级数据结构的基础，这些高级数据结构有queue、list、stack等等。一般情况下，我们不会直接用单向链表解决现实问题，而是借助高级数据结构来解决现实问题。

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

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

    定义

    Singly linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.

    以上定义说明，单向链表是由一个一个的链表节点串联而成，每个链表节点由2部分组成：数据部分和指向下一个节点部分，如下图所示：

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

    1. 向链表的尾部增加一个新的链表节点
    2. 移除链表头部的节点
    3. 遍历链表

    单向链表有以下几点特性：

    1. 链表上的节点在内存空间上无需连续存放
    2. 表头和表尾是单向链表操作最频繁的地方
    3. 单向链表不支持随机存取，如果你想利用随机存取的特性，那么放弃链表
    4. 删除链表中间的节点需要遍历
    5. 删除或增加节点，不会影响其它节点的内存分布
    6. 需要额外的空间来记录下一个节点，因此，会造成内存翻倍增长

    实现和操作

    以下是Python版本的链表，我们定义了一个单向链表类型SinglyLinkedList，它有以下属性：

    1. head指向了表头，能够方便地让你从表头开始遍历整个链表或者删除表头节点
    2. tail指向了表尾，能够方便地让你向表尾增加新的节点
    3. count是指链表的节点数，可以用它来判断链表是否为空

    除此之外，以下代码还定义了4个与单向链表相关的操作：

    1. add_to_tail，向表尾增加新的节点
    2. remove_from_head，删除表头
    3. empty，判断链表是否为空链表
    4. print_all，遍历并打印链表上所有节点
    class SinglyLinkedListNode:
    def __init__(self, key, val):
        self.next = None
        self.key = key
        self.value = val

    def __str__(self):
        return f'{self.key},{self.value}'

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

    def add_to_tail(self, key, val):
        new_node = SinglyLinkedListNode(key, val)
        if self.count == 0:
            self.tail = self.head = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.count += 1

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

    def find(self, key):
        current_node = self.head
        while current_node is not None:
            if current_node.key == key:
                return current_node
            current_node = current_node.next
        return None

    def insert(self, key, value):
        node = self.find(key)
        if node is None:
            self.add_to_tail(key, value)
            return 1
        else:
            node.value = value
            return 0

    def remove(self, key):
        previous_node = current_node = self.head
        while current_node is not None:
            if current_node.key == key:
                if previous_node == current_node:
                    return self.remove_from_head()
                else:
                    previous_node.next = current_node.next
                    current_node.next = None
                    return current_node
            previous_node = current_node
            current_node = current_node.next
        return None

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

    def print_all(self):
        current_node = self.head
        while current_node:
            print(current_node.value)
            current_node = current_node.next

    以下是以上单向链表的用法：

    single_linked_list = SinglyLinkedList()
single_linked_list.add_to_tail(1, 1)
single_linked_list.add_to_tail(10, 10)
single_linked_list.add_to_tail(90, 90)
single_linked_list.add_to_tail(100, 100)
single_linked_list.add_to_tail(2, 2)

single_linked_list.print_all()

    输出结果如下所示：

    1
10
90
100
2

    空间复杂度和时间复杂度

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

    • add_to_tail用于向表尾增加新节点，它的空间复杂度是O(1)，而时间复杂度是O(1)
    • remove_from_head，删除表头，它的空间复杂度是O(1)，而时间复杂度是O(1)
    • empty用于判断链表是否不包含任何节点，它的空间复杂度是O(1)，而时间复杂度是O(1)
    • print_all用于顺序遍历整个链表，它的空间复杂度是O(1)，而时间复杂度是O(n)

    从以上分析可知，除了遍历的时间复杂度与链表的节点个数成正比，其它操作的时间复杂度均是O(1)。另外，单向链表非常不适合反向遍历，为了解决这个问题，计算机的先驱们发明了另外一种类似的数据结构-双向链表。