数据结构——链表

链表（Linked List）是一种常见的基础数据结构，它由一系列节点（Node）构成，每个节点包含两个部分：

  1. 数据域（Data）：存储数据的部分。
  2. 指针域（Next）：指向链表中下一个节点的引用或指针。

链表是一种动态数据结构，与数组不同，链表的元素不需要在内存中是连续的，它们通过指针连接形成一个链式结构。

1. 链表的基本概念

1.1. 节点结构

一个链表由多个节点组成，每个节点包含数据和指向下一个节点的指针。典型的节点结构如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点的值
        self.next = next  # 指向下一个节点的指针

1.2. 链表的基本操作

链表的操作主要包括：

  • 插入操作：在指定位置插入新的节点。
  • 删除操作：删除指定位置的节点。
  • 查找操作：查找链表中某个节点。
  • 遍历操作：访问链表中的所有节点。

2. 链表的类型

链表有多种不同类型，最常见的有以下几种：

2.1. 单链表（Singly Linked List）

每个节点只包含一个指向下一个节点的指针。链表的最后一个节点的 next 指针指向 None。

头节点 -> 节点1 -> 节点2 -> 节点3 -> ... -> 节点n -> None

2.2. 双链表（Doubly Linked List）

每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。双链表可以双向遍历。

None <- 节点1 <-> 节点2 <-> 节点3 <-> ... <-> 节点n -> None

2.3. 循环链表（Circular Linked List）

链表的最后一个节点指向头节点，而不是 None。可以是单向或双向循环链表。

头节点 -> 节点1 -> 节点2 -> ... -> 节点n -> 头节点（循环）

3. 单链表的操作

3.1. 插入操作

  1. 在头部插入节点：
    插入一个新节点到链表的头部，更新头指针。
def insert_at_head(head, val):
    new_node = ListNode(val)
    new_node.next = head
    return new_node  # 返回新的头节点
  1. 在尾部插入节点：
    遍历到链表的尾部，插入一个新的节点。
def insert_at_tail(head, val):
    new_node = ListNode(val)
    if not head:  # 链表为空，直接将新节点作为头节点
        return new_node
    current = head
    while current.next:
        current = current.next
    current.next = new_node  # 将尾节点的指针指向新节点
    return head
  1. 在指定位置插入节点：
    在链表的指定位置插入一个节点。
def insert_at_position(head, val, position):
    new_node = ListNode(val)
    if position == 0:  # 在头部插入
        new_node.next = head
        return new_node
    current = head
    count = 0
    while current and count < position - 1:
        current = current.next
        count += 1
    if current is None:  # 如果位置超过链表长度，返回原链表
        return head
    new_node.next = current.next
    current.next = new_node
    return head

3.2. 删除操作

  1. 删除头节点：
    删除链表的第一个节点，更新头指针。
def delete_head(head):
    if head is None:
        return None  # 链表为空，返回空
    return head.next  # 返回新的头节点
  1. 删除指定节点：
    删除链表中某个位置的节点。
def delete_at_position(head, position):
    if position == 0:  # 删除头节点
        return delete_head(head)
    current = head
    count = 0
    while current and count < position - 1:
        current = current.next
        count += 1
    if current is None or current.next is None:  # 如果位置不合法
        return head
    current.next = current.next.next  # 删除指定位置的节点
    return head

3.3. 查找操作

  1. 查找指定值的节点：
    遍历链表，查找值为 val 的节点。
def find_node(head, val):
    current = head
    while current:
        if current.val == val:
            return current
        current = current.next
    return None  # 如果没有找到，返回 None

3.4. 遍历操作

遍历整个链表，打印每个节点的值。

def print_linked_list(head):
    current = head
    while current:
        print(current.val, end=" -> ")
        current = current.next
    print("None")

4. 链表的优缺点

4.1. 优点

  • 动态大小：链表不需要预分配内存空间，可以在运行时动态地调整大小。
  • 高效的插入和删除操作：在链表中插入或删除节点不需要移动大量元素，时间复杂度为 O(1)。
  • 内存利用率高：节点按需分配内存，节省了内存空间。

4.2. 缺点

  • 随机访问效率低：链表无法直接访问任意节点，需要通过遍历来查找，时间复杂度为 O(n)。
  • 额外的空间开销：每个节点除了存储数据外，还需要额外的指针域，占用更多内存。
  • 指针复杂度高：在复杂操作中，指针的维护和管理容易出错，增加了程序的复杂性。

5. 链表的应用

链表作为一种基本数据结构，广泛应用于许多场景中：

  1. 实现栈和队列：链表是实现栈（LIFO）和队列（FIFO）数据结构的常见选择。
  2. 内存管理：操作系统中的动态内存分配常使用链表来管理空闲内存块。
  3. 图的邻接表表示：链表可以用于表示图的邻接表，其中每个节点存储与某个节点相邻的其他节点。
  4. LRU 缓存：链表也常用于实现 LRU（Least Recently Used）缓存，按需删除最不常用的元素。

6. 总结

链表是一种灵活的动态数据结构，通过节点间的链接实现了灵活的插入和删除操作。尽管链表的随机访问效率较低，但它在实现栈、队列、图的邻接表等应用中仍然发挥着重要作用。掌握链表的基本操作和应用可以帮助我们解决许多实际问题，并为理解更复杂的数据结构打下基础。