前端常用数据结构

前端常用数据结构

• 什么是数据结构
• 常用的数据结构
  • JavaScript 如何实现
  • 这些数据结构实际场景

数据结构

所谓数据结构，是在计算机中组织、管理和存储数据的一种方式。

🙋：你知道哪些数据结构？

数据结构整体可以分为两大类：线性数据结构 和 非线性数据结构

• 线性数据结构：数据会排列成线性的序列

  • 数组（Array）：一种固定大小的数据结构，里面存储相同类型的元素集合。通过索引来进行访问。
  • 链表（Linked List）：由一个一个的节点组成，每个节点会包含数据还有下一个节点的指针（内存地址）
  • 栈（Stack）：只有一个出入口，先进后出、后进先出
  • 队列（Queue）：有两个口，因此先进先出，后进后出

• 非线性数据结构：顾名思义，就是元素不以线性的顺序排列

  • 树（Tree）：体现了一个层次，DOM 树、组件树
  • 图（Graph）：由多个节点以及连接节点的边组成。
  • 哈希表（Hash Table）

前端常用的数据结构有：数组、栈、队列、链表以及树

数组

回顾一下数组创建的方法：

// 字面量创建
const arr = [];
// Array构造函数
const arr2 = new Array(3); // 如果参数只有一个值，那么表示的是长度
const arr3 = new Array(1, 2, 3); // 如果参数是多个值，那么表示的是数组的元素
// Array.of方法：ES6 新引入的方法
// 解决 Array 构造函数参数只有一个的时候的怪异行为
const arr4 = Array.of(3); // [3]
const arr5 = Array.of(1, 2, 3); // [1, 2, 3]
// Array.from方法：从一个类组数对象或者可迭代对象创建一个新的数组
const arr6 = Array.from("abc"); // ['a', 'b', 'c']
// 扩展运算符
const a = [1, 2, 3];
const b = [4, 5, 6];
const arr7 = [...a, ...b];

严格意义来讲，JS 里面所提供的数组并非数据结构里面的数组：

int[] arr = new int[3];
arr[0] = 100; // 合法
arr[1] = 200; // 合法
arr[2] = 300; // 合法
arr[3] = 400; // 报错：数组越界

在 JS 中压根儿就没有数组越界这个概念

const arr = [];
console.log(arr[10]); // undefined
arr[10] = 100;
console.log(arr[10]); // 100

究其原因，是因为 JS 底部，数组实际上就是对象。

类似于：

const arr = {0: 100,1: 200,2: 300,
};
console.log(arr[0]);

栈

• FILO（first in last out）：先进后出
• LIFO（last in first out）：后进先出

class Stack {constructor(...args) {this.stack = [...args];}// 返回栈中元素的数量size() {return this.stack.length;}// 检查栈是否为空isEmpty() {return this.size() === 0;}// 添加一个或者多个元素到栈顶push(...items) {return this.stack.push(...items);}// 移除栈顶元素，返回被移除的元素pop() {return this.stack.pop();}// 返回栈顶元素，但是不删除peek() {return this.isEmpty() ? undefined : this.stack[this.size() - 1];}
}const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4, 5, 6);
console.log(stack.size()); // 6
// 访问栈顶的元素
console.log(stack.peek