资讯专栏INFORMATION COLUMN

前端不得不说的数据结构

netmou / 1951人阅读

摘要:前端必须要掌握常见的数据结构,学会这招,让你对开发中的数据结构更加清晰一队列像排队一样,队列就是先进先出,排队入场入队列出队列二栈像拿起堆放的柴火一样,栈就是先进后出,离场时后进的人先出入栈出栈三链表链表让我们删除数据和新增数据更加方便指针

前端必须要掌握常见的数据结构,学会这招,让你对开发中的数据结构更加清晰! 一.队列

像排队一样,队列就是先进先出,排队入场!

class Queue {
    constructor() {
        this.arr = []
    }
    enqueue(element){ // 入队列
        this.arr.push(element)
    }
    dequeue(){ // 出队列
        return this.items.shift()
    }
}
二.栈

像拿起堆放的柴火一样,栈就是先进后出,离场时后进的人先出!

class Stack {
    constructor(){
        this.arr = [];
    }
    push(element){ // 入栈
        this.arr.push(element);
    }
    pop() { // 出栈
        return this.items.pop();
    }
}
三.链表

链表让我们删除数据和新增数据更加方便!

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表

特点是查找速度快,但是存储量需要手动扩展

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"));
六.树

叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

前端最常考察的就是二叉树!

二叉树: 树中的节点最多只能有两个子节点

二叉查找树:
若左子树不空,则左子树上所有节点的值均小于它的根节点的值
若右子树不空,则右子树上所有节点的值均大于它的根节点的值

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);
七.图

图可以看成有关联的树,我们可以使用邻接表来描述各个节点的关系

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"]);

看到这里是不是对数据结构有了一定的认识啦!接下来就看大家的合理应用啦~

觉得本文对你有帮助吗?请分享给更多人
关注「前端优选」加星标,提升前端技能

加我微信:webyouxuan

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/116335.html

相关文章

  • node实现文件下载不得不说那些事儿

    摘要:如果像本例中这样的场景会遇到这样一个问题,详见链接当请求参数过长或为了安全,就需要用到下载。写到这里自己都忍不住想锤自己,给自己挖坑不说,这样来回请求下载,流量,真的是败家。 这几天一直在做远程文件下载的事,现在总算有了解决,特来记录一下踩过的坑和想揍自己的心 需求 应用场景是这样的,底层逻辑数据请求接口是由Java写的,也就是说原始文件存在Java服务端,返回时有加密措施 由于工作...

    Coly 评论0 收藏0
  • node实现文件下载不得不说那些事儿

    摘要:如果像本例中这样的场景会遇到这样一个问题,详见链接当请求参数过长或为了安全,就需要用到下载。写到这里自己都忍不住想锤自己,给自己挖坑不说,这样来回请求下载,流量,真的是败家。 这几天一直在做远程文件下载的事,现在总算有了解决,特来记录一下踩过的坑和想揍自己的心 需求 应用场景是这样的,底层逻辑数据请求接口是由Java写的,也就是说原始文件存在Java服务端,返回时有加密措施 由于工作...

    AnthonyHan 评论0 收藏0
  • nginx限速不得不说事之连接数限制技巧

    摘要:但是,你的连接数限制配置为允许单个连接数,单个连接数最大带宽为。就降低单个连接数带宽吧要知道大家谁没事会用浏览器自带下载器下载呢注本文只探讨限速模块在不同业务下的限速彩蛋偶尔发现,将连接数限制为迅雷不能高速下载了。 nginx 内置模块限速怎么使用就不多说了,今天来说说连接数和单个连接数限速的事。 场景:A公司有100人,A公司只有一个公网IP,假设A公司可能有100个人同时在下载你的...

    neroneroffy 评论0 收藏0
  • nginx限速不得不说事之连接数限制技巧

    摘要:但是,你的连接数限制配置为允许单个连接数,单个连接数最大带宽为。就降低单个连接数带宽吧要知道大家谁没事会用浏览器自带下载器下载呢注本文只探讨限速模块在不同业务下的限速彩蛋偶尔发现,将连接数限制为迅雷不能高速下载了。 nginx 内置模块限速怎么使用就不多说了,今天来说说连接数和单个连接数限速的事。 场景:A公司有100人,A公司只有一个公网IP,假设A公司可能有100个人同时在下载你的...

    remcarpediem 评论0 收藏0
  • JavaScript数据类型和他背后不得不说故事

    摘要:基本概念中有种简单数据类型也称为基本数据类型,存放在栈中和。在使用声明变量但未对其加以初始化时,这个变量的值就是,例如类型是第二个只有一个值的数据类型,这个特殊的值是。类型阿拉伯数字的八进制十进制十六进制整数浮点数。 基本概念 ECMAScript 中有 5 种简单数据类型(也称为基本数据类型,存放在栈中):Undefined、Null、Boolean、Number 和String。还...

    ASCH 评论0 收藏0

发表评论

0条评论

netmou

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<