链表、树、图是javascript实现高级算法的基础。链表通过节点和指针实现，支持插入、删除、反转及快慢指针检测环；树以二叉树为主，常用递归遍历（前序、中序、后序、层序），中序遍历可验证bst；图用邻接表或矩阵表示，配合dfs和bfs进行搜索，可扩展至拓扑排序与最短路径。这些结构广泛应用于虚拟dom、依赖分析等前端场景。
链表、树、图是JavaScript中实现高级算法的重要数据结构。它们在处理复杂逻辑、路径查找、层级关系等问题时表现出色。下面分别介绍这三种结构的基本实现方式及常见高级算法的应用。
链表的实现与常用操作
链表由节点组成，每个节点包含数据和指向下一个节点的指针。最常见的为单向链表。
节点定义：```javascript
class ListNode {
constructor(val, next) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
}
```
链表操作示例：
立即学习“Java免费学习笔记（深入）”；
- 插入节点：可在头部、尾部或指定位置插入
- 删除节点：根据值或索引移除节点
- 反转链表：常用于LeetCode第206题
```javascript
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
```
二叉树结构与遍历算法
树是一种非线性结构，二叉树是最基础的形式，每个节点最多有两个子节点。
节点定义：```javascript
class TreeNode {
constructor(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : right);
}
}
```
常见遍历方式：
- 前序遍历（根-左-右）：可用于复制树结构
- 中序遍历（左-根-右）：BST中序结果为有序序列
- 后序遍历（左-右-根）：适合释放内存或计算子树信息
- 层序遍历：使用队列实现广度优先搜索（BFS）
```javascript
function inorderTraversal(root) {
const result = [];
function traverse(node) {
if (!node) return;
traverse(node.left);
result.push(node.val);
traverse(node.right);
}
traverse(root);
return result;
}
```
图的表示与搜索算法
图由顶点和边构成，适合表达网络、依赖关系等场景。
常见表示方法：
- 邻接矩阵：二维数组，适合稠密图
- 邻接表：对象或Map + 数组，适合稀疏图
```javascript
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'D'],
D: ['B', 'C']
};
```
核心搜索算法：
- 深度优先搜索（DFS）：用递归或栈实现
- 广度优先搜索（BFS）：用队列实现，求最短路径
```javascript
function bfs(graph, start) {
const visited = new Set();
const queue = [start];
const result = [];
while (queue.length > 0) {
const node = queue.shift();
if (visited.has(node)) continue;
visited.add(node);
result.push(node);
for (const neighbor of graph[node]) {
queue.push(neighbor);
}
}
return result;
}
```
高级算法应用示例
基于这些数据结构，可实现更复杂的算法。
- 拓扑排序：用于任务调度，基于图的入度进行BFS
- 二叉搜索树验证：利用中序遍历判断是否有序
- 环检测：链表可用快慢指针（Floyd算法），图可用DFS标记状态
- 最短路径：Dijkstra算法结合优先队列优化
```javascript
// 快慢指针检测链表环
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
```
基本上就这些。掌握链表、树、图的基础实现和遍历方式，是理解更高级算法的前提。在实际编码中，注意边界条件和指针操作，避免引用错误。这些结构在前端开发中的应用场景也越来越多，比如虚拟DOM树、状态依赖图、路由关系等。不复杂但容易忽略细节。
