谈谈常见的数据结构（如数组、链表、栈、队列、哈希表、树、图）及其应用场景

一、数组（Array）

定义：连续存储相同类型数据的线性结构，支持随机访问。
应用场景：列表渲染、数据缓存、算法处理
代码示例：

// 数组基本操作
const arr = [1, 2, 3, 4];
arr.push(5); // O(1) 平均时间复杂度
arr.pop();  // O(1)
arr.shift();// O(n) 不推荐高频使用
arr.unshift(0); // O(n)

// 数组遍历优化
// 推荐写法（减少属性查找）
for (let i = 0, len = arr.length; i < len; i++) {
  console.log(arr[i]);
}

// 二维数组初始化
const matrix = Array.from({ length: 3 }, () => new Array(3).fill(0));

使用建议：

1. 优先使用 push/pop 替代 shift/unshift
2. 大数据量时避免频繁操作数组头部
3. 遍历数组使用 for 循环而非 forEach 可提高性能
4. 多维数组建议使用 Array.from 初始化

注意事项：

• 警惕数组越界访问
• 避免使用稀疏数组（会影响性能）
• 注意数组原型链方法的副作用（如 sort 会改变原数组）

二、链表（Linked List）

定义：由节点组成的链式结构，节点包含值和指向下一个节点的指针
应用场景：内存管理、DOM 节点操作、LRU 缓存
代码示例：

class ListNode {
  constructor(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
  }
}

// 链表反转
function reverseList(head) {
  let prev = null;
  let current = head;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

使用建议：

1. 插入 / 删除操作优先使用链表
2. 实现双向链表时维护好前驱指针
3. 使用虚拟头节点简化边界条件处理

注意事项：

• 避免循环引用导致内存泄漏
• 注意空指针检查
• 遍历链表时设置终止条件
• 内存分配比数组更碎片化

三、栈（Stack）

定义：遵循后进先出（LIFO）原则的线性结构
应用场景：路由管理、撤销重做、函数调用栈
代码示例：

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }
}

// 浏览器路由栈模拟
const routerStack = new Stack();
routerStack.push('/home');
routerStack.push('/about');
routerStack.pop(); // 返回 '/about'，当前栈顶 '/home'

使用建议：

1. 用数组实现简单栈时，直接使用 push/pop
2. 需要高性能时考虑使用 Uint8Array 实现
3. 限制栈的最大深度防止溢出

注意事项：

• 处理栈溢出（Stack Overflow）
• 避免在栈中存储过大对象
• 递归深度受限于栈大小

四、队列（Queue）

定义：遵循先进先出（FIFO）原则的线性结构
应用场景：任务调度、事件队列、消息缓冲
代码示例：

class Queue {
  constructor() {
    this.items = [];
  }

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

  dequeue() {
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }
}

// 任务队列处理
const taskQueue = new Queue();
taskQueue.enqueue(() => console.log('Task 1'));
taskQueue.enqueue(() => console.log('Task 2'));
taskQueue.dequeue()(); // 执行 Task 1

使用建议：

1. 优先使用 enqueue + pop 替代 shift
2. 使用双端队列（Deque）实现更灵活操作
3. 限制队列长度防止内存耗尽

注意事项：

• 避免饥饿问题（高优先级任务阻塞队列）
• 处理并发访问时需加锁
• 内存泄漏风险（未及时释放旧任务）

五、哈希表（Hash Table）

定义：通过哈希函数将键映射到存储位置的结构
应用场景：状态管理、缓存、快速查找
代码示例：

class HashTable {
  constructor(size = 1024) {
    this.table = new Array(size);
    this.size = size;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.size;
  }

  set(key, value) {
    const index = this.hash(key);
    this.table[index] = value;
  }

  get(key) {
    const index = this.hash(key);
    return this.table[index];
  }
}

// 简单状态管理
const state = new HashTable();
state.set('user', { name: 'John', age: 30 });
console.log(state.get('user'));

使用建议：

1. 选择合适的哈希函数（如 BKDRHash）
2. 负载因子控制在 0.75 以下
3. 实现冲突解决（开放寻址法 / 链地址法）

注意事项：

• 哈希冲突的处理
• 键的可哈希性（对象需重写 toString）
• 动态扩容的性能消耗

六、树（Tree）

定义：n 个节点构成的有限集合，具有层次关系
应用场景：DOM 树、路由配置、算法优化
代码示例：

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 二叉树前序遍历
function preorderTraversal(root) {
  const result = [];
  function traverse(node) {
    if (!node) return;
    result.push(node.val);
    traverse(node.left);
    traverse(node.right);
  }
  traverse(root);
  return result;
}

// 构建DOM树
const div = document.createElement('div');
const span = document.createElement('span');
div.appendChild(span);

使用建议：

1. 使用递归实现树遍历需注意栈溢出
2. 优先使用迭代法（如 Morris 遍历）优化空间复杂度
3. 树的深度控制在合理范围

注意事项：

• 树的平衡问题（AVL 树 / RBTree）
• 内存泄漏（未释放子节点引用）
• 遍历顺序的选择（前序 / 中序 / 后序）

七、图（Graph）

定义：由节点和边构成的非线性结构
应用场景：社交网络、路径规划、依赖分析
代码示例：

class Graph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjList.has(vertex)) {
      this.adjList.set(vertex, new Set());
    }
  }

  addEdge(v1, v2) {
    if (this.adjList.has(v1) && this.adjList.has(v2)) {
      this.adjList.get(v1).add(v2);
      this.adjList.get(v2).add(v1);
    }
  }

  bfs(start) {
    const visited = new Set();
    const queue = [start];
    visited.add(start);
    while (queue.length) {
      const node = queue.shift();
      console.log(node);
      this.adjList.get(node).forEach(neighbor => {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      });
    }
  }
}

// 页面依赖关系图
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addEdge('A', 'B');
graph.bfs('A'); // 输出 A -> B

使用建议：

1. 选择邻接表存储稀疏图
2. 使用邻接矩阵存储稠密图
3. 路径查找使用 Dijkstra/A * 算法

注意事项：

• 图的遍历需要标记访问状态
• 处理环的问题（强连通分量）
• 内存消耗较大，需注意优化

总结建议

1. 空间与时间权衡：根据数据量和操作类型选择结构
2. 性能优化：避免在高频操作中使用低效率方法
3. 内存管理：及时释放不再使用的结构引用
4. 算法适配：不同场景选择对应算法（如树用 DFS，图用 BFS）
5. 边界处理：空值检查、越界处理等防御性编程

建议在实际开发中建立数据结构选择决策表，根据具体场景评估时间复杂度、空间复杂度和操作频率，同时结合浏览器 / Node.js 环境特性进行优化。