跳到主要内容

数据结构基础

什么是数据结构？​

数据结构 = 数据的组织方式

就像整理房间一样：

  • 衣服可以叠起来放（栈）
  • 排队买奶茶要先来后到（队列）
  • 字典按拼音查找（哈希表）
  • 家族关系是树状的（树）

选择合适的数据结构，能让程序运行得更快、代码写得更简单。

常见数据结构一览​

一、数组（Array）​

概念​

数组就像一排储物柜，每个柜子有编号（下标），可以直接通过编号找到对应的柜子。

下标:    0     1     2     3     4
       +-----+-----+-----+-----+-----+
数组:  |  5  |  2  |  8  |  1  |  9  |
       +-----+-----+-----+-----+-----+

特点​

操作时间复杂度说明
读取O(1)O(1)直接通过下标访问，超快
插入O(n)O(n)需要移动后面所有元素
删除O(n)O(n)需要移动后面所有元素
查找O(n)O(n)最坏情况要遍历整个数组

TypeScript 示例​

// 创建数组
const arr: number[] = [5, 2, 8, 1, 9];

// 读取：O(1)
console.log(arr[2]); // 8

// 修改：O(1)
arr[2] = 100;

// 末尾添加：O(1)
arr.push(6);

// 中间插入：O(n) - 需要移动元素
arr.splice(2, 0, 99); // 在下标2处插入99
什么时候用数组？
  • 需要频繁读取数据（通过下标）
  • 数据量固定或只在末尾增删
  • 需要顺序遍历所有数据

二、链表（LinkedList）​

概念​

链表就像一条珠子项链，每颗珠子（节点）包含两部分：

  1. 数据本身
  2. 指向下一颗珠子的线（指针）
+-------+    +-------+    +-------+    +-------+
|   5   | -> |   2   | -> |   8   | -> |   1   | -> null
+-------+    +-------+    +-------+    +-------+

特点​

操作时间复杂度说明
读取O(n)O(n)必须从头开始找
插入O(1)O(1)只需修改指针（已知位置时）
删除O(1)O(1)只需修改指针（已知位置时）
查找O(n)O(n)必须从头开始找

TypeScript 示例​

// 链表节点
class ListNode {
  val: number;
  next: ListNode | null;

  constructor(val: number) {
    this.val = val;
    this.next = null;
  }
}

// 创建链表: 5 -> 2 -> 8
const head = new ListNode(5);
head.next = new ListNode(2);
head.next.next = new ListNode(8);

// 遍历链表
let current: ListNode | null = head;
while (current !== null) {
  console.log(current.val);
  current = current.next;
}

// 在头部插入新节点：O(1)
const newHead = new ListNode(99);
newHead.next = head;
什么时候用链表？
  • 需要频繁插入/删除数据
  • 不需要通过下标访问
  • 数据量不确定，需要动态增长

三、栈（Stack）​

概念​

栈就像叠盘子：

  • 只能从顶部放盘子（入栈 push）
  • 只能从顶部拿盘子（出栈 pop）
  • 后放的先拿（后进先出 LIFO）
      +-----+
      |  3  | <- 栈顶（最后放入，最先取出）
      +-----+
      |  2  |
      +-----+
      |  1  | <- 栈底（最先放入，最后取出）
      +-----+

TypeScript 示例​

// 用数组模拟栈
class Stack<T> {
  private items: T[] = [];

  // 入栈
  push(item: T): void {
    this.items.push(item);
  }

  // 出栈
  pop(): T | undefined {
    return this.items.pop();
  }

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

  // 是否为空
  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

// 使用示例
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3（后进先出）
console.log(stack.pop()); // 2
栈的应用场景
  • 浏览器后退：访问的页面依次入栈，后退时出栈
  • 撤销操作：每次操作入栈，撤销时出栈
  • 括号匹配：左括号入栈，遇到右括号时出栈匹配
  • 函数调用栈：函数调用时入栈，返回时出栈

四、队列（Queue）​

概念​

队列就像排队买奶茶：

  • 从队尾排队（入队 enqueue）
  • 从队头离开（出队 dequeue）
  • 先来的先走（先进先出 FIFO）
出队 <-- [  1  |  2  |  3  ] <-- 入队
         队头            队尾

TypeScript 示例​

// 用数组模拟队列
class Queue<T> {
  private items: T[] = [];

  // 入队
  enqueue(item: T): void {
    this.items.push(item);
  }

  // 出队
  dequeue(): T | undefined {
    return this.items.shift();
  }

  // 查看队头
  front(): T | undefined {
    return this.items[0];
  }

  // 是否为空
  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

// 使用示例
const queue = new Queue<string>();
queue.enqueue('小明');
queue.enqueue('小红');
queue.enqueue('小刚');
console.log(queue.dequeue()); // 小明（先进先出）
console.log(queue.dequeue()); // 小红
队列的应用场景
  • 消息队列：处理异步任务
  • 打印队列：按顺序打印文档
  • BFS 广度优先搜索：层序遍历树/图

五、哈希表（HashMap）​

概念​

哈希表就像字典：通过"关键词"直接找到"解释"，不需要一页一页翻。

键(Key)     哈希函数      值(Value)
  "apple"  ------>  [0] -> "苹果"
  "banana" ------>  [1] -> "香蕉"
  "cat"    ------>  [2] -> "猫"

特点​

操作平均时间复杂度说明
查找O(1)O(1)通过键直接定位
插入O(1)O(1)计算哈希值后直接存储
删除O(1)O(1)通过键直接定位后删除

TypeScript 示例​

// 使用 Map
const hashMap = new Map<string, number>();

// 插入
hashMap.set('apple', 5);
hashMap.set('banana', 3);
hashMap.set('orange', 8);

// 查找：O(1)
console.log(hashMap.get('apple')); // 5

// 检查是否存在
console.log(hashMap.has('grape')); // false

// 删除
hashMap.delete('banana');

// 遍历
hashMap.forEach((value, key) => {
  console.log(`${key}: ${value}`);
});
什么时候用哈希表？
  • 需要快速查找某个元素是否存在
  • 需要统计出现次数
  • 需要建立映射关系（如两数之和）

六、树（Tree）​

概念​

树就像家族族谱：有一个祖先（根节点），往下分支出子孙（子节点）。

        1        <- 根节点
       / \
      2   3      <- 子节点
     / \   \
    4   5   6    <- 叶子节点（没有子节点）

常见术语​

术语含义
根节点最顶部的节点，没有父节点
叶子节点最底部的节点，没有子节点
深度从根到该节点的边数
高度从该节点到最远叶子的边数

二叉树（最常见）​

每个节点最多有两个子节点（左子节点、右子节点）。

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 创建二叉树
//       1
//      / \
//     2   3
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
树的应用场景
  • DOM 树：网页的结构
  • 文件系统：文件夹的层级结构
  • 二叉搜索树：快速查找
  • 堆：优先队列、Top K 问题

七、图（Graph）​

概念​

图由顶点（节点）和边组成，用来表示对象之间的关系。与树不同，图可以有环，且任意两个节点间可以有边。

无向图:          有向图:
  A --- B        A --> B
  |   / |        |     ↓
  |  /  |        ↓     D
  C --- D        C -->

图的分类​

类型说明示例
无向图边没有方向微信好友关系
有向图边有方向微博关注关系
加权图边带有权重地图导航（距离）

图的表示方式​

邻接矩阵​

// 用二维数组表示，matrix[i][j] = 1 表示 i 到 j 有边
const matrix: number[][] = [
  // A  B  C  D
  [0, 1, 1, 0], // A
  [1, 0, 1, 1], // B
  [1, 1, 0, 1], // C
  [0, 1, 1, 0], // D
];

// 优点：查询两点是否相连 O(1)
// 缺点：空间 O(n²)，稀疏图浪费空间

邻接表​

// 用 Map + 数组表示，每个节点存储相邻节点列表
const graph = new Map<string, string[]>();
graph.set('A', ['B', 'C']);
graph.set('B', ['A', 'C', 'D']);
graph.set('C', ['A', 'B', 'D']);
graph.set('D', ['B', 'C']);

// 优点：节省空间，适合稀疏图
// 缺点：查询两点是否相连需要遍历邻接列表

图的遍历​

// BFS 广度优先搜索
function bfs(graph: Map<string, string[]>, start: string): string[] {
  const visited = new Set<string>();
  const queue: string[] = [start];
  const result: string[] = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

// DFS 深度优先搜索
function dfs(graph: Map<string, string[]>, start: string): string[] {
  const visited = new Set<string>();
  const result: string[] = [];

  function traverse(node: string): void {
    visited.add(node);
    result.push(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        traverse(neighbor);
      }
    }
  }

  traverse(start);
  return result;
}
图的应用场景
  • 社交网络：好友关系、关注关系
  • 地图导航：最短路径
  • 依赖管理：npm 包依赖、任务调度（拓扑排序）
  • 网络爬虫：网页之间的链接关系

数据结构选择速查表​

场景推荐数据结构原因
频繁读取，少量增删数组下标访问 O(1)O(1)
频繁增删，不需要下标访问链表插入删除 O(1)O(1)
后进先出（撤销、括号匹配）栈LIFO 特性
先进先出（任务队列、BFS）队列FIFO 特性
快速查找、去重、计数哈希表查找 O(1)O(1)
层级关系、递归结构树天然递归
多对多关系、网络图表达复杂关系

常见面试问题​

Q1: 数组和链表的区别是什么？什么时候用哪个？​

答案：

对比项数组链表
内存连续内存空间不连续，通过指针连接
读取O(1)O(1)，按下标随机访问O(n)O(n)，必须从头遍历
插入/删除O(n)O(n)，需移动元素O(1)O(1)，只修改指针（已知位置时）
缓存友好好（连续内存，CPU 预取）差（内存分散）

选择建议：

  • 频繁随机读取 → 数组
  • 频繁头部/中间插入删除 → 链表
  • 实际开发中，数组的缓存友好性使其在大多数场景下性能更好

Q2: 栈和队列分别在前端有哪些应用？​

答案：

栈的应用：

  • 浏览器前进/后退：用两个栈分别管理历史和前进记录
  • 函数调用栈：JavaScript 执行上下文栈
  • 括号匹配：编辑器语法检查
  • 撤销/重做：编辑器的 undo/redo

队列的应用：

  • 事件循环：宏任务队列、微任务队列
  • 消息队列：异步任务处理
  • BFS：层序遍历 DOM 树
  • 打印队列：按顺序处理任务

Q3: 哈希表的哈希冲突怎么解决？​

答案：

哈希冲突是指不同的 key 经过哈希函数计算后得到相同的位置。常见解决方式：

  1. 链地址法（Chaining）：每个位置存储一个链表，冲突的元素追加到链表中。JavaScript 的 Map 底层就采用类似策略。

  2. 开放寻址法（Open Addressing）：冲突时，按照某种规则寻找下一个空位置。

// 链地址法简单示意
class SimpleHashMap<V> {
  private buckets: [string, V][][] = new Array(16).fill(null).map(() => []);

  private hash(key: string): number {
    let h = 0;
    for (const char of key) {
      h = (h * 31 + char.charCodeAt(0)) % this.buckets.length;
    }
    return h;
  }

  set(key: string, value: V): void {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    const existing = bucket.find(([k]) => k === key);
    if (existing) {
      existing[1] = value;
    } else {
      bucket.push([key, value]);
    }
  }

  get(key: string): V | undefined {
    const index = this.hash(key);
    const pair = this.buckets[index].find(([k]) => k === key);
    return pair?.[1];
  }
}

相关链接​