链表和树可通过对象与引用实现；链表用于高效插入删除，树适用于查找与层级结构，JavaScript中二者均需手动构建节点与操作方法。
链表和树是JavaScript中常见的数据结构，尤其在处理动态数据和层级关系时非常有用。虽然JavaScript没有内置的链表或树类型，但我们可以用对象和引用轻松实现它们。下面分别介绍链表和树形结构的基本实现方式。
链表的实现
链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。最常见的链表是单向链表。
定义节点：
每个节点是一个对象，包含两个属性：data（存储数据）和next（指向下一个节点）。
立即学习“Java免费学习笔记（深入）”；
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}链表类的基本操作：
实现一个链表类，支持插入、删除、查找等操作。
class LinkedList {
constructor() {
this.head = null;
}
// 在链表末尾添加节点
append(data) {
const newNode = new ListNode(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// 在指定位置插入节点
insertAt(index, data) {
if (index === 0) {
const newNode = new ListNode(data);
newNode.next = this.head;
this.head = newNode;
return;
}
let current = this.head;
for (let i = 0; i < index - 1 && current; i++) {
current = current.next;
}
if (!current) throw new Error('Index out of bounds');
const newNode = new ListNode(data);
newNode.next = current.next;
current.next = newNode;
}
// 删除指定值的第一个节点
remove(data) {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next && current.next.data !== data) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
}
}
// 查找是否包含某个值
contains(data) {
let current = this.head;
while (current) {
if (current.data === data) return true;
current = current.next;
}
return false;
}
// 转为数组便于查看
toArray() {
const result = [];
let current = this.head;
while (current) {
result.push(current.data);
current = current.next;
}
return result;
}
}使用示例：
const list = new LinkedList(); list.append(1); list.append(2); list.append(3); console.log(list.toArray()); // [1, 2, 3] list.insertAt(1, 1.5); console.log(list.toArray()); // [1, 1.5, 2, 3] list.remove(1.5); console.log(list.toArray()); // [1, 2, 3]
树形结构的实现
树是一种分层数据结构，最常见的是二叉树，每个节点最多有两个子节点：左子节点和右子节点。
定义树节点：
class TreeNode {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}二叉搜索树（BST）实现：
二叉搜索树满足：左子树所有节点值小于根节点，右子树所有节点值大于根节点。
class BinarySearchTree {
constructor() {
this.root = null;
}
// 插入节点
insert(data) {
const newNode = new TreeNode(data);
if (!this.root) {
this.root = newNode;
return;
}
this._insertNode(this.root, newNode);
}
_insertNode(node, newNode) {
if (newNode.data < node.data) {
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(data) {
return this._searchNode(this.root, data);
}
_searchNode(node, data) {
if (!node) return null;
if (data === node.data) return node;
return data < node.data
? this._searchNode(node.left, data)
: this._searchNode(node.right, data);
}
// 中序遍历（左-根-右），输出有序序列
inorderTraversal(node = this.root, result = []) {
if (node) {
this.inorderTraversal(node.left, result);
result.push(node.data);
this.inorderTraversal(node.right, result);
}
return result;
}
// 先序遍历（根-左-右）
preorderTraversal(node = this.root, result = []) {
if (node) {
result.push(node.data);
this.preorderTraversal(node.left, result);
this.preorderTraversal(node.right, result);
}
return result;
}
// 后序遍历（左-右-根）
postorderTraversal(node = this.root, result = []) {
if (node) {
this.postorderTraversal(node.left, result);
this.postorderTraversal(node.right, result);
result.push(node.data);
}
return result;
}
}使用示例：
const bst = new BinarySearchTree(); bst.insert(10); bst.insert(5); bst.insert(15); bst.insert(3); bst.insert(7); console.log(bst.inorderTraversal()); // [3, 5, 7, 10, 15] console.log(bst.preorderTraversal()); // [10, 5, 3, 7, 15] console.log(bst.postorderTraversal()); // [3, 7, 5, 15, 10] console.log(bst.search(7) !== null); // true console.log(bst.search(9) !== null); // false
链表适合频繁插入删除的场景，而树适合快速查找、排序和层级表达。JavaScript通过对象引用来构建这些结构非常自然。理解它们的原理有助于写出更高效的代码。
基本上就这些。掌握基本实现后，可以进一步扩展功能，比如双向链表、平衡树、删除节点等复杂操作。
