数组与链表

1.数组（Array）

数组特点

连续内存：数组元素在内存中紧密排列，每个元素占用相同大小的空间。
随机访问 O(1)：通过索引计算内存地址，直接读取。
插入/删除 O(n)：在中间位置插入或删除元素时，需要移动后续所有元素。

前端典型场景

列表渲染（React/Vue diff）

// React 中列表的 key 为什么要稳定？

function TodoList({ todos }) {
    return (
        <ul>
        {todos.map((todo) => (
            // key 帮助 React 识别哪些元素改变了
            <li key={todo.id}>{todo.text}</li>
        ))}
        </ul>
    );
}

数组顺序变化时，React 会对比新旧 children 数组。如果使用下标作为 key，删除第一个元素会导致所有后续元素的 key 变化，引发不必要的重渲染。这背后就是因为数组的删除操作是 O(n) 的，而 React 的 diff 算法也要遍历数组。

虚拟列表（windowing）

渲染长列表（如 10 万条数据）时，直接渲染全部 DOM 节点会导致页面卡死。虚拟列表只渲染可视区域内的元素，通过计算滚动位置动态更新数组的 startIndex 和 endIndex。

// 简化版虚拟列表核心逻辑

class VirtualList {
    private items: any[] = [];       // 全量数据（数组）
    private visibleRange: [number, number] = [0, 20];

    onScroll(scrollTop: number) {
        const start = Math.floor(scrollTop / this.itemHeight);
        const end = start + this.visibleCount;
        this.visibleRange = [start, end];
        this.render();  // 只渲染 items[start..end]
    }
}

这里利用数组的 O(1) 随机访问能力，根据索引快速拿到需要渲染的数据项。

批量数据处理

前端处理从接口返回的 JSON 数组（如报表数据、日志列表），经常需要 map、filter、reduce。这些方法都会遍历整个数组，时间复杂度 O(n)。如果数据量达到上万，就需要考虑优化。

常见优化点

避免频繁 splice

splice 在中间插入/删除时会导致后续元素内存移动。对于频繁修改的场景，考虑改用链表或对象 Map。

// ❌ 错误示例：在循环中频繁删除

let arr = [0, 1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
    if (arr[i] % 2 === 0) {
        arr.splice(i, 1); // 每次删除都移动后续元素
        i--; // 调整索引
    }
}
// 时间复杂度 O(n²)

// ✅ 改进：使用 filter 一次性生成新数组
arr = arr.filter(item => item % 2 !== 0); // O(n)

使用索引替代对象查找

如果你有一个数组，需要频繁根据某个字段查找元素，不要用 Array.find，它每次都是 O(n)。应该先用对象（Map）建立索引。

const users = [
    { id: 1, name: 'Alice' },
    { id: 2, name: 'Bob' },
    // ... 大量数据
];

// ❌ 每次查找 O(n)
function getUserById(id) {
    return users.find(u => u.id === id);
}

// ✅ 建立 Map 索引，查找 O(1)
const userMap = new Map(users.map(u => [u.id, u]));
function getUserByIdFast(id) {
    return userMap.get(id);
}

大数据量分页 / 虚拟滚动

对于超过 1000 条的数据，不要一次性渲染到 DOM。使用分页或虚拟滚动，本质上是限制数组的“可见窗口”。

2.链表（Linked List）

链表特点

非连续内存：每个节点（Node）独立存储，通过指针（引用）连接。
插入删除快（O(1)）：只需修改相邻节点的指针，无需移动元素。
查询慢（O(n)）：无法随机访问，必须从头遍历。

在 JavaScript 中，链表没有原生实现，但我们可以轻松定义一个简单的单向链表或双向链表。

// 单向链表节点
class ListNode<T> {
  value: T;
  next: ListNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

// 双向链表节点（React Fiber 使用的就是类似结构）
class DoublyListNode<T> {
  value: T;
  next: DoublyListNode<T> | null = null;
  prev: DoublyListNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

前端思维映射

Fiber 架构（类似链表调度）

React 16+ 的 Fiber 架构将渲染工作拆分成多个小任务，每个 Fiber 节点就是一个链表节点。Fiber 树采用单向链表的 child、sibling、return 指针来遍历，使得 React 可以暂停、恢复、优先级调度。
```
// 简化版 Fiber 节点结构

interface FiberNode {
    type: 'div' | 'span' | ...;
    child: FiberNode | null;     // 第一个子节点
    sibling: FiberNode | null;   // 下一个兄弟节点
    return: FiberNode | null;    // 父节点
    // ... 其他属性（stateNode, memoizedProps 等）
}
```
利用链表结构，React 可以在不依赖调用栈的情况下实现“可中断的递归”。

中间件链（如 Redux / Koa）

Redux 的中间件通过手动调用 next(action) 形成一条链式调用的“洋葱模型”。每个中间件相当于链表的一个节点，next 指向下一个中间件。

// Redux 中间件简化示意

type Middleware = (store: any) => (next: any) => (action: any) => any;

function applyMiddleware(...middlewares: Middleware[]) {
    return (createStore) => (reducer) => {
        const store = createStore(reducer);
        let dispatch = store.dispatch;

        // 中间件链：每个中间件包装 dispatch
        const chain = middlewares.map(m => m(store));
        // 类似链表的 reduce 构建调用链
        dispatch = chain.reduceRight((next, middleware) => middleware(next), dispatch);

        return { ...store, dispatch };
    };
}

Koa 的中间件也是类似的链表思想，每个 await next() 会执行下一个中间件。

任务调度队列

前端中的任务队列（如事件循环中的微任务、宏任务）本质上是一个队列，可以用链表实现。相比数组实现的队列，链表队列在入队、出队时都有 O(1) 性能，而数组实现的 shift() 是 O(n)。

// 用链表实现队列（FIFO）
class Queue<T> {
    private head: ListNode<T> | null = null;
    private tail: ListNode<T> | null = null;

    enqueue(value: T): void {
        const node = new ListNode(value);
        if (this.tail) {
        this.tail.next = node;
        this.tail = node;
        } else {
        this.head = this.tail = node;
        }
    }

    dequeue(): T | null {
        if (!this.head) return null;
        const value = this.head.value;
        this.head = this.head.next;
        if (!this.head) this.tail = null;
        return value;
    }
}

关键认知

链表本质是“指针关系”，适合频繁插入删除场景

在前端业务中，真正需要手动写链表的机会不多（因为数组 + 优化已经够用），但链表的思想无处不在：

当你需要维护一个可暂停、可恢复的遍历任务时，链表比递归栈更可控。
当你有大量的动态插入/删除（如实时日志、游戏实体管理），数组频繁 splice 代价高，链表是更好的选择。
当数据量很小（几百以内），数组的简单性完全占优；只有达到一定规模或特定场景（如编辑器撤销栈、LRU 缓存），才值得引入链表。

3. 实战对比：数组 vs 链表性能测试

写一个简单的 benchmark，感受一下差异：

// 测试在头部插入 10000 个元素
function testArrayPrepend() {
  const arr: number[] = [];
  console.time('Array prepend');
  for (let i = 0; i < 10000; i++) {
    arr.unshift(i);  // O(n) 每次
  }
  console.timeEnd('Array prepend');
}

function testLinkedListPrepend() {
  class Node {
    value: number;
    next: Node | null = null;
    constructor(v: number) { this.value = v; }
  }
  let head: Node | null = null;
  console.time('LinkedList prepend');
  for (let i = 0; i < 10000; i++) {
    const node = new Node(i);
    node.next = head;
    head = node;   // O(1)
  }
  console.timeEnd('LinkedList prepend');
}

testArrayPrepend();      // Array prepend: ~4ms (具体数值取决于环境)
testLinkedListPrepend(); // LinkedList prepend: ~0.3ms

而在随机访问场景，数组完胜：

function testArrayAccess(list: number[]) {
  console.time('Array random access');
  let sum = 0;
  for (let i = 0; i < 100000; i++) {
    sum += list[Math.floor(Math.random() * list.length)];
  }
  console.timeEnd('Array random access');
}

function testLinkedListAccess(head: Node | null, length: number) {
  console.time('LinkedList random access');
  let sum = 0;
  for (let i = 0; i < 100000; i++) {
    let idx = Math.floor(Math.random() * length);
    let cur = head;
    while (idx-- && cur) cur = cur.next; // O(n)
    if (cur) sum += cur.value;
  }
  console.timeEnd('LinkedList random access');
}
// 数组访问比链表快几个数量级

4. 总结

场景	推荐数据结构	原因
随机访问频繁（如表格展示、虚拟列表）	数组	O(1) 索引
频繁在头部/中间插入删除（如任务队列、撤销栈）	链表	O(1) 改指针
绝大部分前端业务（数据量<5000）	数组	简单、缓存友好、原生方法丰富
需要可中断遍历（如 Fiber、异步任务）	链表	指针控制灵活，不依赖递归栈

前端开发者的自我修养：

默认使用数组，它足够快且 API 丰富。
当遇到性能瓶颈（如 splice、unshift 导致大量重绘或耗时），先考虑算法优化（建立索引、批量处理、虚拟滚动），再考虑重构为链表。
学习链表的“指针思维”，它能帮你理解 React Fiber、Redux 中间件、Koa 洋葱模型等高级架构。