JavaScript LinkedList

学习目标

理解链表的基本结构与工作原理
掌握在 JavaScript 中实现单向链表的核心方法（创建、追加、删除、打印）
能够区分链表与数组的优劣及适用场景
了解链表在实际系统中的典型应用
避免常见实现错误，写出健壮的链表代码

什么是链表

链表（Linked List） 是一种线性数据结构，由一系列节点（Node） 组成。每个节点包含两部分：

数据（value）：存储实际值
指针（next）：指向下一个节点的引用（若为最后一个节点，则指向 null）

链表从头节点（head） 开始，通过 next 指针依次连接，形成一条“链条”。

关键特性：
动态大小：可随时增长或缩小
非连续内存：节点可分散在内存各处
顺序访问：必须从头开始遍历，无法像数组那样随机访问

JS 实现链表

1. 定义节点类

class Node {
    constructor(value) {
        this.value = value;   // 存储数据
        this.next = null;     // 指向下一个节点
    }
}

2. 定义链表类

class LinkedList {
    constructor() {
        this.head = null; // 初始时链表为空
    }

    // 在链表末尾添加新节点
    append(value) {
        const newNode = new Node(value);
        
        // 如果链表为空，新节点即为头节点
        if (!this.head) {
            this.head = newNode;
            return;
        }

        // 否则遍历到末尾，将新节点接上
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 打印整个链表（用于调试）
    printList() {
        let current = this.head;
        let result = "";
        while (current) {
            result += current.value + "->";
            current = current.next;
        }
        console.log(result + "null");
    }
}

3. 使用示例

const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList(); // 输出：10->20->30->null

扩展操作：删除节点

在基础实现上，增加 delete 方法以支持按值删除节点。

delete(value) {
    // 链表为空
    if (!this.head) {
        console.log("链表为空，无元素可删除");
        return;
    }

    // 要删除的是头节点
    if (this.head.value === value) {
        this.head = this.head.next;
        return;
    }

    // 查找目标节点
    let prev = null;
    let current = this.head;
    while (current && current.value !== value) {
        prev = current;
        current = current.next;
    }

    // 未找到该值
    if (!current) {
        console.log("未在链表中找到值：" + value);
        return;
    }

    // 跳过当前节点（即删除）
    prev.next = current.next;
}

删除示例

const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.delete(20);
list.printList(); // 输出：10->30->null

链表 vs 数组

特性	链表（LinkedList）	数组（Array）
内存布局	非连续（节点分散）	连续
大小	动态，可任意扩展	固定（虽 JS 数组可变，但底层可能重分配）
插入 / 删除效率	O(1)（已知位置）；O(n)（需查找）	O(n)（需移动后续元素）
访问效率	O(n)（必须从头遍历）	O(1)（通过索引直接访问）
内存开销	每个节点额外存储 `next` 指针	仅存储数据

何时用链表？
当频繁在中间插入 / 删除，且不需要随机访问时。

链表应用场景

浏览器历史记录
- 前进 / 后退功能天然适合双向链表（本例为单向，但原理相通）
音乐播放列表
- 动态增删歌曲，无需重新分配大块内存
操作系统内存管理
- 管理空闲内存块（如伙伴系统）
实时任务调度
- RTOS 中动态添加 / 移除任务队列
社交平台信息流
- 用户动态可随时插入（如置顶）、删除，保持顺序

链表的优势

动态扩容：无需预先指定大小
高效插入 / 删除：只需修改指针，无需移动大量数据
内存灵活：不要求连续内存空间，适合碎片化内存环境
基础构建块：可用于实现栈、队列、图等更复杂结构

注意：JavaScript 引擎对数组高度优化，日常开发中除非有明确需求，否则优先使用数组。链表主要用于理解数据结构或特定性能场景。

重点总结

操作	实现要点
创建链表	`head = null` 表示空链表
追加节点	遍历至 `current.next === null`，然后挂载新节点
删除节点	处理三种情况：空链表、删除头节点、删除中间 / 尾节点
打印链表	从 `head` 开始遍历，拼接字符串
查找节点	需从头遍历（O(n) 时间复杂度）
内存特点	每个节点独立分配，通过指针连接

思考题

当前实现的 append 方法时间复杂度是多少？如何优化频繁尾部插入的性能？
如果要实现在指定位置插入节点（如 insertAt(index, value)），你会如何设计？
单向链表无法高效地从后往前遍历。如果需要支持反向遍历，应使用什么结构？请简述其节点设计。

源本科技 | 码上会

学习目标

什么是链表

JS 实现链表

1. 定义节点类

2. 定义链表类

3. 使用示例

扩展操作：删除节点

链表 vs 数组

链表应用场景

链表的优势

重点总结

思考题