说说你了解的js数据结构？

问题解析

数据结构是计算机存储、组织数据的方式。在 JavaScript 开发中，虽然数组和对象是最常用的，但了解更多的数据结构可以帮助我们编写更高效的代码，解决更复杂的问题。

核心概念

数据结构意味着接口或封装：一个数据结构可被视为两个函数之间的接口，或者是由数据类型联合组成的存储内容的访问方法封装。

详细解答

1. 数组（Array）

数组是最基本的数据结构，使用一块连续的内存空间保存数据。

// 创建数组
let arr = [1, 2, 3, 4, 5];

// 特点：
// 1. 连续内存存储
// 2. 通过索引访问，时间复杂度 O(1)
// 3. 插入/删除可能需要移动元素，时间复杂度 O(n)

// 常用操作
arr.push(6);        // 尾部添加: O(1)
arr.pop();          // 尾部删除: O(1)
arr.unshift(0);     // 头部添加: O(n)
arr.shift();        // 头部删除: O(n)
arr.splice(2, 1);   // 中间删除: O(n)

适用场景：数据结构较为简单，不需要频繁在中间位置插入/删除元素。

2. 栈（Stack）

栈是一种遵循**后进先出（LIFO）**原则的有序集合。

class Stack {
    constructor() {
        this.items = [];
    }

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

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

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

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}

// 使用示例
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack.peek()); // 2

应用场景：

• 函数调用栈
• 浏览器历史记录
• 撤销操作（Undo）
• 括号匹配检查

3. 队列（Queue）

队列是遵循**先进先出（FIFO）**原则的一组有序的项。

class Queue {
    constructor() {
        this.items = [];
    }

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

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

    // 查看队首
    front() {
        return this.items[0];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}

// 使用示例
const queue = new Queue();
queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C");
console.log(queue.dequeue()); // "A"
console.log(queue.front());   // "B"

应用场景：

• 任务队列
• 消息队列
• 广度优先搜索（BFS）

4. 链表（Linked List）

链表使用非连续的内存空间存储数据，每个节点包含数据和指向下一个节点的指针。

class ListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }

    // 在尾部添加节点
    append(data) {
        const newNode = new ListNode(data);
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.length++;
    }

    // 在指定位置插入
    insert(position, data) {
        if (position < 0 || position > this.length) return false;
        const newNode = new ListNode(data);
        if (position === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let current = this.head;
            let index = 0;
            while (index < position - 1) {
                current = current.next;
                index++;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
        this.length++;
        return true;
    }

    // 删除指定位置节点
    removeAt(position) {
        if (position < 0 || position >= this.length) return null;
        let current = this.head;
        if (position === 0) {
            this.head = current.next;
        } else {
            let index = 0;
            let previous = null;
            while (index < position) {
                previous = current;
                current = current.next;
                index++;
            }
            previous.next = current.next;
        }
        this.length--;
        return current.data;
    }
}

链表 vs 数组：

特性	数组	链表
内存分配	连续	非连续
随机访问	O(1)	O(n)
头部插入/删除	O(n)	O(1)
尾部插入/删除	O(1)	O(n)（需遍历）
中间插入/删除	O(n)	O(n)（查找）+ O(1)（操作）

应用场景：

• 需要频繁在头部/中间插入删除的场景
• 实现 LRU 缓存
• 实现文件系统

5. 字典（Map）/ 哈希表（Hash Table）

字典是一种以键-值对存储数据的数据结构，JavaScript 中的 Object 和 Map 都是字典的实现。

// 使用 Object 作为字典
const dict = {};
dict["name"] = "John";
dict["age"] = 25;
console.log(dict["name"]); // "John"

// 使用 ES6 Map
const map = new Map();
map.set("name", "John");
map.set("age", 25);
map.set({ id: 1 }, "object key"); // 可以用对象作为键

console.log(map.get("name")); // "John"
console.log(map.has("age"));  // true
console.log(map.size);        // 3

// 遍历
map.forEach((value, key) => {
    console.log(key, value);
});

// Map vs Object
// 1. Map 的键可以是任意类型，Object 的键只能是字符串或 Symbol
// 2. Map 保持插入顺序，Object 不保证（虽然现代引擎通常保持顺序）
// 3. Map 有 size 属性，Object 需要手动计算
// 4. Map 在频繁增删键值对时性能更好

哈希表原理：

• 通过哈希函数将键映射为数组索引
• 理想情况下，插入、删除、查找都是 O(1)
• 哈希冲突解决方法：开链法、线性探测法

6. 集合（Set）

集合是一种存储唯一值的数据结构。

// 使用 ES6 Set
const set = new Set();
set.add(1);
set.add(2);
set.add(2); // 重复值被忽略
set.add(3);

console.log(set.size);      // 3
console.log(set.has(2));    // true
set.delete(2);
console.log(set.has(2));    // false

// 数组去重
const arr = [1, 2, 2, 3, 3, 3];
const unique = [...new Set(arr)];
console.log(unique); // [1, 2, 3]

// 集合运算
const setA = new Set([1, 2, 3]);
const setB = new Set([2, 3, 4]);

// 交集
const intersection = new Set([...setA].filter(x => setB.has(x)));
console.log(intersection); // Set {2, 3}

// 并集
const union = new Set([...setA, ...setB]);
console.log(union); // Set {1, 2, 3, 4}

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

7. 树（Tree）

树是一种分层数据结构，由节点和边组成。

// 二叉树节点
class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 二叉搜索树
class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const newNode = new TreeNode(value);
        if (!this.root) {
            this.root = newNode;
            return;
        }

        let current = this.root;
        while (true) {
            if (value < current.value) {
                if (!current.left) {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = newNode;
                    return;
                }
                current = current.right;
            }
        }
    }

    // 中序遍历（左-根-右）
    inOrderTraversal(node = this.root, result = []) {
        if (node) {
            this.inOrderTraversal(node.left, result);
            result.push(node.value);
            this.inOrderTraversal(node.right, result);
        }
        return result;
    }
}

// 使用示例
const bst = new BinarySearchTree();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(1);
bst.insert(4);
console.log(bst.inOrderTraversal()); // [1, 3, 4, 5, 7]

树的类型：

• 二叉树：每个节点最多两个子节点
• 二叉搜索树：左子树所有节点值 < 根节点值 < 右子树所有节点值
• 平衡二叉树：左右子树高度差不超过1（如 AVL 树、红黑树）
• B树/B+树：多路搜索树，常用于数据库索引

8. 图（Graph）

图是由节点（顶点）和边组成的非线性数据结构。

// 使用邻接表表示图
class Graph {
    constructor() {
        this.adjacencyList = new Map();
    }

    addVertex(vertex) {
        if (!this.adjacencyList.has(vertex)) {
            this.adjacencyList.set(vertex, []);
        }
    }

    addEdge(vertex1, vertex2) {
        this.adjacencyList.get(vertex1).push(vertex2);
        this.adjacencyList.get(vertex2).push(vertex1); // 无向图
    }

    // 广度优先搜索
    bfs(start) {
        const queue = [start];
        const visited = new Set([start]);
        const result = [];

        while (queue.length > 0) {
            const vertex = queue.shift();
            result.push(vertex);

            const neighbors = this.adjacencyList.get(vertex);
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
        return result;
    }

    // 深度优先搜索
    dfs(start, visited = new Set(), result = []) {
        visited.add(start);
        result.push(start);

        const neighbors = this.adjacencyList.get(start);
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                this.dfs(neighbor, visited, result);
            }
        }
        return result;
    }
}

9. 堆（Heap）

堆是一种特殊的完全二叉树，分为最大堆和最小堆。

class MinHeap {
    constructor() {
        this.heap = [];
    }

    getParentIndex(i) {
        return Math.floor((i - 1) / 2);
    }

    getLeftChildIndex(i) {
        return 2 * i + 1;
    }

    getRightChildIndex(i) {
        return 2 * i + 2;
    }

    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }

    insert(value) {
        this.heap.push(value);
        this.heapifyUp(this.heap.length - 1);
    }

    heapifyUp(index) {
        let currentIndex = index;
        while (currentIndex > 0) {
            const parentIndex = this.getParentIndex(currentIndex);
            if (this.heap[currentIndex] < this.heap[parentIndex]) {
                this.swap(currentIndex, parentIndex);
                currentIndex = parentIndex;
            } else {
                break;
            }
        }
    }

    extractMin() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);
        return min;
    }

    heapifyDown(index) {
        let currentIndex = index;
        while (true) {
            const leftChild = this.getLeftChildIndex(currentIndex);
            const rightChild = this.getRightChildIndex(currentIndex);
            let smallest = currentIndex;

            if (leftChild < this.heap.length && this.heap[leftChild] < this.heap[smallest]) {
                smallest = leftChild;
            }
            if (rightChild < this.heap.length && this.heap[rightChild] < this.heap[smallest]) {
                smallest = rightChild;
            }

            if (smallest !== currentIndex) {
                this.swap(currentIndex, smallest);
                currentIndex = smallest;
            } else {
                break;
            }
        }
    }
}

深入理解

数据结构选择指南

场景	推荐数据结构
需要快速随机访问	数组
需要频繁在头部操作	链表、双端队列
需要后进先出	栈
需要先进先出	队列
需要快速查找/插入/删除	哈希表
需要去重	集合
需要维护有序数据	二叉搜索树、堆
需要表示层级关系	树
需要表示网络关系	图

最佳实践

1. 根据使用场景选择合适的数据结构
2. 优先使用 JavaScript 内置的 Map 和 Set，而不是 Object 来存储键值对和唯一值
3. 理解时间复杂度，在性能敏感的场景选择合适的数据结构
4. 对于复杂数据结构，考虑使用现有库（如 Immutable.js）

面试要点

1. JavaScript 中常用的数据结构有哪些？

   • 数组、栈、队列、链表、字典/哈希表、集合、树、图、堆

2. 数组和链表的区别？

   • 数组连续存储，支持随机访问 O(1)，但插入删除慢 O(n)
   • 链表非连续存储，不支持随机访问 O(n)，但插入删除快 O(1)

3. Map 和 Object 的区别？

   • Map 键可以是任意类型，Object 只能是字符串/Symbol
   • Map 保持插入顺序，有 size 属性
   • Map 在频繁增删时性能更好

4. 什么是哈希冲突？如何解决？

   • 不同键通过哈希函数得到相同索引
   • 解决方法：开链法（拉链法）、线性探测法