数据结构 JavaScript 实现 🔥 面试重点

一、数据结构总览

二、线性表

2.1 数组（Array）

JavaScript 数组是内置的动态数组，支持随机访问：

// 数组基本操作
const arr = [1, 2, 3, 4, 5];

// 访问 O(1)
arr[0];        // 1

// 搜索 O(n)
arr.indexOf(3); // 2

// 插入 O(n)
arr.push(6);    // 尾部插入
arr.unshift(0); // 头部插入
arr.splice(2, 0, 99); // 中间插入

// 删除 O(n)
arr.pop();      // 尾部删除
arr.shift();    // 头部删除
arr.splice(2, 1); // 删除指定位置

2.2 链表（Linked List）

// 单链表节点
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// 单链表实现
class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  
  // 头部插入 O(1)
  prepend(val) {
    this.head = new ListNode(val, this.head);
    this.size++;
  }
  
  // 尾部插入 O(n)
  append(val) {
    const node = new ListNode(val);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }
  
  // 查找 O(n)
  find(val) {
    let current = this.head;
    while (current) {
      if (current.val === val) return current;
      current = current.next;
    }
    return null;
  }
  
  // 删除 O(n)
  remove(val) {
    if (!this.head) return;
    if (this.head.val === val) {
      this.head = this.head.next;
      this.size--;
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.val === val) {
        current.next = current.next.next;
        this.size--;
        return;
      }
      current = current.next;
    }
  }
  
  // 反转链表 O(n)
  reverse() {
    let prev = null;
    let current = this.head;
    while (current) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }
    this.head = prev;
  }
  
  // 转为数组
  toArray() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.val);
      current = current.next;
    }
    return result;
  }
}

// 使用示例
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
console.log(list.toArray()); // [0, 1, 2, 3]
list.reverse();
console.log(list.toArray()); // [3, 2, 1, 0]

2.3 栈（Stack）

// 栈：后进先出 LIFO
class Stack {
  constructor() {
    this.items = [];
  }
  
  push(element) { this.items.push(element); }  // O(1)
  pop() { return this.items.pop(); }          // O(1)
  peek() { return this.items[this.items.length - 1]; } // O(1)
  isEmpty() { return this.items.length === 0; }
  size() { return this.items.length; }
}

// 使用链表实现栈（避免数组扩容）
class LinkedStack {
  constructor() {
    this.top = null;
    this.size = 0;
  }
  
  push(val) {
    this.top = { val, next: this.top };
    this.size++;
  }
  
  pop() {
    if (!this.top) return undefined;
    const val = this.top.val;
    this.top = this.top.next;
    this.size--;
    return val;
  }
  
  peek() { return this.top?.val; }
  isEmpty() { return this.size === 0; }
}

// 经典应用：有效的括号
function isValid(s) {
  const stack = [];
  const map = { ')': '(', ']': '[', '}': '{' };
  
  for (const char of s) {
    if (!map[char]) {
      stack.push(char);
    } else {
      if (stack.pop() !== map[char]) return false;
    }
  }
  return stack.length === 0;
}

2.4 队列（Queue）

// 队列：先进先出 FIFO
class Queue {
  constructor() {
    this.items = {};
    this.front = 0;
    this.rear = 0;
  }
  
  enqueue(element) {
    this.items[this.rear++] = element; // O(1)
  }
  
  dequeue() {
    if (this.isEmpty()) return undefined;
    const item = this.items[this.front];
    delete this.items[this.front++];
    return item; // O(1)
  }
  
  peek() { return this.items[this.front]; }
  isEmpty() { return this.rear - this.front === 0; }
  size() { return this.rear - this.front; }
}

// 循环队列
class CircularQueue {
  constructor(capacity) {
    this.capacity = capacity;
    this.items = new Array(capacity);
    this.head = 0;
    this.tail = 0;
    this.size = 0;
  }
  
  enqueue(val) {
    if (this.isFull()) return false;
    this.items[this.tail] = val;
    this.tail = (this.tail + 1) % this.capacity;
    this.size++;
    return true;
  }
  
  dequeue() {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.capacity;
    this.size--;
    return true;
  }
  
  isFull() { return this.size === this.capacity; }
  isEmpty() { return this.size === 0; }
}

// 双端队列 Deque
class Deque {
  constructor() {
    this.items = {};
    this.front = 0;
    this.rear = 0;
  }
  
  addFront(val) { this.items[--this.front] = val; }
  addRear(val) { this.items[this.rear++] = val; }
  removeFront() { /* ... */ }
  removeRear() { /* ... */ }
}

三、树形结构

3.1 二叉树（Binary Tree）

// 二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// 二叉树遍历
class BinaryTree {
  constructor() { this.root = null; }
  
  // 前序遍历：根 → 左 → 右
  preorder(node = this.root, result = []) {
    if (node) {
      result.push(node.val);
      this.preorder(node.left, result);
      this.preorder(node.right, result);
    }
    return result;
  }
  
  // 中序遍历：左 → 根 → 右
  inorder(node = this.root, result = []) {
    if (node) {
      this.inorder(node.left, result);
      result.push(node.val);
      this.inorder(node.right, result);
    }
    return result;
  }
  
  // 后序遍历：左 → 右 → 根
  postorder(node = this.root, result = []) {
    if (node) {
      this.postorder(node.left, result);
      this.postorder(node.right, result);
      result.push(node.val);
    }
    return result;
  }
  
  // 层序遍历（BFS）
  levelOrder() {
    if (!this.root) return [];
    const result = [];
    const queue = [this.root];
    
    while (queue.length) {
      const level = [];
      const size = queue.length;
      for (let i = 0; i < size; i++) {
        const node = queue.shift();
        level.push(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
      }
      result.push(level);
    }
    return result;
  }
  
  // 最大深度
  maxDepth(node = this.root) {
    if (!node) return 0;
    return 1 + Math.max(
      this.maxDepth(node.left),
      this.maxDepth(node.right)
    );
  }
}

3.1.1 遍历的非递归实现（栈实现）

// 前序遍历 - 非递归（栈）
preorderIterative() {
  if (!this.root) return [];
  const result = [];
  const stack = [this.root];
  
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);        // 访问根
    if (node.right) stack.push(node.right); // 右子树先入栈
    if (node.left) stack.push(node.left);   // 左子树后入栈（先出）
  }
  return result;
}

// 中序遍历 - 非递归（栈）
inorderIterative() {
  const result = [];
  const stack = [];
  let node = this.root;
  
  while (node || stack.length) {
    while (node) {
      stack.push(node);      // 一路向左，全部入栈
      node = node.left;
    }
    node = stack.pop();
    result.push(node.val);   // 访问
    node = node.right;       // 转向右子树
  }
  return result;
}

// 后序遍历 - 非递归（双栈法）
postorderIterative() {
  if (!this.root) return [];
  const stack1 = [this.root];
  const stack2 = [];
  
  while (stack1.length) {
    const node = stack1.pop();
    stack2.push(node.val);
    if (node.left) stack1.push(node.left);
    if (node.right) stack1.push(node.right);
  }
  return stack2.reverse(); // 逆序输出
}

3.1.2 根据遍历序列重建二叉树

// 前序 + 中序 → 重建二叉树
function buildTree(preorder, inorder) {
  if (!preorder.length) return null;
  
  const rootVal = preorder[0];
  const root = new TreeNode(rootVal);
  const rootIndex = inorder.indexOf(rootVal);
  
  root.left = buildTree(
    preorder.slice(1, rootIndex + 1),
    inorder.slice(0, rootIndex)
  );
  root.right = buildTree(
    preorder.slice(rootIndex + 1),
    inorder.slice(rootIndex + 1)
  );
  return root;
}

// 中序 + 后序 → 重建二叉树
function buildTreeFromInPost(inorder, postorder) {
  if (!postorder.length) return null;
  
  const rootVal = postorder[postorder.length - 1];
  const root = new TreeNode(rootVal);
  const rootIndex = inorder.indexOf(rootVal);
  
  root.left = buildTreeFromInPost(
    inorder.slice(0, rootIndex),
    postorder.slice(0, rootIndex)
  );
  root.right = buildTreeFromInPost(
    inorder.slice(rootIndex + 1),
    postorder.slice(rootIndex, postorder.length - 1)
  );
  return root;
}

// 示例
// 前序: [3,9,20,15,7]
// 中序: [9,3,15,20,7]
// 后序: [9,15,7,20,3]
const tree = buildTree([3,9,20,15,7], [9,3,15,20,7]);

3.1.3 遍历的应用场景

3.2 二叉搜索树（BST）

class BST {
  constructor() { this.root = null; }
  
  // 插入 O(log n) ~ O(n)
  insert(val) {
    this.root = this._insert(this.root, val);
  }
  
  _insert(node, val) {
    if (!node) return new TreeNode(val);
    if (val < node.val) {
      node.left = this._insert(node.left, val);
    } else if (val > node.val) {
      node.right = this._insert(node.right, val);
    }
    return node;
  }
  
  // 查找 O(log n)
  search(val) {
    let node = this.root;
    while (node) {
      if (val === node.val) return node;
      node = val < node.val ? node.left : node.right;
    }
    return null;
  }
  
  // 删除 O(log n)
  delete(val) {
    this.root = this._delete(this.root, val);
  }
  
  _delete(node, val) {
    if (!node) return null;
    if (val < node.val) {
      node.left = this._delete(node.left, val);
    } else if (val > node.val) {
      node.right = this._delete(node.right, val);
    } else {
      // 找到要删除的节点
      if (!node.left) return node.right;
      if (!node.right) return node.left;
      // 有两个子节点：找右子树最小值
      const minNode = this._findMin(node.right);
      node.val = minNode.val;
      node.right = this._delete(node.right, minNode.val);
    }
    return node;
  }
  
  _findMin(node) {
    while (node.left) node = node.left;
    return node;
  }
  
  // 验证 BST
  isValidBST(node = this.root, min = -Infinity, max = Infinity) {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return this.isValidBST(node.left, min, node.val) &&
           this.isValidBST(node.right, node.val, max);
  }
}

3.3 AVL 树（自平衡二叉搜索树）

class AVLNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

class AVLTree {
  constructor() { this.root = null; }
  
  getHeight(node) { return node ? node.height : 0; }
  
  getBalance(node) {
    return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
  }
  
  updateHeight(node) {
    node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
  }
  
  // 右旋
  rotateRight(y) {
    const x = y.left;
    const T2 = x.right;
    x.right = y;
    y.left = T2;
    this.updateHeight(y);
    this.updateHeight(x);
    return x;
  }
  
  // 左旋
  rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;
    y.left = x;
    x.right = T2;
    this.updateHeight(x);
    this.updateHeight(y);
    return y;
  }
  
  insert(val) { this.root = this._insert(this.root, val); }
  
  _insert(node, val) {
    if (!node) return new AVLNode(val);
    if (val < node.val) node.left = this._insert(node.left, val);
    else if (val > node.val) node.right = this._insert(node.right, val);
    else return node; // 重复值不插入
    
    this.updateHeight(node);
    const balance = this.getBalance(node);
    
    // LL
    if (balance > 1 && val < node.left.val) return this.rotateRight(node);
    // RR
    if (balance < -1 && val > node.right.val) return this.rotateLeft(node);
    // LR
    if (balance > 1 && val > node.left.val) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }
    // RL
    if (balance < -1 && val < node.right.val) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }
    return node;
  }
}

四、哈希表

class HashTable {
  constructor(size = 53) { // 质数减少冲突
    this.buckets = new Array(size);
    this.size = size;
  }
  
  // 哈希函数
  _hash(key) {
    let hash = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      hash = (hash * PRIME + key.charCodeAt(i)) % this.size;
    }
    return hash;
  }
  
  // 设置 O(1)
  set(key, value) {
    const index = this._hash(key);
    if (!this.buckets[index]) this.buckets[index] = [];
    const bucket = this.buckets[index];
    const existing = bucket.find(item => item[0] === key);
    if (existing) {
      existing[1] = value; // 更新
    } else {
      bucket.push([key, value]); // 新增
    }
  }
  
  // 获取 O(1)
  get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    if (!bucket) return undefined;
    const item = bucket.find(item => item[0] === key);
    return item ? item[1] : undefined;
  }
  
  // 删除 O(1)
  delete(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    if (!bucket) return false;
    const i = bucket.findIndex(item => item[0] === key);
    if (i >= 0) { bucket.splice(i, 1); return true; }
    return false;
  }
  
  // 获取所有键
  keys() {
    const keys = [];
    for (const bucket of this.buckets) {
      if (bucket) bucket.forEach(item => keys.push(item[0]));
    }
    return keys;
  }
  
  values() {
    const values = [];
    for (const bucket of this.buckets) {
      if (bucket) bucket.forEach(item => values.push(item[1]));
    }
    return [...new Set(values)]; // 去重
  }
}

五、堆（Heap）

// 最小堆
class MinHeap {
  constructor() { this.heap = []; }
  
  size() { return this.heap.length; }
  peek() { return this.heap[0]; }
  
  push(val) {
    this.heap.push(val);
    this._bubbleUp(this.heap.length - 1);
  }
  
  pop() {
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._sinkDown(0);
    }
    return min;
  }
  
  _bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }
  
  _sinkDown(i) {
    const length = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < length && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < length && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

// 应用：合并 K 个有序链表
function mergeKLists(lists) {
  const heap = new MinHeap();
  for (const node of lists) {
    if (node) heap.push({ val: node.val, node });
  }
  const dummy = { next: null };
  let current = dummy;
  while (heap.size()) {
    const { val, node } = heap.pop();
    current.next = { val, next: null };
    current = current.next;
    if (node.next) heap.push({ val: node.next.val, node: node.next });
  }
  return dummy.next;
}

六、图结构

// 邻接表实现图
class Graph {
  constructor(directed = false) {
    this.adjacencyList = {};
    this.directed = directed;
  }
  
  addVertex(v) {
    if (!this.adjacencyList[v]) this.adjacencyList[v] = [];
  }
  
  addEdge(v1, v2, weight = 1) {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList[v1].push({ node: v2, weight });
    if (!this.directed) {
      this.adjacencyList[v2].push({ node: v1, weight });
    }
  }
  
  // BFS 广度优先搜索
  bfs(start, end) {
    const queue = [[start, [start]]];
    const visited = new Set([start]);
    while (queue.length) {
      const [node, path] = queue.shift();
      if (node === end) return path;
      for (const { node: neighbor } of this.adjacencyList[node] || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push([neighbor, [...path, neighbor]]);
        }
      }
    }
    return null;
  }
  
  // DFS 深度优先搜索
  dfs(start, end, visited = new Set()) {
    if (start === end) return [end];
    visited.add(start);
    for (const { node: neighbor } of this.adjacencyList[start] || []) {
      if (!visited.has(neighbor)) {
        const path = this.dfs(neighbor, end, visited);
        if (path) return [start, ...path];
      }
    }
    return null;
  }
  
  // Dijkstra 最短路径
  dijkstra(start, end) {
    const distances = {};
    const previous = {};
    const pq = new MinHeap();
    
    for (const vertex of Object.keys(this.adjacencyList)) {
      distances[vertex] = vertex === start ? 0 : Infinity;
      pq.push({ vertex, priority: distances[vertex] });
    }
    
    while (pq.size()) {
      const { vertex } = pq.pop();
      if (vertex === end) break;
      for (const { node, weight } of this.adjacencyList[vertex]) {
        const alt = distances[vertex] + weight;
        if (alt < distances[node]) {
          distances[node] = alt;
          previous[node] = vertex;
          pq.push({ vertex: node, priority: alt });
        }
      }
    }
    return distances[end];
  }
}

七、排序算法

// 快速排序
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;
  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

// 归并排序
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

八、LeetCode 实战

function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) return [map.get(complement), i];
    map.set(nums[i], i);
  }
}

function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }
  
  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val); // 移到末尾
    return val;
  }
  
  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey); // 删除最久未使用
    }
  }
}