前端必须要掌握常见的数据结构，学会这招，让你对开发中的数据结构更加清晰！
一.队列
像排队一样，队列就是先进先出，排队入场！
image
class Queue {
constructor() {
this.arr = []
}
enqueue(element){ // 入队列
this.arr.push(element)
}
dequeue(){ // 出队列
return this.items.shift()
}
}
二.栈
像拿起堆放的柴火一样，栈就是先进后出，就是离场时后进的人先出！
image
class Stack {
constructor(){
this.arr = [];
}
push(element){ // 入栈
this.arr.push(element);
}
pop() { // 出栈
return this.items.pop();
}
}
三.链表
image
链表让我们删除数据和新增数据更加方便！
head指针指向第一个存入的元素节点，每个节点都有next属性指向一下一个元素节点，最后一个元素的指针指向null
创建一个节点，每个节点的结构非常简单
class Node {
constructor(element){
this.element = element; // 每个节点保存的内容
this.next = null; // 保存的指针，指向下一个节点
}
}
构建链表
class LinkList {
constructor(){
this.head = null; // 表头 默认指向第一个节点，没有为null
this.length = 0;
}
append(element){
// 追加节点
const node = new Node(element);
if(this.head == null){
this.head = node; // 第一个节点就是表头
}else{
let current = this.head;
// 从第一个节点查找到最后一个节点
while(current.next){
current = current.next;
}
current.next = node; // 找到最后一个节点添加next指向新增节点
}
this.length++; // 每增加一个长度
}
}
使用链表，不难看出链表的特点就是通过next来指向下一个节点（像链条一样）
const ll = new LinkList();
ll.append(1);
ll.append(2);
console.log(ll); // head: Node { element: 1, next: Node { element: 2, next: null } }
实现链表的插入
insert(position,element){
// 插入的时候判断插入的位置
if(position>=0 && position <=this.length){
const node = new Node(element); // 创建一个节点
if(position === 0){ // 如果位置是0
node.next = this.head; // 那么就让当前节点变成头
this.head = node;
}else{
let current = this.head; // 获取头节点查找位置
let previous = null;
let index = 0;
while(index++ < position){ // 查找到节点位置
previous = current;
current = current.next;
}
node.next = current; // 让当前节点next是刚才找到的节点
previous.next = node; // 他的上一个节点的next是当前节点
}
this.length++;
}
}
实现链表的删除
removeAt(position){
if(position > -1 && position < this.length){
if(position ==0){ // 如果是第一个直接改变指针
this.head = this.head.next
}else{
let index = 0;
let previous = null;
let current = this.head;
while(index++ < position){ // 找到要删除的这一项，直接让上一个指针指向下一个人
previous = current;
current = current.next
}
previous.next = current.next; // 上一个next直接指向下一个next
}
this.length--;
}
}
更新链表中的内容
update(position,element) {
if (position >= 0 && position < this.length) {
if (position === 0) {
// 根位置 直接更改跟的内容即可
this.head.element = element
}else{
let index = 0;
// 查找到要修改的项来更新
let current = this.head;
while(index++ < position){
current = current.next;
}
current.element = element;
}
}
}
四.集合
ES6已经为我们提供了Set的api，但是在某些时候(浏览器不支持的情况下),我们还是需要自己来实现Set的
class Set{
constructor(){
this.items = {};
}
has(value){ // 判断
return this.items.hasOwnProperty(value);
}
add(value){ // 像集合中添加
if(!this.has(value)){
this.items[value] = value;
}
}
remove(value){ // 删除集合中的某一项
if(this.has(value)){
delete this.items[value];
}
}
}
集合，常见的方法有：交集、并集、差集
五.hash表
image
特点是查找速度快，但是存储量需要手动扩展
class HashTable{
constructor(){
this.table = [];
}
calcuteHash(key){ // 通过put的key 计算hash戳，存到数组中
let hash = 0;
for(let s of key){
hash += s.charCodeAt();
}
return hash % 100; // 只能存放100个
}
get(key){ // 从hash表中取出值
let hash = this.calcuteHash(key);
return this.table[hash]
}
put(key,value){ // 像hash表中存入
let hash = this.calcuteHash(key);
this.table[hash] = value;
}
}
let hash = new HashTable();
hash.put('abc',1);
console.log(hash.get('abc'));
六.树
叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
image
前端最常考察的就是二叉树！
二叉树: 树中的节点最多只能有两个子节点
二叉查找树:
若左子树不空，则左子树上所有节点的值均小于它的根节点的值
若右子树不空，则右子树上所有节点的值均大于它的根节点的值
class Node {
constructor(key){
this.key = key;
this.left = null; // 左树
this.right = null;// 右树
}
}
class BinarySearchTree{
constructor(){
this.root = null;
}
insert(key){
const newNode = new Node(key);
const insertNode = (node,newNode)=>{
// 看下是放在左边还是右边
if(newNode.key < node.key){ // left
if(node.left == null){
node.left = newNode;
}else{ // 如果节点已经有了那么继续像当前节点插入
insertNode(node.left,newNode);
}
}else{ // right
if(node.right == null){
node.right = newNode;
}else{
insertNode(node.right,newNode);
}
}
}
if(!this.root){ // 如果根没有值 那么他就是根
this.root = newNode;
}else{ // 插到某一侧
insertNode(this.root,newNode)
}
}
}
let binaryTree = new BinarySearchTree();
binaryTree.insert(8);
binaryTree.insert(3);
binaryTree.insert(10);
七.图
图可以看成有关联的树,我们可以使用邻接表来描述各个节点的关系
image
class Graph{
constructor(){
this.List = {};
}
addNode(v){
this.List[v] = [];
}
addRelation(v,w){
// 相互存储关系
this.List[v].push(w);
this.List[w].push(v);
}
}
const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'].forEach(node => graph.addNode(node));
graph.addRelation('A', 'B')
graph.addRelation('A', 'C')
graph.addRelation('A', 'D')
console.log(graph.List['A']);
看到这里是不是对数据结构有了一定的认识啦！接下来就靠大家的合理应用啦~
觉得本文对你有帮助吗？请分享给更多人
关注「前端优选」加星标，提升前端技能
前端优选公众号.jpg
加我微信：webyouxuan
