1. 数据结构基础：从链表开始说起

链表这种数据结构就像一列火车，每个车厢（节点）通过挂钩（指针）连接。在JavaScript中可以通过对象轻松实现：

// 实现单链表（技术栈：原生JavaScript）
class Node {
  constructor(data) {
    this.data = data;
    this.next = null; // 下一节点的指针
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  // 在末尾添加节点（类似火车加挂车厢）
  append(data) {
    const newNode = new Node(data);
    
    // 当链表为空时直接设置头部
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      // 找到最后一个节点
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.length++;
  }

  // 删除指定位置的节点（类似拆开车厢连接）
  removeAt(position) {
    if (position < 0 || position >= this.length) return null;
    
    let current = this.head;
    if (position === 0) {
      this.head = current.next;
    } else {
      let index = 0;
      let previous = null;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }
    this.length--;
    return current.data;
  }
}

// 使用示例
const train = new LinkedList();
train.append("机车头");
train.append("油罐车厢");
train.append("冷藏车厢");
console.log(train.removeAt(1)); // 输出"油罐车厢"

应用场景：文件版本控制系统使用链表记录修改历史，浏览器前进后退功能基于双向链表实现。相比于数组的连续存储，链表能实现O(1)的插入删除，但随机访问需要O(n)时间。

2. 栈与队列：程序世界的收纳法则

2.1 栈：后进先出的智慧

浏览器后退按钮就是个典型栈应用：

// 实现栈结构（技术栈：TypeScript）
interface Stack<T> {
  push(item: T): void;
  pop(): T | undefined;
  peek(): T | undefined;
  size(): number;
}

class ArrayStack<T> implements Stack<T> {
  private items: T[] = [];

  // 入栈（像叠盘子）
  push(item: T) {
    this.items.push(item);
  }

  // 出栈（取最上层盘子）
  pop(): T | undefined {
    return this.items.pop();
  }

  // 查看栈顶（不改变栈）
  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  // 获取容量
  size(): number {
    return this.items.length;
  }
}

// 使用示例
const browserHistory = new ArrayStack<string>();
browserHistory.push("首页");
browserHistory.push("商品页");
browserHistory.push("购物车");
console.log(browserHistory.pop()); // 输出"购物车"

2.2 队列：先进先出的哲学

打印机任务队列是队列的经典应用：

// 实现队列（技术栈：JavaScript Class）
class Queue {
  constructor() {
    this.items = [];
    this.frontIndex = 0; // 优化性能的指针
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const item = this.items[this.frontIndex];
    this.frontIndex++;
    // 自动清理内存空间（当超过50%空间空闲时重置）
    if (this.frontIndex > this.items.length / 2) {
      this.items = this.items.slice(this.frontIndex);
      this.frontIndex = 0;
    }
    return item;
  }

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

  size() {
    return this.items.length - this.frontIndex;
  }
}

// 使用示例
const printerQueue = new Queue();
printerQueue.enqueue("财务报表.pdf");
printerQueue.enqueue("产品手册.docx");
console.log(printerQueue.dequeue()); // 输出"财务报表.pdf"

注意事项：当需要控制队列最大容量时，应该实现环形队列避免内存溢出。JavaScript的微任务队列就是基于队列结构的特殊实现。

3. 排序算法：数据的编排艺术

3.1 冒泡排序的温暖怀抱

// 冒泡排序实现（技术栈：纯函数式）
function bubbleSort(arr) {
  let swapped;
  // 每次冒出一个最大值（像水泡上升）
  do {
    swapped = false;
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
  } while (swapped);
  return arr;
}

// 使用示例
console.log(bubbleSort([3, 6, 2, 1, 5])); // [1, 2, 3, 5, 6]

3.2 快速排序的分治之道

// 快速排序实现（技术栈：递归算法）
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const right = [];
  
  // 分割操作（像整理书架）
  for (let i = 0; i < arr.length; i++) {
    if (i === Math.floor(arr.length / 2)) continue;
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }
  
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 百万数据测试
const bigData = Array.from({length: 1000000}, () => Math.random());
console.time("快速排序");
quickSort(bigData); // 耗时约120ms（测试环境：Node.js v16）
console.timeEnd("快速排序");

技术对比：V8引擎的Array.sort()方法在数组长度小于10时使用插入排序，否则使用快速排序的变体。当处理对象数组时，需要特别注意比较函数的实现。

4. 综合应用场景与技术选型

银行叫号系统完美结合队列算法：

class BankingSystem {
  constructor() {
    this.normalQueue = new Queue();
    this.vipQueue = new Queue();
  }

  // 用户取号
  getNumber(isVIP) {
    const number = Date.now(); // 时间戳作为唯一编号
    isVIP ? this.vipQueue.enqueue(number) : this.normalQueue.enqueue(number);
    return number;
  }

  // 呼叫下一个客户
  callNext() {
    // VIP优先策略（如果存在VIP客户）
    return this.vipQueue.size() > 0 
      ? this.vipQueue.dequeue()
      : this.normalQueue.dequeue();
  }
}

类似系统在Node.js的事件循环机制中也得到应用，其中定时器队列和I/O队列的优先级处理策略值得深入研究。

5. 技术优缺点全景分析

链表

  • 👍 动态内存分配、插入删除高效
  • 👎 无法随机访问、额外指针内存开销

栈

  • 👍 后进先出特性、函数调用栈实现
  • 👎 容量固定可能导致栈溢出

归并排序

  • 👍 稳定O(n log n)时间复杂度
  • 👎 需要额外O(n)内存空间

实际开发中，数组的sort方法和链表的WeakMap实现存在内存管理的差异，需要根据场景审慎选择。

6. 重点注意事项备忘录

  1. 循环链表的尾节点next必须指向head
  2. 栈的实现要考虑最大容量限制
  3. 快速排序的基准值选择关乎性能
  4. TypeScript实现时注意类型泛化
  5. 队列的假溢出问题需通过环形结构避免
  6. 浏览器中排序大量数据要考虑主线程阻塞

7. 总结与未来展望

这些基础数据结构与算法如同编程世界的乐高积木，React Fiber架构采用链表实现任务调度，Chrome浏览器的垃圾回收算法融合多种数据结构优化。随着WebAssembly的发展，未来JavaScript的性能瓶颈问题将得到进一步改善，但数据结构的核心思想永不过时。