当函数调用层层嵌套，JavaScript 引擎如何管理这些调用？当事件循环处理异步任务时，背后的数据结构是什么？本文将深入探讨栈、队列和树在前端开发中的核心应用。

前言：从函数调用说起

// 一个简单的函数调用栈示例
function funcA() {
    console.log('进入函数A');
    funcB();
    console.log('离开函数A');
}

function funcB() {
    console.log('进入函数B');
    funcC();
    console.log('离开函数B');
}

function funcC() {
    console.log('进入函数C');
    console.log('离开函数C');
}

funcA();

这段代码的输出顺序是什么？进入函数A 进入函数B 进入函数C 离开函数C 离开函数B 离开函数A 。

这种"先进后出"的执行顺序，正是栈的典型特征。

栈（Stack）的实现与应用

栈的基本概念

栈 是一种后进先出（LIFO）的数据结构，就像一摞盘子，我们只能从最上面取放盘子。

栈的操作示意图

      push(3)      push(5)      pop() → 5
┌───┐    →    ┌───┐    →    ┌───┐    →    ┌───┐
│   │         │ 3 │         │ 5 │         │ 3 │
├───┤         ├───┤         ├───┤         ├───┤
│   │         │   │         │ 3 │         │   │
└───┘         └───┘         └───┘         └───┘
 空栈          栈底:3        栈顶:5        栈底:3

用数组实现栈

class ArrayStack {
  constructor(capacity = 10) {
    this.items = new Array(capacity);  // 底层数组
    this.top = -1;                     // 栈顶指针
    this.capacity = capacity;          // 栈容量
  }

  // 入栈操作
  push(element) {
    if (this.isFull()) {
      throw new Error('栈已满');
    }
    this.top++;
    this.items[this.top] = element;
    return this;
  }

  // 出栈操作
  pop() {
    if (this.isEmpty()) {
      throw new Error('栈为空');
    }
    const element = this.items[this.top];
    this.items[this.top] = undefined;  // 清理引用
    this.top--;
    return element;
  }

  // 查看栈顶元素（不弹出）
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.top];
  }

  // 判断栈是否为空
  isEmpty() {
    return this.top === -1;
  }

  // 判断栈是否已满
  isFull() {
    return this.top === this.capacity - 1;
  }

  // 获取栈大小
  get size() {
    return this.top + 1;
  }

  // 清空栈
  clear() {
    this.items = new Array(this.capacity);
    this.top = -1;
  }
}

用链表实现栈

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;    // 栈顶节点
    this.length = 0;    // 栈长度
  }

  // 入栈操作
  push(element) {
    // 创建新节点，指向原来的栈顶
    const newNode = new ListNode(element, this.top);
    this.top = newNode;
    this.length++;
    return this;
  }

  // 出栈操作
  pop() {
    if (this.isEmpty()) {
      throw new Error('栈为空');
    }
    const value = this.top.value;
    this.top = this.top.next;  // 移动栈顶指针
    this.length--;
    return value;
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.top.value;
  }

  isEmpty() {
    return this.top === null;
  }

  get size() {
    return this.length;
  }

  clear() {
    this.top = null;
    this.length = 0;
  }
}

数组栈 vs 链表栈

• 数组栈：内存连续，CPU缓存友好，访问速度快
• 链表栈：动态扩容，无容量限制，但内存不连续
• 实际选择：JavaScript 数组经过V8引擎优化，通常数组栈性能更好

栈的实际应用

应用1：函数调用栈模拟

class CallStackSimulator {
  constructor() {
    this.callStack = new ArrayStack(50);
    this.currentDepth = 0;
    this.maxDepth = 0;
  }

  // 函数调用
  callFunction(funcName) {
    const frame = {
      funcName,
      timestamp: Date.now(),
      localVars: {}
    };

    this.callStack.push(frame);
    this.currentDepth++;
    this.maxDepth = Math.max(this.maxDepth, this.currentDepth);

    console.log(`调用: ${funcName} (深度: ${this.currentDepth})`);
    this.printStack();

    return frame;
  }

  // 函数返回
  returnFromFunction() {
    if (this.callStack.isEmpty()) {
      console.log('调用栈已空');
      return null;
    }

    const frame = this.callStack.pop();
    const duration = Date.now() - frame.timestamp;
    this.currentDepth--;

    console.log(`返回: ${frame.funcName} (耗时: ${duration}ms)`);
    console.log(`剩余深度: ${this.currentDepth}`);

    return frame;
  }
}

队列（Queue）与双端队列（Deque）

队列（Queue）的基本概念

队列 是一种先进先出（FIFO）的数据结构，就像排队买票，先来的人先服务。

队列的操作示意图

      enqueue(3)    enqueue(5)    dequeue() → 3
┌───┬───┐  →  ┌───┬───┐  →  ┌───┬───┐  →  ┌───┬───┐
│   │   │     │ 3 │   │     │ 3 │ 5 │     │   │ 5 │
└───┴───┘     └───┴───┘     └───┴───┘     └───┴───┘
front rear   front↑rear    front rear↑     ↑front rear

双端队列（Deque）的基本概念

双端队列 允许在两端进行插入和删除操作，结合了栈和队列的特性。

双端队列的实现

class Deque {
  constructor(capacity = 10) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.front = 0;
    this.rear = 0;
    this.count = 0;
  }

  // 前端添加
  addFront(element) {
    if (this.isFull()) {
      this._resize();
    }

    this.front = (this.front - 1 + this.capacity) % this.capacity;
    this.items[this.front] = element;
    this.count++;

    console.log(`前端添加: ${element}, front: ${this.front}`);
    return this;
  }

  // 后端添加
  addRear(element) {
    if (this.isFull()) {
      this._resize();
    }

    this.items[this.rear] = element;
    this.rear = (this.rear + 1) % this.capacity;
    this.count++;

    console.log(`后端添加: ${element}, rear: ${this.rear}`);
    return this;
  }

  // 前端删除
  removeFront() {
    if (this.isEmpty()) {
      throw new Error('队列为空');
    }

    const element = this.items[this.front];
    this.items[this.front] = undefined;
    this.front = (this.front + 1) % this.capacity;
    this.count--;

    console.log(`前端删除: ${element}, front: ${this.front}`);
    return element;
  }

  // 后端删除
  removeRear() {
    if (this.isEmpty()) {
      throw new Error('队列为空');
    }

    this.rear = (this.rear - 1 + this.capacity) % this.capacity;
    const element = this.items[this.rear];
    this.items[this.rear] = undefined;
    this.count--;

    console.log(`后端删除: ${element}, rear: ${this.rear}`);
    return element;
  }

  // 查看前端
  peekFront() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.front];
  }

  // 查看后端
  peekRear() {
    if (this.isEmpty()) {
      return null;
    }
    const index = (this.rear - 1 + this.capacity) % this.capacity;
    return this.items[index];
  }

  // 扩容
  _resize() {
    const newCapacity = this.capacity * 2;
    const newItems = new Array(newCapacity);

    // 复制元素到新数组
    for (let i = 0; i < this.count; i++) {
      const index = (this.front + i) % this.capacity;
      newItems[i] = this.items[index];
    }

    this.items = newItems;
    this.front = 0;
    this.rear = this.count;
    this.capacity = newCapacity;

    console.log(`队列扩容: ${this.capacity / 2} → ${newCapacity}`);
  }

  isEmpty() {
    return this.count === 0;
  }

  isFull() {
    return this.count === this.capacity;
  }

  get size() {
    return this.count;
  }
}

队列的实际应用

应用1：任务调度器

class TaskScheduler {
  constructor() {
    this.taskQueue = new CircularQueue(100);  // 任务队列
    this.currentTask = null;
    this.taskId = 0;
    this.isProcessing = false;
  }

  // 创建任务
  createTask(name, duration, priority = 0) {
    return {
      id: ++this.taskId,
      name,
      duration,      // 任务执行时间（毫秒）
      priority,      // 优先级（数值越小优先级越高）
      status: 'pending',
      createdAt: Date.now(),
      startedAt: null,
      completedAt: null
    };
  }

  // 添加任务到队列
  addTask(task) {
    this.taskQueue.enqueue(task);
    console.log(`任务添加: ${task.name} (ID: ${task.id})`);
    this.printQueueStatus();

    // 如果没有正在处理的任务，开始处理
    if (!this.isProcessing) {
      this.processNextTask();
    }
  }

  // 处理下一个任务
  async processNextTask() {
    if (this.taskQueue.isEmpty()) {
      this.isProcessing = false;
      console.log('所有任务处理完成！');
      return;
    }

    this.isProcessing = true;
    this.currentTask = this.taskQueue.dequeue();
    this.currentTask.status = 'processing';
    this.currentTask.startedAt = Date.now();

    console.log(`\n开始处理任务: ${this.currentTask.name}`);
    console.log(`任务ID: ${this.currentTask.id}, 预计耗时: ${this.currentTask.duration}ms`);
    this.printQueueStatus();

    // 模拟任务执行
    await this.executeTask(this.currentTask);

    // 任务完成
    this.currentTask.completedAt = Date.now();
    this.currentTask.status = 'completed';
    const totalTime = this.currentTask.completedAt - this.currentTask.startedAt;

    console.log(`任务完成: ${this.currentTask.name}`);
    console.log(`实际耗时: ${totalTime}ms`);

    // 处理下一个任务
    setTimeout(() => {
      this.processNextTask();
    }, 0);
  }

  // 模拟任务执行
  executeTask(task) {
    return new Promise(resolve => {
      setTimeout(() => {
        resolve();
      }, task.duration);
    });
  }
}

树（Tree）的实现与应用

树的基本概念

树是一种分层的数据结构，由节点和边组成。每个节点有零个或多个子节点，没有父节点的节点称为根节点；没有子节点的节点称为叶子节点。

二叉树结构示意图

        A (根节点)
       / \
      B   C
     / \   \
    D   E   F
   /
  G

术语解释：

• 根节点: A
• 叶子节点: E, F, G
• 深度: 节点G的深度是3
• 高度: 树的高度是3
• 子树: B、D、E、G构成一个子树

二叉树的实现

class TreeNode {
  constructor(value) {
    this.value = value;    // 节点值
    this.left = null;      // 左子节点
    this.right = null;     // 右子节点
    this.parent = null;    // 父节点（可选）
  }

  // 判断是否为叶子节点
  isLeaf() {
    return this.left === null && this.right === null;
  }

  // 判断是否有左子节点
  hasLeft() {
    return this.left !== null;
  }

  // 判断是否有右子节点
  hasRight() {
    return this.right !== null;
  }

  // 获取高度
  getHeight() {
    const leftHeight = this.left ? this.left.getHeight() : 0;
    const rightHeight = this.right ? this.right.getHeight() : 0;
    return Math.max(leftHeight, rightHeight) + 1;
  }
}

二叉树遍历算法

class BinaryTree {
  constructor() {
    this.root = null;  // 根节点
  }

  // 前序遍历：根 → 左 → 右
  preorderTraversal(callback) {
    const result = [];
    this._preorder(this.root, callback, result);
    return result;
  }

  _preorder(node, callback, result) {
    if (node === null) return;

    // 访问当前节点
    if (callback) callback(node);
    result.push(node.value);

    // 遍历左子树
    this._preorder(node.left, callback, result);

    // 遍历右子树
    this._preorder(node.right, callback, result);
  }

  // 中序遍历：左 → 根 → 右（对二叉搜索树会得到有序序列）
  inorderTraversal(callback) {
    const result = [];
    this._inorder(this.root, callback, result);
    return result;
  }

  _inorder(node, callback, result) {
    if (node === null) return;

    // 遍历左子树
    this._inorder(node.left, callback, result);

    // 访问当前节点
    if (callback) callback(node);
    result.push(node.value);

    // 遍历右子树
    this._inorder(node.right, callback, result);
  }

  // 后序遍历：左 → 右 → 根
  postorderTraversal(callback) {
    const result = [];
    this._postorder(this.root, callback, result);
    return result;
  }

  _postorder(node, callback, result) {
    if (node === null) return;

    // 遍历左子树
    this._postorder(node.left, callback, result);

    // 遍历右子树
    this._postorder(node.right, callback, result);

    // 访问当前节点
    if (callback) callback(node);
    result.push(node.value);
  }

  // 层序遍历：按层级从上到下，从左到右
  levelOrderTraversal(callback) {
    if (this.root === null) return [];

    const result = [];
    const queue = new CircularQueue(100);
    queue.enqueue(this.root);

    while (!queue.isEmpty()) {
      const node = queue.dequeue();

      // 访问当前节点
      if (callback) callback(node);
      result.push(node.value);

      // 将子节点加入队列
      if (node.left) {
        queue.enqueue(node.left);
      }
      if (node.right) {
        queue.enqueue(node.right);
      }
    }

    return result;
  }

  // 深度优先搜索（DFS）
  dfs(targetValue) {
    return this._dfs(this.root, targetValue);
  }

  _dfs(node, targetValue) {
    if (node === null) return null;

    // 检查当前节点
    if (node.value === targetValue) {
      return node;
    }

    // 搜索左子树
    const leftResult = this._dfs(node.left, targetValue);
    if (leftResult !== null) {
      return leftResult;
    }

    // 搜索右子树
    return this._dfs(node.right, targetValue);
  }

  // 广度优先搜索（BFS）
  bfs(targetValue) {
    if (this.root === null) return null;

    const queue = new CircularQueue(100);
    queue.enqueue(this.root);

    while (!queue.isEmpty()) {
      const node = queue.dequeue();

      // 检查当前节点
      if (node.value === targetValue) {
        return node;
      }

      // 将子节点加入队列
      if (node.left) {
        queue.enqueue(node.left);
      }
      if (node.right) {
        queue.enqueue(node.right);
      }
    }
    return null;
  }
}

数据结构选择的关键因素

访问模式

• 随机访问：数组（O(1)）
• 顺序访问：链表、栈、队列
• 层级访问：树

操作频率

• 频繁插入/删除开头：链表
• 频繁插入/删除两端：双端队列
• 频繁随机访问：数组

内存考虑

• 内存连续：数组（缓存友好）
• 内存分散：链表（无扩容成本）
• 动态大小：链表、树

结语

本文讲解了栈、队列和树的实现与应用，理解这些数据结构，不仅能帮助我们在面试中表现出色，更能让我们在实际开发中写出更高效、更可靠的代码。对于文章中错误的地方或者有任何问题，欢迎在评论区留言讨论！

数组在 JavaScript 中如此方便，为什么我们还需要链表呢？当 V8 引擎处理数组时，链表又在哪些场景下更有优势？本篇文章将深入探讨数据结构的核心差异。

前言：从一道面试题说起

// 面试题：如何高效地从大型数据集合中频繁插入和删除元素？
const data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

// 场景1：在数组开头插入元素（性能如何？）
data.unshift(0); // 需要移动所有元素！

// 场景2：在数组中间删除元素（性能如何？）
data.splice(5, 1); // 需要移动一半的元素！

// 场景3：只需要顺序访问数据
for (let i = 0; i < data.length; i++) {
    console.log(data[i]); // 数组很快！
}

那么问题来了：有没有一种数据结构，插入和删除快，顺序访问也快？当然有，答案就是：链表！ 数组和链表是编程中最基础的两种数据结构，理解它们的差异能帮助我们在不同场景下做出最优选择。

理解数组与链表的本质差异

内存结构对比

我们先通过一个简图，观察一下数组和链表在内存中的存储方式：

数组的内存结构（连续存储）

┌─────┬─────┬─────┬─────┬─────┐
│  0  │  1  │  2  │  3  │  4  │ ← 索引
├─────┼─────┼─────┼─────┼─────┤
│  10 │  20 │  30 │  40 │  50 │ ← 值
└─────┴─────┴─────┴─────┴─────┘
地址: 1000 1004 1008 1012 1016 （假设每个元素占4字节）

数组的存储特点：

1. 连续的内存空间
2. 通过索引直接计算地址：地址 = 基地址 + 索引 × 元素大小
3. 随机访问时间复杂度：O(1)

链表的内存结构（非连续存储）

      ┌─────┐    ┌─────┐    ┌─────┐
头 →  │  10 │ →  │  20 │ →  │  30 │ → null
      └─────┘    └─────┘    └─────┘
地址:  2000       3040       4080  （地址不连续）

链表的特点

1. 非连续的内存空间
2. 每个节点包含数据和指向下一个节点的指针
3. 随机访问需要遍历：O(n)
4. 插入和删除只需要修改指针：O(1)

时间复杂度对比表

数据结构	访问	插入开头	插入结尾	插入中间	删除开头	删除结尾	删除中间	搜索
数组	O(1)	O(n)	O(1)	O(n)	O(n)	O(1)	O(n)	O(n)
单向链表	O(n)	O(1)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)
双向链表	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)	O(n)	O(n)
带尾指针的单向链表	O(n)	O(1)	O(1)	O(n)	O(1)	O(n)	O(n)	O(n)

关键差异总结

1. 随机访问元素：数组完胜（O(1) vs O(n)）
2. 插入/删除开头：链表完胜（O(1) vs O(n)）
3. 插入/删除结尾：数组和双向链表都很快
4. 插入/删除中间：都不快，但链表稍好
5. 内存使用：数组更紧凑，链表有指针开销

实现单向链表

基础节点类

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

单向链表类

class LinkedList {
  constructor() {
    this.head = null;    // 链表头节点
    this.length = 0;     // 链表长度
  }

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

  // 在链表头部添加节点
  addFirst(value) {
    // 创建新节点，指向原来的头节点
    const newNode = new ListNode(value, this.head);
    // 更新头节点为新节点
    this.head = newNode;
    this.length++;
    return this;
  }

  // 在链表尾部添加节点
  addLast(value) {
    const newNode = new ListNode(value);
    // 如果链表为空，新节点就是头节点
    if (this.head == null) {
      this.head = newNode;
    } else {
      // 找到最后一个节点
      let current = this.head;
      while (current.next != null) {
        current = current.next;
      }
      // 将新节点添加到末尾
      current.next = newNode;
    }
    this.length++;
    return this;
  }

  // 删除头节点
  removeFirst() {
    if (this.head == null) {
      return null;
    }
    const removedValue = this.head.value;
    this.head = this.head.next;
    this.length--;

    return removedValue;
  }

  // 删除尾节点
  removeLast() {
    if (this.head == null) {
      return null;
    }
    // 如果只有一个节点
    if (this.head.next == null) {
      const removedValue = this.head.value;
      this.head = null;
      this.length--;
      return removedValue;
    }
    // 找到倒数第二个节点
    let current = this.head;
    while (current.next.next != null) {
      current = current.next;
    }
    const removedValue = current.next.value;
    current.next = null;
    this.length--;
    return removedValue;
  }
}

单向链表的实际应用

应用1：浏览器历史记录

class BrowserHistory {
  constructor() {
    this.history = new LinkedList();
    this.current = null;
  }

  // 访问新页面
  visit(url) {
    // 如果当前有页面，添加到历史记录
    if (this.current !== null) {
      this.history.addLast(this.current);
    }
    this.current = url;
    console.log(`访问: ${url}`);
  }

  // 后退
  back() {
    if (this.history.size === 0) {
      console.log('无法后退：已经是第一页');
      return null;
    }
    const previous = this.history.removeLast();
    const current = this.current;
    this.current = previous;
    console.log(`后退: ${current} → ${previous}`);
    return previous;
  }

  // 查看历史记录
  showHistory() {
    console.log('历史记录:');
    this.history.forEach((url, index) => {
      console.log(`  ${index + 1}. ${url}`);
    });
    console.log(`当前: ${this.current}`);
  }
}

应用2：任务队列

class TaskQueue {
  constructor() {
    this.queue = new LinkedList();
  }

  // 添加任务
  enqueue(task) {
    this.queue.addLast(task);
    console.log(`添加任务: ${task.name}`);
  }

  // 执行下一个任务
  dequeue() {
    if (this.queue.isEmpty()) {
      console.log('任务队列为空');
      return null;
    }

    const task = this.queue.removeFirst();
    console.log(`执行任务: ${task.name}`);

    // 模拟任务执行
    try {
      task.execute();
    } catch (error) {
      console.error(`任务执行失败: ${error.message}`);
    }

    return task;
  }

  // 查看下一个任务（不执行）
  peek() {
    if (this.queue.isEmpty()) {
      return null;
    }
    return this.queue.get(0);
  }

  // 清空任务队列
  clear() {
    this.queue = new LinkedList();
    console.log('任务队列已清空');
  }

  // 获取队列长度
  get size() {
    return this.queue.size;
  }

  // 打印队列状态
  printQueue() {
    console.log('当前任务队列:');
    this.queue.forEach((task, index) => {
      console.log(`  ${index + 1}. ${task.name}`);
    });
  }
}

实现双向链表

基础节点类

class ListNode {
  constructor(value, next = null) {
    this.value = value;  // 存储的数据
    this.next = next;    // 指向下一个节点的指针
    this.prev = prev;    // 指向前一个节点的指针
  }
}

双向链表类

class DoublyLinkedList {
  constructor() {
    this.head = null;    // 链表头节点
    this.tail = null;    // 链表尾节点
    this.length = 0;     // 链表长度
  }

  get size() {
    return this.length;
  }

  // 在头部添加节点
  addFirst(value) {
    const newNode = new DoubleListNode(value, null, this.head);

    if (this.head !== null) {
      this.head.prev = newNode;
    } else {
      // 如果链表为空，新节点也是尾节点
      this.tail = newNode;
    }

    this.head = newNode;
    this.length++;
    return this;
  }

  // 在尾部添加节点
  addLast(value) {
    const newNode = new DoubleListNode(value, this.tail, null);

    if (this.tail !== null) {
      this.tail.next = newNode;
    } else {
      // 如果链表为空，新节点也是头节点
      this.head = newNode;
    }

    this.tail = newNode;
    this.length++;
    return this;
  }

  // 删除头节点
  removeFirst() {
    if (this.head === null) {
      return null;
    }

    const removedValue = this.head.value;

    if (this.head === this.tail) {
      // 只有一个节点
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.head.prev = null;
    }

    this.length--;
    return removedValue;
  }

  // 删除尾节点
  removeLast() {
    if (this.tail === null) {
      return null;
    }

    const removedValue = this.tail.value;

    if (this.head === this.tail) {
      // 只有一个节点
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail.next = null;
    }

    this.length--;
    return removedValue;
  }
}

双向链表的实际应用

应用1：浏览器历史记录（增强版）

class EnhancedBrowserHistory {
  constructor() {
    this.history = new DoublyLinkedList();
    this.current = null;
    this.currentIndex = -1;
  }

  // 访问新页面
  visit(url) {
    console.log(`访问: ${url}`);

    // 如果当前位置不在末尾，需要截断后面的历史
    if (this.currentIndex < this.history.size - 1) {
      // 移除当前位置之后的所有历史
      const removeCount = this.history.size - 1 - this.currentIndex;
      for (let i = 0; i < removeCount; i++) {
        this.history.removeLast();
      }
    }

    // 添加新页面到历史记录
    if (this.current !== null) {
      this.history.addLast(this.current);
    }

    this.current = url;
    this.currentIndex = this.history.size;

    this.printHistory();
  }

  // 后退
  back() {
    if (this.currentIndex <= 0) {
      console.log('无法后退：已经是第一页');
      return null;
    }

    this.currentIndex--;
    this.current = this.history.get(this.currentIndex);

    console.log(`后退到: ${this.current}`);
    this.printHistory();

    return this.current;
  }

  // 前进
  forward() {
    if (this.currentIndex >= this.history.size - 1) {
      console.log('无法前进：已经是最后一页');
      return null;
    }

    this.currentIndex++;
    this.current = this.currentIndex === this.history.size ?
      '当前页面' : this.history.get(this.currentIndex);

    console.log(`前进到: ${this.current}`);
    this.printHistory();

    return this.current;
  }

  // 查看历史记录
  printHistory() {
    console.log('历史记录:');
    this.history.forEach((url, index) => {
      const marker = index === this.currentIndex ? '← 当前' : '';
      console.log(`  ${index + 1}. ${url} ${marker}`);
    });

    if (this.currentIndex === this.history.size) {
      console.log(`  当前: ${this.current}`);
    }
  }

  // 跳转到指定历史
  go(index) {
    if (index < 0 || index > this.history.size) {
      console.log(`无效的历史位置: ${index}`);
      return null;
    }

    this.currentIndex = index;
    this.current = index === this.history.size ?
      '当前页面' : this.history.get(index);

    console.log(`跳转到: ${this.current}`);
    this.printHistory();

    return this.current;
  }
}

核心要点总结

数组 vs 链表的本质差异

• 数组：连续内存，随机访问快(O(1))，插入删除慢(O(n))
• 链表：非连续内存，随机访问慢(O(n))，插入删除快(O(1))
• JavaScript数组：是特殊对象，V8引擎会优化存储方式

单向链表 vs 双向链表

• 单向链表：每个节点只有一个指针(next)，内存开销小
• 双向链表：每个节点有两个指针(prev, next)，支持双向遍历
• 选择：需要反向操作时用双向链表，否则用单向链表

结语

数据结构的选择没有绝对的对错，只有适合与否。理解数组和链表的差异，能帮助我们在实际开发中做出更明智的选择，写出更高效的代码。对于文章中错误的地方或者有任何问题，欢迎在评论区留言讨论！