跳到主要内容

链表

链表是一种基本数据结构，它表示一个元素序列。每个元素，称为节点，包含：

  • 数据（值）：存储在节点中的信息。
  • 引用（指针）：指向序列中下一个节点的链接。

第一个节点称为头节点，最后一个节点是尾节点，它指向 None，表示列表的结束。

Python 中的节点结构​

以下是一个单向链表的简单节点类示例：

class ListNode:
    """单向链表的节点类。"""
    def __init__(self, val: int):
        self.val: int = val          # 存储在节点中的数据
        self.next: 'ListNode' = None # 指向下一个节点的引用

创建链表​

要构建一个链表，需要实例化节点并使用它们的 next 引用将它们链接起来：

# 创建带有值的节点
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)

# 链接节点：1 -> 3 -> 2 -> 5 -> 4
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

# 设置链表的头节点
head = n0

链表的常见操作​

时间复杂度比较​

操作数组单向链表双向链表循环链表
按索引访问O (1)O (n)O (n)O (n)
在头部插入O (n)O (1)O (1)O (1)
在头部删除O (n)O (1)O (1)O (1)
在尾部插入O (1)*O (n)**O (1)O (1)
在尾部删除O (1)*O (n)O (1)O (1)
按值搜索O (n)O (n)O (n)O (n)

* 如果数组在末尾有未使用的容量。

** 如果维护尾部引用，则为 O (1)。

插入节点​

要在节点 n0 之后插入节点 P：

def insert(n0: ListNode, P: ListNode):
    """在链表中，将节点 P 插入到节点 n0 之后。"""
    P.next = n0.next
    n0.next = P

删除节点​

要移除紧跟在 n0 之后的节点：

def remove(n0: ListNode):
    """移除链表中节点 n0 之后的节点。"""
    if n0.next:
        n0.next = n0.next.next

按索引访问节点​

访问特定索引处的节点：

def access(head: ListNode, index: int) -> ListNode | None:
    """返回指定索引处的节点。"""
    current = head
    for _ in range(index):
        if current is None:
            return None
        current = current.next
    return current

按值搜索节点​

查找具有给定值的第一个节点：

def find(head: ListNode, target: int) -> int:
    """返回具有目标值的节点的索引。"""
    current = head
    index = 0
    while current:
        if current.val == target:
            return index
        current = current.next
        index += 1
    return -1  # 未找到目标

数组 vs. 链表​

主要区别​

特性数组链表
内存分配连续非连续
大小固定（静态）动态
内存开销最小指针额外开销
访问时间O (1)（随机访问）O (n)（顺序访问）
插入/删除O (n)（需要移位）O (1)（如果节点已知）
缓存性能更好（由于局部性）较差

链表的类型​

单向链表​

  • 结构：带有单个 next 引用的节点。
  • 遍历：只能向前。

双向链表​

  • 结构：带有 next 和 prev 引用的节点。

  • 遍历：向前和向后。

  • 节点类示例：

    class ListNode:
        """双向链表的节点类。"""
        def __init__(self, val: int):
            self.val: int = val
            self.next: 'ListNode' = None
            self.prev: 'ListNode' = None

循环链表​

  • 结构：最后一个节点指回第一个节点。
  • 用例：适用于需要循环遍历的应用程序。

优点和缺点​

优点​

  • 动态大小：在运行时随着元素的添加或移除而调整。
  • 高效的插入/删除：在已知位置插入或删除时，时间复杂度为 O (1)。
  • 灵活的内存使用：根据需要使用内存，无需预先分配。

缺点​

  • 内存开销：存储引用需要额外内存。
  • 无随机访问：不能通过索引直接访问元素。
  • 缓存效率低下：非连续内存分配可能导致缓存未命中。
  • 复杂性：与数组相比实现更复杂。

链表的应用​

单向链表​

  • 栈和队列：实现 LIFO 和 FIFO 结构。
  • 哈希表：使用链表处理冲突。
  • 邻接表：表示稀疏图。

双向链表​

  • LRU 缓存：有效地更新和访问最近使用的项。
  • 文本编辑器：管理字符序列以实现高效的插入和删除。
  • 浏览器导航：实现前进和后退导航。

循环链表​

  • 轮询调度：在进程之间均匀分配资源。
  • 音频/视频缓冲区：实现连续播放循环。
  • 多人游戏：在回合制游戏中管理玩家。