摘要：前端必須要掌握常見的數(shù)據(jù)結(jié)構(gòu)，學(xué)會這招，讓你對開發(fā)中的數(shù)據(jù)結(jié)構(gòu)更加清晰一隊(duì)列像排隊(duì)一樣，隊(duì)列就是先進(jìn)先出，排隊(duì)入場入隊(duì)列出隊(duì)列二棧像拿起堆放的柴火一樣，棧就是先進(jìn)后出，離場時后進(jìn)的人先出入棧出棧三鏈表鏈表讓我們刪除數(shù)據(jù)和新增數(shù)據(jù)更加方便指針

像排隊(duì)一樣，隊(duì)列就是先進(jìn)先出，排隊(duì)入場！

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

像拿起堆放的柴火一樣，棧就是先進(jìn)后出，離場時后進(jìn)的人先出！

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

鏈表讓我們刪除數(shù)據(jù)和新增數(shù)據(jù)更加方便！

head指針指向第一個存入的元素節(jié)點(diǎn)，每個節(jié)點(diǎn)都有next屬性指向一下一個元素節(jié)點(diǎn)，最后一個元素的指針指向null

創(chuàng)建一個節(jié)點(diǎn)，每個節(jié)點(diǎn)的結(jié)構(gòu)非常簡單

class Node {
    constructor(element){
        this.element = element; // 每個節(jié)點(diǎn)保存的內(nèi)容
        this.next = null; // 保存的指針，指向下一個節(jié)點(diǎn)
    }
}

構(gòu)建鏈表

class LinkList {
    constructor(){
        this.head = null; // 表頭 默認(rèn)指向第一個節(jié)點(diǎn)，沒有為null
        this.length = 0;
    }
    append(element){
        // 追加節(jié)點(diǎn)
        const node = new Node(element);
        if(this.head == null){
            this.head = node; // 第一個節(jié)點(diǎn)就是表頭
        }else{
            let current = this.head;
            // 從第一個節(jié)點(diǎn)查找到最后一個節(jié)點(diǎn)
            while(current.next){
                current = current.next;
            }
            current.next = node; // 找到最后一個節(jié)點(diǎn)添加next指向新增節(jié)點(diǎn)
        }
        this.length++; // 每增加一個長度
    }
}

使用鏈表，不難看出鏈表的特點(diǎn)就是通過next來指向下一個節(jié)點(diǎn)（像鏈條一樣）

const ll = new LinkList();
ll.append(1);
ll.append(2);
console.log(ll); // head: Node { element: 1, next: Node { element: 2, next: null } }

實(shí)現(xiàn)鏈表的插入

insert(position,element){
    // 插入的時候判斷插入的位置
    if(position>=0 && position <=this.length){
        const node = new Node(element); // 創(chuàng)建一個節(jié)點(diǎn)
        if(position === 0){ // 如果位置是0
            node.next = this.head; // 那么就讓當(dāng)前節(jié)點(diǎn)變成頭
            this.head = node;
        }else{
            let current = this.head; // 獲取頭節(jié)點(diǎn)查找位置
            let previous = null;
            let index = 0;
            while(index++ < position){ // 查找到節(jié)點(diǎn)位置
                previous = current;
                current = current.next;
            }
            node.next = current; // 讓當(dāng)前節(jié)點(diǎn)next是剛才找到的節(jié)點(diǎn)
            previous.next = node; // 他的上一個節(jié)點(diǎn)的next是當(dāng)前節(jié)點(diǎn)
        }
        this.length++;
    }
}

實(shí)現(xiàn)鏈表的刪除

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){ // 找到要刪除的這一項(xiàng)，直接讓上一個指針指向下一個人
                  previous = current;
                  current = current.next
              }
              previous.next = current.next; // 上一個next直接指向下一個next
          }
          this.length--;
      }
  }

更新鏈表中的內(nèi)容

update(position,element) {
    if (position >= 0 && position < this.length) {
        if (position === 0) {
          // 根位置 直接更改跟的內(nèi)容即可
          this.head.element = element
        }else{
            let index = 0;
            // 查找到要修改的項(xiàng)來更新
            let current = this.head;
            while(index++ < position){
              current = current.next;
            }
            current.element = element;
        }
      }
  }

ES6已經(jīng)為我們提供了Set的api，但是在某些時候(瀏覽器不支持的情況下),我們還是需要自己來實(shí)現(xiàn)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){ // 刪除集合中的某一項(xiàng)
        if(this.has(value)){
            delete this.items[value];
        }
    }
}

集合，常見的方法有：交集、并集、差集

特點(diǎn)是查找速度快，但是存儲量需要手動擴(kuò)展

class HashTable{
    constructor(){
        this.table = [];
    }
    calcuteHash(key){ // 通過put的key 計算hash戳，存到數(shù)組中
        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"));

叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。

前端最常考察的就是二叉樹！

二叉樹: 樹中的節(jié)點(diǎn)最多只能有兩個子節(jié)點(diǎn)

二叉查找樹:
若左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值
若右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值

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{ // 如果節(jié)點(diǎn)已經(jīng)有了那么繼續(xù)像當(dāng)前節(jié)點(diǎn)插入
                    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{ // 插到某一側(cè)
            insertNode(this.root,newNode)
        }
    }
}
let binaryTree = new BinarySearchTree();
binaryTree.insert(8);
binaryTree.insert(3);
binaryTree.insert(10);

圖可以看成有關(guān)聯(lián)的樹,我們可以使用鄰接表來描述各個節(jié)點(diǎn)的關(guān)系

class Graph{
    constructor(){
        this.List = {};
    }
    addNode(v){
        this.List[v] = [];
    }
    addRelation(v,w){
        // 相互存儲關(guān)系
        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"]);

看到這里是不是對數(shù)據(jù)結(jié)構(gòu)有了一定的認(rèn)識啦！接下來就看大家的合理應(yīng)用啦~

覺得本文對你有幫助嗎？請分享給更多人
關(guān)注「前端優(yōu)選」加星標(biāo)，提升前端技能

加我微信：webyouxuan