【JS常见数据结构】

前言

JavaScript数据结构是指数据的组织方式

常见的数据结构包括数组、链表、栈、队列、树、图等。在JavaScript中，数组是最常见和最基础的数据结构，而链表、栈和队列等数据结构则需要通过对象和数组等方式进行模拟。

数组

数组是一种线性数据结构，由一系列连续的空间组成，用于存储一组具有相同数据类型的元素。数组是最简单、最基础的数据结构之一，它的操作通常包括访问、插入、删除和查找。

JavaScript 中的数组是一种特殊的对象，可以通过索引来访问元素，索引从 0 开始计数。JavaScript 数组可以存储任意类型的数据，包括数字、字符串、布尔值和对象等。同时也支持动态调整数组的长度，即在数组末尾添加或删除元素。

JavaScript 中数组的常见操作：

1. 创建数组：

let arr = []; // 创建一个空数组
let arr2 = [1, 2, 3, 4, 5]; // 创建一个包含五个元素的数组

2. 访问数组元素：

let arr = [1, 2, 3, 4, 5];
console.log(arr[2]); // 3

3. 插入元素：

let arr = [1, 2, 3, 4, 5];
arr.push(6); // 在末尾添加元素
arr.unshift(0); // 在开头添加元素
arr.splice(2, 0, 2.5); // 在指定位置插入元素

4. 删除元素：

let arr = [1, 2, 3, 4, 5];
arr.pop(); // 删除末尾元素
arr.shift(); // 删除开头元素
arr.splice(2, 1); // 删除指定位置的元素

5. 查询元素：

let arr = [1, 2, 3, 4, 5];
console.log(arr.indexOf(3)); // 2
console.log(arr.includes(6)); // false

JavaScript 的数组还有一些高阶函数，如 map、filter、reduce 等，可用于快速地操作数组中的元素。同时也可以利用数组进行栈、队列等数据结构的实现。
JS 常用的数组方法有：

1. push()：将一个或多个元素添加到数组末尾。
2. pop()：删除数组的最后一个元素。
3. unshift()：将一个或多个元素添加到数组开头。
4. shift()：删除数组的第一个元素。
5. splice()：在指定位置插入或删除元素。
6. slice()：从数组中截取指定部分的元素。
7. concat()：连接两个或多个数组。
8. join()：将数组中的元素以指定的分隔符连接成字符串。
9. reverse()：反转数组中元素的顺序。
10. sort()：按照指定的排序规则对数组中的元素进行排序。
11. indexOf()：返回指定元素在数组中第一次出现的索引。
12. lastIndexOf()：返回指定元素在数组中最后一次出现的索引。
13. filter()：返回一个新数组，其中包含符合指定条件的所有元素。
14. map()：返回一个新数组，其中包含对原数组的每个元素进行操作后的结果。
15. reduce()：对数组中的所有元素进行累加或累积计算，返回计算结果。
16. forEach()：对数组中的每个元素执行指定的操作。

链表

链表是一种常见的数据结构，用于存储一系列元素。它由一系列的节点（Node）组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

链表与数组相比，具有以下优点：

• 链表可以在任何位置添加或删除元素，而数组需要移动元素来完成这些操作；
• 链表可以动态分配空间，而数组的大小是固定的；
• 链表的查找和访问效率比数组差。

链表通常分为单向链表、双向链表和循环链表三种。

单向链表

单向链表是最基本的链表类型，每个节点只有一个指针指向下一个节点，最后一个节点的指针指向 null。

JavaScript 实现单向链表可以使用对象字面量或者构造函数：

// 对象字面量实现单向链表
let node1 = { data: 1, next: null };
let node2 = { data: 2, next: null };
let node3 = { data: 3, next: null };node1.next = node2;
node2.next = node3;// 构造函数实现单向链表
class Node {constructor(data) {this.data = data;this.next = null;}
}let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);node1.next = node2;
node2.next = node3;

双向链表

双向链表每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。

JavaScript 实现双向链表可以参考以下代码：

class Node {constructor(data) {this.data = data;this.prev = null;this.next = null;}
}class DoublyLinkedList {constructor() {this.head = null;this.tail = null;}add(data) {let node = new Node(data);if (!this.head) {this.head = node;} else {this.tail.next = node;node.prev = this.tail;}this.tail = node;}remove(data) {let current = this.head;while (current) {if (current.data === data) {if (current === this.head && current === this.tail) {this.head = null;this.tail = null;} else if (current === this.head) {this.head = this.head.next;this.head.prev = null;} else if (current === this.tail) {this.tail = this.tail.prev;this.tail.next = null;} else {current.prev.next = current.next;current.next.prev = current.prev;}}current = current.next;}}
}

循环链表

循环链表是一种特殊的链表，它的最后一个节点的指针不是 null，而是指向第一个节点。循环链表可以用于模拟环形结构。

JavaScript 实现循环链表可以参考以下代码：

class Node {constructor(data) {this.data = data;this.next = null;}
}class CircularLinkedList {constructor() {this.head = null;this.tail = null;}add(data) {let node = new Node(data);if (!this.head) {this.head = node;} else {this.tail.next = node;}this.tail = node;this.tail.next = this.head;}remove(data) {let current = this.head;let previous = null;while (current) {if (current === this.head && current === this.tail) {this.head = null;this.tail = null;break;} else if (current === this.head) {this.head = this.head.next;this.tail.next = this.head;} else if (current === this.tail) {previous.next = this.head;this.tail = previous;} else {previous.next = current.next;}previous = current;current = current.next;}}
}

以上就是 JavaScript 实现链表的基本介绍和示例代码。在实际开发中，链表通常用于实现诸如 LRU 缓存、哈希表等数据结构。

栈

栈是一种后进先出(LIFO)的数据结构，它可以用数组或链表来实现。在栈中，最后插入的元素被称为栈顶，而最早插入的元素被称为栈底。栈的基本操作包括入栈(push)和出栈(pop)两个操作。

入栈操作是将元素添加到栈顶，并更新栈顶位置，而出栈操作则是将栈顶元素删除，并更新栈顶位置。其他常用操作包括访问栈顶元素(peek)，获取栈的大小(size)和判断栈是否为空(isEmpty)。

栈在计算机领域应用广泛，例如在程序调用栈中，每当函数被调用时都会将其返回地址等信息压入栈中，函数执行完毕后再将这些信息弹出以返回到调用点；在表达式的求值中，栈可以用来记录运算符和操作数，完成中缀表达式转换为后缀表达式等操作。

下面是栈的 JavaScript 实现：

class Stack {constructor() {this.items = [];this.top = -1;}push(element) {this.items[++this.top] = element;}pop() {if (this.isEmpty()) return null;return this.items[this.top--];}peek() {if (this.isEmpty()) return null;return this.items[this.top];}size() {return this.top + 1;}isEmpty() {return this.top === -1;}clear() {this.items = [];this.top = -1;}
}

在这个实现中，使用了数组来存储栈元素，变量this.top表示栈顶位置。push操作利用了 JavaScript 数组自带的push方法，在栈顶插入元素并更新栈顶位置；pop操作利用了数组自带的pop方法，删除栈顶元素并更新栈顶位置，同时如果栈为空则返回null；peek操作返回栈顶元素，如果栈为空则返回null；size操作返回栈大小，即栈中元素个数；isEmpty操作判断栈是否为空；clear操作清空栈，即将栈数组和栈顶位置重置为初始状态。

队列

队列是一种线性数据结构，可用于在一端添加元素(队尾)，在另一端删除元素(队首)。队列遵循先进先出(FIFO)原则，即先加入队列的元素先被删除。

队列的常用操作包括：

• 入队(enqueue)：将元素添加到队列的末尾。
• 出队(dequeue)：从队列的头部删除元素并返回。
• 队首(peek)：返回队列头部元素，但不删除它。
• 队列元素个数(size)：返回队列中元素的个数。
• 队列是否为空(isEmpty)：判断队列是否为空。

队列的实现方式有多种，常见的有数组和链表。

数组实现队列：

class Queue {constructor() {this.items = [];}enqueue(item) {this.items.push(item);}dequeue() {if (this.items.length === 0) {return null;}return this.items.shift();}peek() {if (this.items.length === 0) {return null;}return this.items[0];}size() {return this.items.length;}isEmpty() {return this.items.length === 0;}
}

链表实现队列：

class Node {constructor(item) {this.item = item;this.next = null;}
}class Queue {constructor() {this.head = null;this.tail = null;this.length = 0;}enqueue(item) {const node = new Node(item);if (this.length === 0) {this.head = node;this.tail = node;} else {this.tail.next = node;this.tail = node;}this.length++;}dequeue() {if (this.isEmpty()) {return null;}const item = this.head.item;this.head = this.head.next;this.length--;return item;}peek() {if (this.isEmpty()) {return null;}return this.head.item;}size() {return this.length;}isEmpty() {return this.length === 0;}
}

树

树是一种非常常见的数据结构。树结构呈现出有层次的关系，由根节点开始，每个节点可以有多个子节点，但每个节点只能有一个父节点。

树的组成部分包括：节点、边和路径。

节点：树中的每个元素称为一个节点。每个节点包括一个值和指向它的子节点的引用。

边：节点之间的链接称为边，边表示节点之间的关系。

路径：路径是连接两个节点的边的序列。

树有很多种类，每种树都有自己的特定性质和用途。以下是一些常见的树：

• 二叉树：每个节点最多有两个子节点。
• 二叉搜索树：是一种特殊的二叉树，左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值。
• AVL 树：是一种平衡二叉搜索树，使得所有叶子节点到根节点的路径上的高度差最多为 1。
• B 树：一种多路搜索树，每个节点可以有多个子节点。
• 红黑树：是一种自平衡二叉搜索树，能够保证任何一个节点的左右子树高度差小于两倍。

二叉树示例

其中每个节点最多有两个子节点：一个左子节点和一个右子节点。二叉树常用于搜索和排序操作，以及表示表达式和编译器中的语法树。

在 JavaScript 中，可以使用对象来表示二叉树。每个节点都是一个对象，包含一个 value 属性表示节点的值，以及 left 和 right 属性，分别表示该节点的左子节点和右子节点。

以下是一个简单的例子：

class Node {constructor(value) {this.value = value;this.left = null;this.right = null;}
}const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

以上代码创建了一个二叉树，根节点的值为 1，左子节点的值为 2，右子节点的值为 3。2 的左子节点的值为 4，右子节点的值为 5。

遍历二叉树是常见的操作之一。以下是三种遍历方式的实现：

// 前序遍历
function preOrder(root) {if (!root) return;console.log(root.value);preOrder(root.left);preOrder(root.right);
}// 中序遍历
function inOrder(root) {if (!root) return;inOrder(root.left);console.log(root.value);inOrder(root.right);
}// 后序遍历
function postOrder(root) {if (!root) return;postOrder(root.left);postOrder(root.right);console.log(root.value);
}

前序遍历先访问根节点，然后访问左子树，最后访问右子树。中序遍历先访问左子树，然后访问根节点，最后访问右子树。后序遍历先访问左子树，然后访问右子树，最后访问根节点。
除了遍历，二叉树还可以进行插入、删除等操作。这些操作通常需要对树进行递归遍历和修改。

树的应用非常广泛，比如在计算机科学中，树被广泛地应用于搜索算法、排序算法、编译器、操作系统、数据库、人工智能和网络技术等领域。

图

图是一种非常重要的数据结构，由节点和边组成，一些常用的应用包括社交网络分析、路线规划等。下面我将为你详细介绍图的相关概念和示例，希望能帮助你更好地理解。

图的定义

图是由节点和边组成的一种非线性数据结构，它是一组二元关系的集合。节点也称为顶点，边用于连接节点，表示它们之间的关系。每个节点可以有多个相邻节点，这些节点通过边连接在一起。

图可以由以下元素组成：

• 节点（顶点）：表示图中的对象，可以是任何对象；
• 边：连接节点之间的线段，表示节点之间的关系；
• 权重：每条边上的权重，表示两个节点之间的距离或者代价；
• 路径：由边连接的一组节点；
• 网络：由边连接的一组节点和它们的权重。

图的分类

图可以按照有无方向、有无边权、有无环等特性进行分类。

按照有无方向，图可以分为有向图和无向图。有向图中，每条边都有一个方向，从一个节点指向另一个节点。无向图中，每条边没有方向，两个节点之间的关系是相互的。

按照有无边权，图可以分为带权图和无权图。带权图中，每条边都有一个代价或权重，代表两个节点之间的距离或代价。无权图中，每条边没有权重，代表两个节点之间的关系是相等的。

按照有无环，图可以分为有环图和无环图。有环图中，两个节点之间可以有多条路径；无环图中，两个节点之间最多只有一条路径。

图的表示方法

图可以使用多种方式进行表示，最常用的三种方式是邻接矩阵、邻接表和关联矩阵。

邻接矩阵

邻接矩阵是表示图的一种方法，它使用一个二维数组表示节点之间的连接关系。矩阵中的每个元素表示两个节点之间是否有连接，1表示有连接，0表示没有连接，如果是带权图，则可以将0表示为Infinity或-1。

[ [0, 1, 0, 1],[1, 0, 1, 0],[0, 1, 0, 1],[1, 0, 1, 0]
]

在上面的邻接矩阵中，行和列分别代表图中的节点，如果第i行第j列的元素为1，则表示节点i和节点j之间有一条边。如果是带权图，则可以在矩阵中存储边的权重。

邻接表

邻接表是表示图的一种方法，它使用链表的方式表示节点之间的连接关系。每个节点都有一个链表，链表中存储与该节点相邻的节点。

[[1, 3],[0, 2],[1, 3],[0, 2]
]

在上面的邻接表中，数组的下标代表节点的编号，数组元素是一个链表，该链表中存储与该节点相邻的节点的编号。如果是带权图，则链表中可以存储该边的权重。

关联矩阵

关联矩阵也是表示图的一种方法，它使用一个二维数组表示节点与边之间的关系。矩阵中的每个元素表示一个节点和一条边是否有连接关系。如果是带权图，则可以在矩阵中存储边的权重。

[[1, 0, 1, 0],[1, 1, 0, 0],[0, 1, 1, 1],[0, 0, 0, 1],[1, 1, 0, 1]
]

在上面的关联矩阵中，行和列分别代表图中的节点和边。如果第i行第j列的元素为1，则表示节点i和边j之间有连接。

图的遍历

图的遍历是指按照某种顺序来访问图中的所有节点，常用的遍历方法有深度优先遍历和广度优先遍历。

深度优先遍历

深度优先遍历从图中的一个节点开始，一直向下访问，直到没有未访问的节点为止，然后返回之前未访问过的节点，再依次访问。

const visited = [];
function depthFirstSearch(graph, node) {visited[node] = true;console.log(node);for (let i = 0; i < graph[node].length; i++) {const neighbor = graph[node][i];if (!visited[neighbor]) {depthFirstSearch(graph, neighbor);}}
}depthFirstSearch(graph, 0);

上面的代码是使用深度优先遍历来访问图中的节点，visited数组用于记录每个节点是否已经访问过，如果未访问过，则递归遍历该节点所连接的所有节点。

广度优先遍历

广度优先遍历从图中的一个节点开始，访问该节点的所有相邻节点，然后依次访问相邻节点的相邻节点，直到访问完所有节点为止。

function breadthFirstSearch(graph, startNode) {const visited = [];const queue = [];queue.push(startNode);visited[startNode] = true;while (queue.length) {const node = queue.shift();console.log(node);for (let i = 0; i < graph[node].length; i++) {const neighbor = graph[node][i];if (!visited[neighbor]) {visited[neighbor] = true;queue.push(neighbor);}}}
}breadthFirstSearch(graph, 0);

上面的代码是使用广度优先遍历来访问图中的节点，visited数组用于记录每个节点是否已经访问过，queue用于保存待访问的节点，先将起始节点入队，然后依次从队列中取出节点，将该节点的相邻节点入队。

图的常见算法

图是一个重要的数据结构，它有许多常见的算法，包括最短路径算法、拓扑排序算法、最小生成树算法等。

最短路径算法

最短路径算法用于求图中两个节点之间的最短路径，其中最常用的算法是Dijkstra算法和Bellman-Ford算法。

Dijkstra算法是一种贪心算法，它从起点向外扩展，每次找到当前距离最近的节点，并更新与之相邻节点的距离值，直到到达目标节点。

Bellman-Ford算法是一种动态规划算法，它从起点开始，依次更新到每个节点的距离值，循环执行N次，直到没有新的更新为止，其中N是图中节点的数量。它可以处理带有负权边的图，但是时间复杂度较高。

拓扑排序算法

拓扑排序算法用于对有向无环图进行排序，它可以用于任务调度、依赖关系分析等场景。

拓扑排序算法的基本思想