链表、树、图是JavaScript中核心数据结构。链表通过节点连接实现动态存储，支持尾插、指定位置插入与删除；树以二叉搜索树为例，实现节点插入、中序遍历与查找；图采用邻接表表示，支持添加顶点与边，并实现深度优先（DFS）和广度优先（BFS）遍历。三者分别适用于线性、层级与网状关系的数据处理，是算法设计与开发中的基础工具。
链表、树、图是JavaScript中常见的数据结构，它们在算法实现和实际开发中应用广泛。下面分别介绍这三种数据结构的基本实现方式及常用操作。
链表（Linked List）
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
节点定义：
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
单向链表实现：
立即学习“Java免费学习笔记（深入）”；
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
<pre class='brush:php;toolbar:false;'>// 在尾部添加节点
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++;
}
// 插入节点到指定位置
insertAt(index, val) {
if (index < 0 || index > this.size) return false;
const node = new ListNode(val);
if (index === 0) {
node.next = this.head;
this.head = node;
} else {
let current = this.head;
for (let i = 0; i < index - 1; i++) {
current = current.next;
}
node.next = current.next;
current.next = node;
}
this.size++;
return true;
}
// 删除指定值的节点
remove(val) {
if (!this.head) return null;
if (this.head.val === val) {
this.head = this.head.next;
this.size--;
return val;
}
let current = this.head;
while (current.next && current.next.val !== val) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
this.size--;
return val;
}
return null;
}}
树（Tree）— 二叉树与二叉搜索树
树是非线性结构，常用于表示层级关系。二叉树每个节点最多有两个子节点。
二叉树节点定义：
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
二叉搜索树（BST）实现：
class BST {
constructor() {
this.root = null;
}
<pre class='brush:php;toolbar:false;'>// 插入节点
insert(val) {
const node = new TreeNode(val);
if (!this.root) {
this.root = node;
} else {
this._insertNode(this.root, node);
}
}
_insertNode(root, node) {
if (node.val < root.val) {
if (!root.left) {
root.left = node;
} else {
this._insertNode(root.left, node);
}
} else {
if (!root.right) {
root.right = node;
} else {
this._insertNode(root.right, node);
}
}
}
// 中序遍历（升序输出）
inorder(node = this.root, result = []) {
if (node) {
this.inorder(node.left, result);
result.push(node.val);
this.inorder(node.right, result);
}
return result;
}
// 查找节点
search(val, node = this.root) {
if (!node) return null;
if (val === node.val) return node;
if (val < node.val) {
return this.search(val, node.left);
} else {
return this.search(val, node.right);
}
}}
图（Graph）
图由节点（顶点）和边组成，可用于表示复杂关系网络。
图的邻接表实现：
class Graph {
constructor() {
this.adjacencyList = new Map();
}
<pre class='brush:php;toolbar:false;'>// 添加顶点
addVertex(v) {
if (!this.adjacencyList.has(v)) {
this.adjacencyList.set(v, []);
}
}
// 添加边（无向图）
addEdge(v, w) {
this.addVertex(v);
this.addVertex(w);
this.adjacencyList.get(v).push(w);
this.adjacencyList.get(w).push(v);
}
// 深度优先遍历（DFS）
dfs(start) {
const visited = new Set();
const result = [];
const traverse = (vertex) => {
if (!vertex) return;
result.push(vertex);
visited.add(vertex);
this.adjacencyList.get(vertex).forEach(neighbor => {
if (!visited.has(neighbor)) {
traverse(neighbor);
}
});
};
traverse(start);
return result;
}
// 广度优先遍历（BFS）
bfs(start) {
const queue = [start];
const visited = new Set([start]);
const result = [];
while (queue.length) {
const vertex = queue.shift();
result.push(vertex);
this.adjacencyList.get(vertex).forEach(neighbor => {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
});
}
return result;
}}
这些基础实现涵盖了链表、树、图的核心操作。理解其原理有助于解决如路径查找、排序、递归等常见算法问题。基本上就这些，不复杂但容易忽略细节。
