JavaScript数据结构与算法实现

JavaScript可通过数组、对象、类及函数特性高效实现多种数据结构与算法，涵盖线性结构（数组、链表、栈、队列）、树形结构（二叉树）和图形结构（图），并支持递归、排序、搜索等经典算法的实现。

• 数组：

  基于索引的快速访问（O(1)），但头部/中间插入/删除效率低（O(n)）。

  常用方法：push()/pop()（尾部操作，O(1)），shift()/unshift()（头部操作，O(n)）。

• 链表：

  通过节点指针连接，适合频繁插入/删除（O(1)）。

  简易单向链表实现：class ListNode { constructor(val) { this.val = val; this.next = null; }}class LinkedList { constructor() { this.head = null; } 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; } }}

• 栈（LIFO）：

  数组实现，支持push()、pop()、peek()（查看栈顶）和isEmpty()。

  示例：class Stack { constructor() { this.items = []; } push(item) { this.items.push(item); } pop() { return this.items.pop(); } peek() { return this.items[this.items.length - 1]; } isEmpty() { return this.items.length === 0; }}

• 队列（FIFO）：

  数组实现的shift()为O(n)，建议用对象+指针优化（O(1)）。

  优化实现：class Queue { constructor() { this.items = {}; this.head = 0; this.tail = 0; } enqueue(val) { this.items[this.tail] = val; this.tail++; } dequeue() { if (this.head === this.tail) return undefined; const val = this.items[this.head]; delete this.items[this.head]; this.head++; return val; }}

• 二叉树：

  节点最多两个子节点，支持递归遍历（前序、中序、后序）和层序遍历（广度优先）。

  节点定义：class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}

• 图：

  常用邻接表存储（对象实现），支持无向图和有向图。

  无向图实现示例：class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []; } addEdge(v1, v2) { this.adjacencyList[v1].push(v2); this.adjacencyList[v2].push(v1); }}

• 递归与回溯：

  斐波那契数列（记忆化优化）：function fib(n, memo = {}) { if (n in memo) return memo[n]; if (n <= 2) return 1; memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n];}

  全排列问题：通过递归交换元素生成所有排列。

• 排序算法：

  快速排序：选择基准值分区递归。function quickSort(arr) { if (arr.length <= 1) return arr; const pivot = arr[0]; const left = arr.filter(x => x < pivot); const right = arr.filter(x => x > pivot); return [...quickSort(left), pivot, ...quickSort(right)];}

  归并排序：分治合并，稳定排序。

• 搜索算法：

  二分查找：有序数组中查找（O(log n)）。function binarySearch(arr, target) { let left = 0, right = arr.length - 1; while (left <= right) { const mid = Math.floor((left + right) / 2); if (arr[mid] === target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1;}

  深度优先搜索（DFS）：递归遍历树/图。

  广度优先搜索（BFS）：队列实现，适合最短路径问题。

• 性能选择：数组适合随机访问，链表适合频繁增删；栈/队列需根据操作类型选择实现方式。
• 树与图遍历：递归适用于树，队列辅助的BFS适用于图的最短路径。
• 算法优化：记忆化、分治策略可显著提升效率。

掌握这些结构与算法的实现逻辑，能高效解决前端面试题及实际开发中的复杂问题。