单向链表和二叉搜索树可通过对象与引用实现；链表由含值和下一节点指针的节点组成，支持增删查遍操作；树结构中左子小于父、右子大于父，实现插入、查找与遍历。
链表和树是JavaScript中常用的数据结构，尤其适合处理动态数据和层级关系。虽然JavaScript没有内置的链表或树类型，但我们可以用对象和引用轻松实现它们。下面分别介绍单向链表和二叉搜索树的基本实现方式。
单向链表实现
单向链表由节点组成，每个节点包含数据和指向下一个节点的指针。
节点定义： 每个节点是一个对象，有value存储值，next指向下一个节点。
链表操作： 常见操作包括插入、删除、查找和遍历。
立即学习“Java免费学习笔记（深入）”；
示例代码：
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// 在链表末尾添加节点
append(val) {
const newNode = new ListNode(val);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// 查找是否存在某个值
find(val) {
let current = this.head;
while (current) {
if (current.val === val) return true;
current = current.next;
}
return false;
}
// 删除某个值的节点
remove(val) {
if (!this.head) return;
if (this.head.val === val) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next) {
if (current.next.val === val) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
// 遍历并打印所有值
display() {
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.display(); // 输出: 1 -> 2 -> 3 list.remove(2); list.display(); // 输出: 1 -> 3
二叉搜索树实现
二叉搜索树（BST）是一种树形结构，每个节点最多有两个子节点，且左子节点值小于父节点，右子节点值大于父节点。
节点结构： 包含val、left和right。
核心操作： 插入、查找、删除、遍历（中序、前序、后序）。
示例代码：
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
// 插入节点
insert(val) {
const newNode = new TreeNode(val);
if (!this.root) {
this.root = newNode;
return;
}
this._insertNode(this.root, newNode);
}
_insertNode(node, newNode) {
if (newNode.val < node.val) {
if (!node.left) {
node.left = newNode;
} else {
this._insertNode(node.left, newNode);
}
} else {
if (!node.right) {
node.right = newNode;
} else {
this._insertNode(node.right, newNode);
}
}
}
// 查找节点
search(val) {
return this._searchNode(this.root, val);
}
_searchNode(node, val) {
if (!node) return false;
if (val === node.val) return true;
return val < node.val
? this._searchNode(node.left, val)
: this._searchNode(node.right, val);
}
// 中序遍历（升序输出）
inorderTraversal() {
const result = [];
this._inorder(this.root, result);
return result;
}
_inorder(node, result) {
if (node) {
this._inorder(node.left, result);
result.push(node.val);
this._inorder(node.right, result);
}
}
}
使用示例：
const bst = new BinarySearchTree(); bst.insert(5); bst.insert(3); bst.insert(7); bst.insert(2); bst.insert(4); console.log(bst.inorderTraversal()); // [2, 3, 4, 5, 7] console.log(bst.search(3)); // true console.log(bst.search(6)); // false
基本上就这些。链表适合频繁插入删除的场景，树适合快速查找和排序。理解它们的指针操作和递归逻辑，对提升算法能力很有帮助。不复杂但容易忽略细节，比如边界判断和引用更新。
