JavaScript数据结构与算法实现_技术教程

JavaScript可通过数组、对象和类实现核心数据结构：数组适合索引访问，链表利于频繁增删；栈用数组实现LIFO，队列用对象优化FIFO；二叉树支持递归遍历，图用邻接表存储；并可基于这些结构实现递归、排序、搜索等算法。

JavaScript 是一门灵活且强大的编程语言，非常适合用来实现各种数据结构与算法。通过合理使用 JavaScript 的对象、数组和函数特性，我们可以高效地构建常见数据结构，并在此基础上实现经典算法。以下是几种核心数据结构及其在 JavaScript 中的实现方式。

数组与链表

数组是 JavaScript 中最基础的数据结构之一，基于索引访问非常快，但在插入或删除时效率较低，尤其是在头部或中间位置。

常见操作：

push() / pop()：尾部增删，时间复杂度 O(1)
shift() / unshift()：头部增删，时间复杂度 O(n)

链表通过节点连接实现，每个节点包含值和指向下一个节点的指针。适合频繁插入删除的场景。

简易单向链表实现：

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）原则，可以用数组快速实现。

实现示例：

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)，建议用对象加指针优化。

优化队列实现：

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;
  }
}

常见遍历方式包括递归实现的前序、中序、后序遍历，以及用队列实现的层序遍历（广度优先）。

图可以用邻接表或邻接矩阵表示。JavaScript 中常用对象存储邻接表。

无向图实现示例：

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);
}
}