链表

#链表

• 什么是链表
• 内存中的存储方式
• 顺序访问
• 添加和删除数据
• 循环链表与双向链表
• 时间复杂度

#什么是链表

链表也是一种数据呈线性排列的数据结构，但与数组不同：链表中的数据分散存储在内存的各个地方，每个元素通过一个「指针」指向下一个元素的地址，把它们串在一起。

你可以把链表想象成一场寻宝游戏：你到达第一个地点，找到一张纸条写着「下一个地点在 123 号」；到了 123 号，又找到一张纸条写着「下一个地点在 456 号」……就这样一环扣一环地找下去。

┌──────┬──┐    ┌──────┬──┐    ┌──────┬────┐
│ Blue │ ─┼──→ │Yellow│ ─┼──→ │ Red  │null│
└──────┴──┘    └──────┴──┘    └──────┴────┘
  数据  指针      数据  指针      数据  指针(不指向任何位置)

每个元素包含两部分：数据和指针。指针记录了下一个元素的内存地址。最后一个元素的指针为 null，表示链表到此结束。

#内存中的存储方式

内存地址:  200        530        120
         ┌──────┬───┐ ┌──────┬───┐ ┌──────┬────┐
         │ Blue │530│ │Yellow│120│ │ Red  │null│
         └──────┴───┘ └──────┴───┘ └──────┴────┘
           ↑          ↑          ↑
         头节点      第二个       第三个(尾节点)

数据分散在内存各处，不需要连续的空间——这是链表和数组最大的区别。

#顺序访问

因为数据分散存储，想访问第 3 个元素，不能像数组那样直接 a[2]，必须从头开始，顺着指针一步步走过去：

从头开始 → Blue → 顺着指针 → Yellow → 顺着指针 → Red (找到了！)

这就是顺序访问（Sequential Access）。如果目标在链表末尾，需要走遍整个链表，所以访问速度比数组慢。

#添加和删除数据

链表的添加和删除非常方便——只需要改几个指针的指向就行，不需要像数组那样移动大量元素。

添加数据（在 Blue 和 Yellow 之间插入 Green）：

添加前:  Blue ──→ Yellow ──→ Red

步骤1: 把 Blue 的指针指向 Green
        Blue ──→ Green     Yellow ──→ Red

步骤2: 把 Green 的指针指向 Yellow
        Blue ──→ Green ──→ Yellow ──→ Red

完成！只改了两个指针

删除数据（删除 Yellow）：

删除前:  Blue ──→ Green ──→ Yellow ──→ Red

步骤: 把 Green 的指针从 Yellow 改为 Red
        Blue ──→ Green ──→ Red       Yellow (变成孤儿，无法访问)

完成！Yellow 还在内存中，但没人能访问它了

#循环链表与双向链表

循环链表（环形链表）：尾部的指针不指向 null，而是指向头节点，形成环形。

  Blue ──→ Yellow ──→ Red ──┐
    ↑                       │
    └───────────────────────┘

没有头和尾的概念，适合保存数量固定的最新数据（如循环缓冲区）。

双向链表：每个节点有两个指针，分别指向前驱和后继。

  ┌──────┬──┬──┐    ┌──────┬──┬──┐    ┌──────┬──┬──┐
  │ Blue │  │ ─┼──→ │Yellow│ ─│ ─┼──→ │ Red  │ ─│  │
  │      │  │←─┼─── │      │←─│  │←───│      │  │  │
  └──────┴──┴──┘    └──────┴──┴──┘    └──────┴──┴──┘
         前驱  后继       前驱  后继       前驱  后继

不仅可以从前往后走，还可以从后往前走。缺点是：每个节点多存一个指针，占用更多空间；增删时需要修改更多指针。

#时间复杂度

#小结

• 链表的数据分散存储，通过指针串联，不需要连续内存
• 访问慢（O(n) 顺序访问），但增删快（O(1)）
• 数组适合频繁读取，链表适合频繁增删
• 变体有循环链表（环形）和双向链表（可双向遍历）