链表的内存模型与类型 ​

数组需要连续的内存空间，如果要在中间插入元素，就得移动后面所有元素。链表解决了这个问题。

为什么需要链表 ​

数组有两个明显的局限：

1. 插入/删除效率低：在数组中间插入元素，需要移动后续所有元素，时间 O(n)
2. 需要连续内存：大数组可能因为内存碎片而分配失败

链表的设计思路完全不同：

• 元素可以散落在内存的任何位置
• 每个元素存储下一个元素的地址
• 插入/删除只需修改指针，O(1)

单链表 ​

节点结构 ​

链表由一系列节点组成，每个节点包含两部分：

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;    // 数据域：存储数据
        this.next = next;  // 指针域：指向下一个节点
    }
}

内存分布 ​

链表在内存中是这样的：

地址      |  数据  |  next
---------|--------|----------
0x1000   |   1    | 0x2000 ──┐
         |        |          │
0x2000   |   2    | 0x3000 ←─┘──┐
         |        |             │
0x3000   |   3    | null   ←────┘

逻辑视图：
[1] → [2] → [3] → null

节点不需要连续存储，通过 next 指针串联起来。

创建链表 ​

// 方式 1：逐个节点创建
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

// 方式 2：从数组创建（常用）
function createLinkedList(arr) {
    const dummy = new ListNode(0);
    let curr = dummy;
    for (const val of arr) {
        curr.next = new ListNode(val);
        curr = curr.next;
    }
    return dummy.next;
}

// 使用
const head = createLinkedList([1, 2, 3]);

这里用了一个技巧：虚拟头节点（dummy）。它简化了"第一个节点"的特殊处理，后面会经常用到。

双向链表 ​

单链表只能从前往后遍历。如果需要双向遍历，就用双向链表。

节点结构 ​

class DoublyListNode {
    constructor(val = 0, prev = null, next = null) {
        this.val = val;
        this.prev = prev;  // 前驱指针
        this.next = next;  // 后继指针
    }
}

逻辑视图 ​

null ← [1] ⇄ [2] ⇄ [3] → null

每个节点都有两个指针：prev 指向前一个节点，next 指向后一个节点。

优缺点 ​

优势：

• 双向遍历
• 删除节点时不需要先找前驱（单链表需要）

劣势：

• 每个节点多一个指针，空间开销更大
• 操作时需要维护两个指针，更容易出错

循环链表 ​

把链表的最后一个节点连回第一个节点，形成环。

单向循环链表 ​

[1] → [2] → [3] ─┐
 ↑               │
 └───────────────┘

双向循环链表 ​

┌─────────────────────┐
│                     ↓
[1] ⇄ [2] ⇄ [3]
↑                     │
└─────────────────────┘

应用场景：约瑟夫环问题、轮询调度等需要"循环"的场景。

链表 vs 数组 ​

*数组尾部插入 O(1) 是均摊复杂度
**链表尾部插入 O(n) 是因为要先遍历到尾部，如果维护尾指针则是 O(1)
***链表中间插入 O(1) 是指已知位置后的插入操作

选择建议：

• 频繁随机访问 → 数组
• 频繁插入删除 → 链表
• 两者都需要 → 考虑混合数据结构

本章小结 ​

链表是一种通过指针连接的线性数据结构：

1. 单链表：每个节点有一个 next 指针
2. 双向链表：每个节点有 prev 和 next 两个指针
3. 循环链表：尾节点指向头节点形成环
4. 核心优势：插入删除 O(1)，不需要连续内存
5. 核心劣势：不支持随机访问，有指针额外开销

下一章学习链表的基本操作：遍历、查找、插入、删除。