链表和二叉搜索树可用JavaScript通过对象引用实现。1. 单向链表支持尾插、指定位置插入和删除节点，操作高效；2. 二叉搜索树实现插入、查找、中序遍历及最值获取，平均时间复杂度O(log n)。两者均适用于动态数据管理，是前端算法基础。
链表和二叉树是前端开发中常被忽视但非常重要的基础数据结构。虽然JavaScript不像C或Java那样直接支持指针和类，但我们可以通过对象引用来模拟这些结构。下面介绍如何用JS实现单向链表和二叉搜索树（BST），并附上常用操作。
单向链表的实现
链表由一系列节点组成，每个节点包含数据和指向下一个节点的引用。相比数组，链表在插入和删除操作上更高效。
定义节点和链表结构：
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// 在尾部添加节点
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) {
const removed = this.head;
this.head = this.head.next;
this.size--;
return removed.val;
}
let current = this.head;
while (current.next && current.next.val !== val) {
current = current.next;
}
if (current.next) {
const removed = current.next;
current.next = current.next.next;
this.size--;
return removed.val;
}
return null;
}
// 打印链表
print() {
const result = [];
let current = this.head;
while (current) {
result.push(current.val);
current = current.next;
}
console.log(result.join(' -> '));
}
}
使用示例：
const list = new LinkedList(); list.append(1); list.append(2); list.append(3); list.insertAt(1, 1.5); list.print(); // 输出: 1 -> 1.5 -> 2 -> 3 list.remove(1.5); list.print(); // 输出: 1 -> 2 -> 3
二叉搜索树（BST）的实现
二叉树每个节点最多有两个子节点：左子树和右子树。二叉搜索树在此基础上满足：左子节点值小于父节点，右子节点值大于父节点。
定义节点和树结构：
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
// 插入节点
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(ro
ot.right, node);
}
}
}
// 查找节点
search(val) {
return this._searchNode(this.root, val);
}
_searchNode(root, val) {
if (!root) return false;
if (val === root.val) return true;
return val < root.val
? this._searchNode(root.left, val)
: this._searchNode(root.right, val);
}
// 中序遍历（升序输出）
inOrder(callback) {
this._inOrderNode(this.root, callback);
}
_inOrderNode(node, callback) {
if (node) {
this._inOrderNode(node.left, callback);
callback(node.val);
this._inOrderNode(node.right, callback);
}
}
// 最小值
min() {
let node = this.root;
while (node && node.left) {
node = node.left;
}
return node ? node.val : null;
}
// 最大值
max() {
let node = this.root;
while (node && node.right) {
node = node.right;
}
return node ? node.val : null;
}
}
ot.right, node);
}
}
}使用示例：
const bst = new BinarySearchTree(); bst.insert(10); bst.insert(5); bst.insert(15); bst.insert(3); bst.insert(7);console.log(bst.search(7)); // true console.log(bst.search(12)); // false
bst.inOrder((val) => console.log(val)); // 输出: 3, 5, 7, 10, 15 console.log(bst.min()); // 3 console.log(bst.max()); // 15
链表适合频繁增删的场景，而二叉搜索树在查找、插入、删除上平均时间复杂度为O(log n)，特别适合动态数据集合管理。理解这些结构有助于写出更高效的算法，比如LeetCode中的很多题目都依赖这些基础。
基本上就这些，不复杂但容易忽略细节。掌握后可以尝试扩展双向链表、平衡二叉树等进阶内容。
