链式存储结构

学习目标

本节学习线性表的第二种常见实现方式：链式存储结构。

链式存储不要求元素在内存中连续摆放，而是让每个节点保存数据和指向下一个节点的引用。链表就是链式存储的典型代表。

什么是链式存储

链式存储把线性表拆成一个个节点。每个节点通常包含两部分：

数据域：保存当前元素的值。
指针或引用域：保存下一个节点的位置。

可以用下面的形式理解单链表：

10 -> 20 -> 30 -> 40 -> null

这里的箭头表示节点之间的连接关系。即使这些节点在内存中不连续，只要每个节点能找到下一个节点，就能表达完整的线性顺序。

节点的基本表示

下面用四种语言表示一个单链表节点：

struct Node {
    int value;
    Node* next;

    Node(int value) : value(value), next(nullptr) {}
};

class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
        this.next = null;
    }
}

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Node
{
    public int Value { get; set; }
    public Node? Next { get; set; }

    public Node(int value)
    {
        Value = value;
        Next = null;
    }
}

这四段代码表达的是同一个结构：节点保存一个整数值，并且保存下一个节点的位置。

链表的关键不是节点本身有多复杂，而是多个节点可以通过 next 串起来，形成线性关系。

从头节点开始遍历

链表不能像数组那样直接通过下标定位。要访问链表中的元素，通常需要从头节点开始，沿着 next 一个一个往后走。

void printList(Node* head) {
    Node* current = head;

    while (current != nullptr) {
        cout << current->value << endl;
        current = current->next;
    }
}

void printList(Node head) {
    Node current = head;

    while (current != null) {
        System.out.println(current.value);
        current = current.next;
    }
}

def print_list(head):
    current = head

    while current is not None:
        print(current.value)
        current = current.next

void PrintList(Node? head)
{
    Node? current = head;

    while (current != null)
    {
        Console.WriteLine(current.Value);
        current = current.Next;
    }
}

如果链表有 $n$ 个节点，遍历需要访问每个节点一次，所以时间复杂度是 $O(n)$ 。

链表的插入思想

链表插入的核心是改变引用关系。

假设有下面的链表：

10 -> 20 -> 30

如果要在 20 后面插入 25，需要让新节点指向 30，再让 20 指向新节点：

10 -> 20 -> 25 -> 30

这一步不需要移动 30，也不需要移动后面的节点，只需要修改连接关系。

如果已经知道要插入位置的前一个节点，插入操作本身通常是 $O(1)$ 。但如果需要先从头查找插入位置，那么查找过程可能是 $O(n)$ 。

链表的删除思想

删除节点也是修改连接关系。

假设有下面的链表：

10 -> 20 -> 30 -> 40

如果要删除 30，可以让 20 直接指向 40：

10 -> 20 -> 40

被删除的节点不再处于链表连接中。

和插入一样，如果已经知道待删除节点的前一个节点，删除连接本身通常是 $O(1)$ ；如果要先查找节点位置，则整体可能是 $O(n)$ 。

链式存储的特点

链式存储的优势包括：

不要求连续空间。
插入和删除时通常不需要移动大量元素。
容量可以随着节点增加而增长。

它的劣势包括：

不能高效按下标随机访问。
每个节点需要额外保存指针或引用。
遍历时必须沿连接逐个访问。
相比连续数组，内存访问局部性通常较差。

这些特点决定了链表适合频繁插入删除、不强调随机访问的场景。

本节小结

链式存储通过节点和引用表达线性关系，不要求元素在内存中连续存放。

链表按位置访问通常需要从头遍历，时间复杂度是 $O(n)$ 。如果已经知道相关节点，插入和删除可以通过修改连接关系完成，操作本身通常是 $O(1)$ 。