前端常用数据结构

前端常用数据结构

• 前端常用数据结构
• • 数据结构
  • 数组
  • 栈
  • 队列
  • 链表
  • • 单向链表
    • 双向链表
  • 树

前端常用数据结构

• 什么是数据结构
• 常���的数据结构
  • 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]); // undefinedarr[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()); // truestack.push(1);stack.push(2);stack.push(3);stack.push(4, 5, 6);console.log(stack.size()); // 6// 访问栈顶的元素console.log(stack.peek