链表和二叉搜索树可用javascript通过对象引用实现。1. 单向链表支持尾插、指定位置插入和删除节点，操作高效；2. 二叉搜索树实现插入、查找、中序遍历及最值获取，平均时间复杂度o(log n)。两者均适用于动态数据管理，是前端算法基础。
链表和二叉树是前端开发中常被忽视但非常重要的基础数据结构。虽然JavaScript不像C或Java那样直接支持指针和类，但我们可以通过对象引用来模拟这些结构。下面介绍如何用JS实现单向链表和二叉搜索树（BST），并附上常用操作。
单向链表的实现
链表由一系列节点组成，每个节点包含数据和指向下一个节点的引用。相比数组，链表在插入和删除操作上更高效。
定义节点和链表结构：
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
<p>class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}</p><p>// 在尾部添加节点
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++;
}</p><p>// 在指定位置插入
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;
}</p><p>// 删除指定值的第一个节点
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;
}</p><p>// 打印链表
print() {
const result = [];
let current = this.head;
while (current) {
result.push(current.val);
current = current.next;
}
console.log(result.join(' -> '));
}
}</p>使用示例：
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
</font><H3>二叉搜索树（BST）的实现</H3><p>二叉树每个节点最多有两个子节点：左子树和右子树。二叉搜索树在此基础上满足：左子节点值小于父节点，右子节点值大于父节点。</p><div class="aritcle_card flexRow">
<div class="artcardd flexRow">
<a class="aritcle_card_img" href="/ai/1338" title="紫东太初"><img
src="https://img.php.cn/upload/ai_manual/000/000/000/175680204118203.png" alt="紫东太初" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a href="/ai/1338" title="紫东太初">紫东太初</a>
<p>中科院和武汉AI研究院推出的新一代大模型</p>
</div>
<a href="/ai/1338" title="紫东太初" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span> </a>
</div>
</div><p><strong>定义节点和树结构：</strong></p><font color="#0000FF"><pre class="brush:php;toolbar:false;">
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
<p>class BinarySearchTree {
constructor() {
this.root = null;
}</p><p>// 插入节点
insert(val) {
const node = new TreeNode(val);
if (!this.root) {
this.root = node;
} else {
this._insertNode(this.root, node);
}
}</p><p>_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);
}
}
}</p><p>// 查找节点
search(val) {
return this._searchNode(this.root, val);
}</p><p>_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);
}</p><p>// 中序遍历（升序输出）
inOrder(callback) {
this._inOrderNode(this.root, callback);
}</p><p>_inOrderNode(node, callback) {
if (node) {
this._inOrderNode(node.left, callback);
callback(node.val);
this._inOrderNode(node.right, callback);
}
}</p><p>// 最小值
min() {
let node = this.root;
while (node && node.left) {
node = node.left;
}
return node ? node.val : null;
}</p><p>// 最大值
max() {
let node = this.root;
while (node && node.right) {
node = node.right;
}
return node ? node.val : null;
}
}</p>使用示例：
const bst = new BinarySearchTree(); bst.insert(10); bst.insert(5); bst.insert(15); bst.insert(3); bst.insert(7); <p>console.log(bst.search(7)); // true console.log(bst.search(12)); // false</p><p>bst.inOrder((val) => console.log(val)); // 输出: 3, 5, 7, 10, 15 console.log(bst.min()); // 3 console.log(bst.max()); // 15</p>
链表适合频繁增删的场景，而二叉搜索树在查找、插入、删除上平均时间复杂度为O(log n)，特别适合动态数据集合管理。理解这些结构有助于写出更高效的算法，比如LeetCode中的很多题目都依赖这些基础。
基本上就这些，不复杂但容易忽略细节。掌握后可以尝试扩展双向链表、平衡二叉树等进阶内容。
