高级数据结构

JavaScript 提供了一些内置的数据结构，可以满足多数常见需求，但在处理复杂问题时，可以结合这些数据结构或实现自定义高级数据结构。以下是 JavaScript 中的高级数据结构及其实现方式和应用：

1. Map

Map 是一种无序的键值对集合，可以用来存储和检索键值对。它类似于对象，但有以下几个不同点：

• Map 中的键值对是无序的，因此没有索引，只能通过键来获取值。
• Map 中的键可以是任意值，而对象只能是字符串或 Symbol。
• Map 中的值可以是任意类型，而对象的值只能是基本类型。

const map = new Map();
// 添加键值对
map.set('key1', 'value1');
map.set('key2', 'value2');
// 获取值
console.log(map.get('key1'));
// 检查是否存在
console.log(map.has('key2'));
// 删除键值对
map.delete('key2');
// 获取大小
console.log(map.size);
// 遍历
for (const [key, value] of map) {
    console.log(`${key}: ${value}`);
}

2. WeakMap

WeakMap 与 Map 类似，也是一种键值对集合，但它的键是弱引用的，即如果没有其他引用指向这个键，那么它会被垃圾回收。

const weakMap = new WeakMap();

const obj = {name: 'John'};
weakMap.set(obj, 'age');

console.log(weakMap.get(obj)); // 'age'

3. Set

Set 是一种无序的集合，它类似于数组，但只能存储唯一的值。

const set = new Set();

set.add(1);
set.add(2);
set.add(3);
set.add(2);

console.log(set); // Set(3) { 1, 2, 3 }

4. WeakSet

WeakSet 与 Set 类似，也是一种集合，但它的成员是弱引用的，即如果没有其他引用指向这个成员，那么它会被垃圾回收。

const weakSet = new WeakSet();

const obj = {name: 'John'};
weakSet.add(obj);

console.log(weakSet.has(obj)); // true

集合运算

const setA = new Set([1, 2, 3]);
const setB = new Set([3, 4, 5]);

// 并集
const union = new Set([...setA, ...setB]);

// 交集
const intersection = new Set([...setA].filter(x => setB.has(x)));

// 差集
const difference = new Set([...setA].filter(x => !setB.has(x)));

console.log(union);         // 输出: Set(5) { 1, 2, 3, 4, 5 }
console.log(intersection);  // 输出: Set(1) { 3 }
console.log(difference);    // 输出: Set(2) { 1, 2 }

5.链表 (Linked List)

链表是一种数据结构，它是由节点组成的线性结构。每个节点包含一个数据项和一个指向下一个节点的引用。链表的优点是可以在 O(1) 时间内插入和删除节点，但缺点是查找节点需要 O(n) 时间。

单向链表

// 定义节点类
class Node {
    constructor(value) {
        this.value = value; // 节点的值
        this.next = null;   // 指向下一个节点的指针，初始为 null
    }
}

// 定义链表类
class LinkedList {
    constructor() {
        this.head = null; // 链表的头节点，初始为 null
    }

    // 在链表末尾添加新节点
    append(value) {
        const newNode = new Node(value); // 创建一个新节点
        if (!this.head) {
            // 如果链表为空，将新节点设为头节点
            this.head = newNode;
            return;
        }
        // 遍历链表，找到最后一个节点
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        // 将新节点连接到最后一个节点的 next 指针
        current.next = newNode;
    }

    // 显示链表中的所有节点值
    display() {
        let current = this.head; // 从头节点开始
        while (current) {
            console.log(current.value); // 输出当前节点的值
            current = current.next;    // 移动到下一个节点
        }
    }
}

// 创建一个链表实例并测试功能
const list = new LinkedList();
list.append(1); // 向链表中添加值为 1 的节点
list.append(2); // 向链表中添加值为 2 的节点
list.append(3); // 向链表中添加值为 3 的节点
list.display(); // 输出链表中的所有节点值：1 2 3

双向链表

// 定义节点类（用于双向链表的节点）
class Node {
    constructor(value) {
        this.value = value; // 节点的值
        this.prev = null;   // 指向前一个节点的指针，初始为 null
        this.next = null;   // 指向后一个节点的指针，初始为 null
    }
}

// 定义双向链表类
class DoublyLinkedList {
    constructor() {
        this.head = null; // 链表的头节点，初始为 null
        this.tail = null; // 链表的尾节点，初始为 null
    }

    // 在链表末尾添加新节点
    append(value) {
        const newNode = new Node(value); // 创建一个新节点
        if (!this.head) {
            // 如果链表为空，将新节点设为头节点和尾节点
            this.head = newNode;
            this.tail = newNode;
            return;
        }
        // 将新节点连接到尾节点的 next 指针
        this.tail.next = newNode;
        // 将尾节点连接到新节点的 prev 指针
        newNode.prev = this.tail;
        // 更新尾节点为新节点
        this.tail = newNode;
    }

    // 在链表头部添加新节点
    prepend(value) {
        const newNode = new Node(value); // 创建一个新节点
        if (!this.head) {
            // 如果链表为空，将新节点设为头节点和尾节点
            this.head = newNode;
            this.tail = newNode;
            return;
        }
        // 将新节点的 next 指针指向当前头节点
        newNode.next = this.head;
        // 将当前头节点的 prev 指针指向新节点
        this.head.prev = newNode;
        // 更新头节点为新节点
        this.head = newNode;
    }

    // 显示链表中的所有节点值（从头到尾遍历）
    display() {
        let current = this.head; // 从头节点开始遍历
        while (current) {
            console.log(current.value); // 输出当前节点的值
            current = current.next;    // 移动到下一个节点
        }
    }
}

// 创建一个双向链表实例并测试功能
const list = new DoublyLinkedList();
list.append(1);  // 向链表尾部添加值为 1 的节点
list.append(2);  // 向链表尾部添加值为 2 的节点
list.append(3);  // 向链表尾部添加值为 3 的节点
list.prepend(0); // 向链表头部添加值为 0 的节点
list.display();  // 输出链表中的所有节点值：0 1 2 3

6.栈 (Stack)

栈是一种线性数据结构，只能在一端进行插入和删除操作，遵循先进后出 (FILO) 原则。栈的应用场景包括函数调用栈、表达式求值、浏览器的前进后退、撤销操作等。

// 定义栈类
class Stack {
    constructor() {
        this.items = []; // 栈的元素数组
    }

    // 入栈
    push(item) {
        this.items.push(item);
    }

    // 出栈
    pop() {
        return this.items.pop();
    }

    // 栈是否为空
    isEmpty() {
        return this.items.length === 0;
    }

    // 栈的大小
    size() {
        return this.items.length;
    }

    // 栈顶元素
    peek() {
        return this.items[this.items.length - 1];
    }
}

// 创建一个栈实例并测试功能
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.peek()); // 输出栈顶元素：3
console.log(stack.pop()); // 输出栈顶元素：3
console.log(stack.pop()); // 输出栈顶元素：2
console.log(stack.pop()); // 输出栈顶元素：1
console.log(stack.isEmpty()); // 输出栈是否为空：true

7.队列 (Queue)

队列是一种线性数据结构，只能在一端进行插入操作，另一端进行删除操作，遵循先进先出 (FIFO) 原则。队列的应用场景包括排队、打印任务、CPU 任务调度等。

// 定义队列类
class Queue {
    constructor() {
        this.items = []; // 队列的元素数组
    }

    // 入队
    enqueue(item) {
        this.items.push(item);
    }

    // 出队
    dequeue() {
        return this.items.shift();
    }

    // 队列是否为空
    isEmpty() {
        return this.items.length === 0;
    }

    // 队列的大小
    size() {
        return this.items.length;
    }

    // 队列头元素
    peek() {
        return this.items[0];
    }
}

// 创建一个队列实例并测试功能
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.peek()); // 输出队列头元素：1
console.log(queue.dequeue()); // 输出队列头元素：1
console.log(queue.dequeue()); // 输出队列头元素：2
console.log(queue.dequeue()); // 输出队列头元素：3
console.log(queue.isEmpty()); // 输出队列是否为空：true

8.二叉树 (Binary Tree)

二叉树是一种树形数据结构，每个节点最多有两个子节点，分别为左子节点和右子节点。二叉树的应用场景包括文件系统、二叉查找树、二叉堆、二叉搜索树等。

// 定义节点类
class Node {
    constructor(value) {
        this.value = value; // 节点的值
        this.left = null;   // 左子节点
        this.right = null;  // 右子节点
    }
}

// 定义二叉搜索树类
class BST {
    constructor() {
        this.root = null; // 根节点
    }

    // 插入新节点
    insert(value) {
        const newNode = new Node(value); // 创建一个新节点
        if (!this.root) {
            // 如果树为空，将新节点设为根节点
            this.root = newNode;
            return;
        }
        let current = this.root; // 从根节点开始
        while (true) {
            if (value < current.value) {
                // 如果新节点的值小于当前节点的值，则移动到左子节点
                if (!current.left) {
                    current.left = newNode;
                    break;
                }
                current = current.left;
            } else {
                // 如果新节点的值大于等于当前节点的值，则移动到右子节点
                if (!current.right) {
                    current.right = newNode;
                    break;
                }
                current = current.right;
            }
        }
    }

    // 搜索节点
    search(value) {
        let current = this.root; // 从根节点开始
        while (current) {
            if (value === current.value) {
                // 如果找到了节点，返回节点的值
                return current.value;
            } else if (value < current.value) {
                // 如果值小于当前节点的值，则移动到左子节点
                current = current.left;
            } else {
                // 如果值大于当前节点的值，则移动到右子节点
                current = current.right;
            }
            // 如果没有找到节点，返回 null
            return null;
        }

        // 删除节点
        delete (value)
        {
            this.root = this._deleteNode(this.root, value);
        }

        // 递归删除节点
        _deleteNode(node, value)
        {
            if (!node) {
                // 如果节点不存在，返回 null
                return null;
            }
            if (value < node.value) {
                // 如果值小于当前节点的值，则递归删除左子节点
                node.left = this._deleteNode(node.left, value);
                return node;
            } else if (value > node.value) {
                // 如果值大于当前节点的值，则递归删除右子节点
                node.right = this._deleteNode(node.right, value);
                return node;
            } else {
                // 如果找到了节点，则删除该节点
                if (!node.left && !node.right) {
                    // 如果节点没有左右子节点，则直接删除该节点
                    return null;
                } else if (!node.left) {
                    // 如果节点只有右子节点，则将右子节点提升为当前节点
                    return node.right;
                } else if (!node.right) {
                    // 如果节点只有左子节点，则将左子节点提升为当前节点
                    return node.left;
                } else {
                    // 如果节点有左右子节点，则找到右子树中最小节点，替换当前节点的值，然后递归删除右子树中最小节点
                    const minNode = this._findMin(node.right);
                    node.value = minNode.value;
                    node.right = this._deleteNode(node.right, minNode.value);
                    return node;
                }
            }
        }

        // 找到右子树中最小节点
        _findMin(node)
        {
            while (node.left) {
                node = node.left;
            }
            return node;
        }
    }
}

// 创建一个二叉搜索树实例并测试功能
const bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
bst.insert(4);
bst.insert(6);
bst.insert(8);
console.log(bst.search(5)); // 输出节点值：5
console.log(bst.search(3)); // 输出节点值：3
console.log(bst.search(7)); // 输出节点值：7
console.log(bst.search(2)); // 输出节点值：2
console.log(bst.search(4)); // 输出节点值：4
console.log(bst.search(6)); // 输出节点值：6
console.log(bst.search(8)); // 输出节点值：8

9.图 (Graph)

图是一种复杂的非线性数据结构，由节点和边组成。图的应用场景包括网络、社交网络、地图等。

邻接表表示图

// 定义节点类
class Node {
    constructor(value) {
        this.value = value; // 节点的值
        this.neighbors = []; // 邻居节点数组
    }
}

// 定义图类
class Graph {
    constructor() {
        this.nodes = []; // 节点数组
    }

    // 添加节点
    addNode(value) {
        const node = new Node(value); // 创建一个新节点
        this.nodes.push(node);
        return node;
    }

    // 添加边
    addEdge(node1, node2) {
        node1.neighbors.push(node2);
        node2.neighbors.push(node1);
    }

    // 显示图
    display() {
        for (const node of this.nodes) {
            console.log(node.value + '的邻居：');
            for (const neighbor of node.neighbors) {
                console.log(neighbor.value);
            }
        }
    }
}

// 创建一个图实例并测试功能
const graph = new Graph();
const node1 = graph.addNode(1);
const node2 = graph.addNode(2);
const node3 = graph.addNode(3);
graph.addEdge(node1, node2);
graph.addEdge(node1, node3);
graph.display(); // 输出图：1的邻居：2 3 2的邻居：1 3 3的邻居：1 2