链表（LinkedList）结构

核心特性

线性结构：元素（节点）通过指针关联，无需连续内存（数组需连续内存）

核心操作：插入（头部 / 中间 / 尾部）、删除（指定节点）、查找（指定值）、遍历

类型：单向链表（仅指向下一节点）、双向链表（前后节点互指）

代码实现（单向链表）

class LinkedList {
  constructor() {
    this.head = null; // 头节点
    this.size = 0;
  }

  // 节点类（内部使用）
  _createNode(value) {
    return { value, next: null };
  }

  // 头部插入
  insertAtHead(value) {
    const newNode = this._createNode(value);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // 尾部插入
  insertAtTail(value) {
    const newNode = this._createNode(value);
    if (this.isEmpty()) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next; // 找到最后一个节点
      }
      current.next = newNode;
    }
    this.size++;
  }

  // 删除指定值的节点（仅删除第一个匹配的）
  delete(value) {
    if (this.isEmpty()) return false;
    // 头节点匹配
    if (this.head.value === value) {
      this.head = this.head.next;
      this.size--;
      return true;
    }
    // 遍历查找匹配节点
    let current = this.head;
    while (current.next && current.next.value !== value) {
      current = current.next;
    }
    if (current.next) {
      current.next = current.next.next; // 跳过匹配节点
      this.size--;
      return true;
    }
    return false; // 未找到
  }

  // 查找指定值的节点（返回索引）
  find(value) {
    if (this.isEmpty()) return -1;
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.value === value) return index;
      current = current.next;
      index++;
    }
    return -1; // 未找到
  }

  // 遍历链表（返回值数组）
  traverse() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }

  // 判断链表是否为空
  isEmpty() {
    return this.size === 0;
  }

  // 获取链表长度
  getSize() {
    return this.size;
  }
}

与数组对比

特性         链表                数组
内存分配     非连续            连续
插入（中间） O (1)（找到节点后）   O (n)（需平移元素）
删除（中间） O (1)（找到节点后）   O (n)（需平移元素）
访问（按索引） O (n)（需遍历）    O (1)（直接索引）
适用场景     频繁增删、长数据    频繁访问、短数据

适用场景

频繁增删的长列表：如虚拟列表的节点管理（避免数组扩容 / 平移的 O (n) 开销）

数据流转：如任务调度中的任务链（每个任务节点指向下一个任务）

浏览器 History API：部分实现用双向链表存储历史记录（前进 / 后退操作）