日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

React前端解鏈表數(shù)據(jù)結(jié)構(gòu)示例詳解_React

作者：龍騎士尹道長 ? 更新時間： 2022-12-03 編程語言

什么是鏈表

在面試中只要被問到React Hooks就常被問到為什么Hooks不能在循環(huán)和條件判斷嵌套函數(shù)當(dāng)中使用；相信很多人都知道標(biāo)準(zhǔn)答案，【因為聲明的Hooks保存在鏈表當(dāng)中】，但是你真的知道鏈表嗎？

我們先看來看一個簡單的單向鏈表結(jié)構(gòu)

如上圖所示我們可以分析出，鏈表是由多個 node(節(jié)點) 組成的，而node(節(jié)點) 指向(保存)不同的內(nèi)存空間，每個node(節(jié)點) 由item(數(shù)據(jù)域) 和next(指針域) (雙向鏈表還包括prev指針域)構(gòu)成，其中item(數(shù)據(jù)域) 用于存儲數(shù)據(jù)，next(指針域) 指向下一個節(jié)點從而形成一個存儲數(shù)據(jù)的線性鏈路

總結(jié)：鏈表是一個用于存儲數(shù)據(jù)的無序線性數(shù)據(jù)結(jié)構(gòu)

而通過指針域指向鏈路的差異我們大致可以分為：

  • 單向鏈表
  • 雙向鏈表
  • 環(huán)形鏈表

鏈表與數(shù)組的比較

不知道鏈表這種數(shù)據(jù)結(jié)構(gòu)能否讓你想起數(shù)組，這兩種都是用于存儲數(shù)據(jù)的線性數(shù)據(jù)結(jié)構(gòu)，而不同的是鏈表是一種無序線性數(shù)據(jù)結(jié)構(gòu)，而數(shù)組是一種有序線性數(shù)據(jù)結(jié)構(gòu)，我們都知道數(shù)組是一種引用類型數(shù)據(jù)結(jié)構(gòu)，當(dāng)我們創(chuàng)建一個數(shù)組的時候會在內(nèi)存種開辟一串連續(xù)的內(nèi)存空間用于存儲，數(shù)組就是依靠這串連續(xù)的內(nèi)存空間來維持線性鏈路，而鏈表則是有一連串無序的內(nèi)存保存node(節(jié)點) 通過node(節(jié)點) 的指針域指向下一個節(jié)點來維持線性鏈路

鏈表有什么作用？

假設(shè)現(xiàn)在有一百條客戶的數(shù)據(jù)你需要對這一百條數(shù)據(jù)進行增、刪、插入你會怎么做？

創(chuàng)建一個數(shù)組將100條數(shù)據(jù)存入數(shù)組當(dāng)中，通過數(shù)組的push，splice，findIndex，indexOf等方法對數(shù)組進行操作，對于少量數(shù)據(jù)答案是顯而易見的，我們直接通過數(shù)組就能解決；但是如果現(xiàn)在有一百萬條數(shù)據(jù)讓你操作呢？我們已經(jīng)提到數(shù)組是通過連續(xù)內(nèi)存地址來維持線性鏈路的一種有序線性結(jié)構(gòu)，如果你在頭部插入一條數(shù)據(jù)的話則后面的一系列元素都要向后移動一位，一百萬條數(shù)據(jù)則要移動一百萬次，如果你要刪除第一萬個元素則后面的九十九萬個元素要向前移動一個位置，如果要將第一條數(shù)據(jù)替換為最后一條數(shù)據(jù)則要先刪除再插入先將第一條數(shù)據(jù)與最后一條數(shù)據(jù)取出其余所有數(shù)據(jù)要向前移動一個位(除頭部數(shù)據(jù)與尾部數(shù)據(jù))，然后再替換插入，所有數(shù)據(jù)再向后移動一位；在數(shù)據(jù)量龐大的情況下這絕對不是一個明智的方案，因為時間維度的不允許；但是如果換成鏈表你只需要操作node(節(jié)點) 指針域的指向便可以完成以上工作；

鏈表的優(yōu)缺點

優(yōu)點：相較于數(shù)組，鏈表操作更加的靈活，不受存儲空間的限制；

缺點：

  • 鏈表不能通過下標(biāo)獲取值，每次要獲取鏈表當(dāng)中的node(節(jié)點) 都需要經(jīng)過遍歷
  • 對于存儲基本類型的數(shù)據(jù)結(jié)構(gòu)因為需要通過指針域的指向則需要多分配一塊內(nèi)存進行存儲(雙向鏈表則乘以2)

通過JS簡單實現(xiàn)一個單向鏈表

而對于鏈表操作我們大致可以分為

  • 新增
  • 插入
  • 刪除
  • 查看
  • 修改

我們以單項鏈表為例依次實現(xiàn)他們

創(chuàng)建Node輔助類

我們已經(jīng)知道鏈表的大致概念也就是鏈表是一種以多個node(節(jié)點) 通過指針域連接的無序線性數(shù)據(jù)結(jié)構(gòu)，因此首先我們需要創(chuàng)建輔助類Node用于創(chuàng)建node(節(jié)點)

//輔助類Node用于創(chuàng)建保存在鏈表中的node
class Node {
    constructor (item) {
        //數(shù)據(jù)域，用于保存數(shù)據(jù)
        this.item = item
        //指針域，用于指向下一個節(jié)點
        this.next = null
    }
}

而在鏈表中始終有一個head屬性，這個屬性是鏈表的開端，用于存放整個鏈表的線性鏈路；我們還需要一個size用于保存鏈表的長度，用于遍歷鏈表；

//用于創(chuàng)建一個鏈表
class Linked{
    constructor () {
        //size屬性用于保存鏈表的長度用于遍歷
        this.size = 0
        //用于存放線性鏈路
        this.head = null
    }
}

至此我們已經(jīng)完成了創(chuàng)建一個鏈表的準(zhǔn)備工作；那么讓我們看看鏈表的基本操作方法是如何實現(xiàn)的

單向鏈表新增操作

對于單向鏈表新增如果當(dāng)前鏈表為空我們需要將鏈表的head屬性直接指向創(chuàng)建的node(節(jié)點)，如果鏈表不為空則我們需要將最末端的node(節(jié)點)的next(指針域) 指向新創(chuàng)建的 node(節(jié)點)

class Linked {
    constructor () {
        this.size = 0
        this.head = null
    }
    //新增node方法
    add (item) {
        //創(chuàng)建node
        let node = new Node (item)
        //this.head === null則代表鏈表為空需要將新head指向新創(chuàng)建的node
        if (this.head === null) {
            this.head = node
        } else {
            //查找需要創(chuàng)建的節(jié)點的上一個節(jié)點(最末端節(jié)點)
            let prevNode = this.getNode (this.size - 1)
            //將末端節(jié)點的next指向新創(chuàng)建的node
            prevNode.next = node
        }
        //新增成功則size+1
        this.size++
    }
    //節(jié)點查找方法傳入index類似于數(shù)組下標(biāo)用于標(biāo)記查找
    getNode (index) {
        //如果index < 0 || index >= this.size則說明下標(biāo)越界需要在此限制
        if (index < 0 || index >= this.size) {
            throw new Error ('out range')
        }
        //獲取第一個節(jié)點，從第一個節(jié)點進行遍歷
        let current = this.head;
        for (let i = 0; i < index; i++) {
            //依次將當(dāng)前節(jié)點指向下一個節(jié)點，直到獲取最后一個節(jié)點
            current = current.next
        }
        return current
    }
}

單向鏈表插入操作

對于單向鏈表插入操作如果需要插入的位置為下標(biāo)為0的位置(頭部)，我們需要將需要插入的node(節(jié)點) 的next(指向域),指向未改變之前的第一個node(節(jié)點)，也就是head，如果是中間追加則我們需要 將插入node（節(jié)點） 的指向域指向插入下標(biāo)的上一個節(jié)點的指向域(插入節(jié)點的下一個節(jié)點)，并將插入node(節(jié)點) 的上一個節(jié)點的指向域，指向當(dāng)前節(jié)點

class Linked {
    constructor () {
        this.size = 0
        this.head = null
    }
    //追加插入
    //position為插入位置下標(biāo)，item為需要保存到節(jié)點的元素
    insert (position, item) {
        //下標(biāo)值越位判斷
        if (position < 0 || position > this.size) {
            throw new Error ('Position out range');
        }
        //創(chuàng)建新節(jié)點
        let node = new Node (item)
        //頭部追加
        //如果插入下標(biāo)為0則直接將head指向新創(chuàng)建的節(jié)點
        if (position === 0) {
            node.next = this.head;
            this.head = node
        } else {//中間追加
            //獲取追加節(jié)點的上一個節(jié)點
            let prevNode = this.getNode (position - 1)
            //將插入下標(biāo)的指向域指向插入下標(biāo)的上一個節(jié)點的指向指向域(下一個節(jié)點)
            node.next = prevNode.next
            //將插入下標(biāo)的上一個節(jié)點的指向域，指向當(dāng)前節(jié)點
            prevNode.next = node
        }
        //插入成功，長度加一
        this.size++
    }
    getNode (index) {
        if (index < 0 || index >= this.size) {
            throw new Error ('out range')
        }
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next
        }
        return current
    }
}

單向鏈表刪除操作

對于單向鏈表的刪除操作，如果刪除元素為鏈表的頂端元素則需要將head指向被刪除元素的指針域（下一個元素），如果不是第一個元素則我們需要將上一個元素的指針域指向被刪除元素的next（指針域）（下一個元素）

class Linked {
    constructor () {
        this.size = 0
        this.head = null
    }
    delete (position) {
        //刪除下標(biāo)合法判斷
        if (position < 0 || position >= this.size) {
            throw new Error ('position out range')
        }
        //獲取當(dāng)前鏈表（head）
        let linkList = this.head
        //如果刪除的是鏈表的第一個元素則將head指向第一個元素的指針域（下一個元素）
        if (position === 0) {
            this.head = linkList.next;
        } else {//中間刪除
            //獲取刪除元素的上一個節(jié)點
            let prevNode = this.getNode (position - 1)
            //將鏈表指向被刪除元素上一個節(jié)點
            linkList = prevNode.next
            //將鏈表的的上一個節(jié)點指向被刪除元素的下一個節(jié)點
            prevNode.next = linkList.next
        }
        //長度減一
        this.size--
    }
    getNode (index) {
        if (index < 0 || index >= this.size) {
            throw new Error ('out range')
        }
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next
        }
        return current
    }
 }

單向鏈表查找操作

對于查找操作我們需要對鏈表進行遍歷比對獲取下標(biāo)

class Linked {
    constructor () {
        this.size = 0
        this.head = null
    }
    //查找指定元素下標(biāo)
    findIndex (item) {
        //獲取當(dāng)前鏈表
        let current  = this.head
        //進行遍歷操作依次比對獲取查找元素下標(biāo)
        for(let i=0;i<this.size;i++){
            if (current.item === item) {//如果current.item === item則說明該元素為需要查找的元素，返回下標(biāo)
                return i
            }
            //使聊表指向他的下一個元素，使循環(huán)可以繼續(xù)
           current = current.next
        }
        return null
    }
    getNode (index) {
        if (index < 0 || index >= this.size) {
            throw new Error ('out range')
        }
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next
        }
        return current
    }
}

單向鏈表修改操作

對于單向鏈表的修改操作我們只需用下標(biāo)獲取需要修改的元素，并對其item重新進行賦值即可；

class Linked {
    constructor () {
        this.size = 0
        this.head = null
    }
    getNode (index) {
        if (index < 0 || index >= this.size) {
            throw new Error ('out range')
        }
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next
        }
        return current
    }
    //修改操作
    //position為需要修改元素的下標(biāo),item為修改的值
    update(position,item){
        let current = this.getNode(position)
        current.item = item
    }
}

單向鏈表類方法整合

class Node {
    constructor (item) {
        this.item = item
        this.next = null
    }
}
class Linked {
    constructor () {
        this.size = 0
        this.head = null
    }
    add (item) {
        let node = new Node (item)
        if (this.head === null) {
            this.head = node
        } else {
            let current = this.getNode (this.size - 1)
            current.next = node
        }
        this.size++
    }
    //追加插入
    insert (position, item) {
        //下標(biāo)值越位判斷
        if (position < 0 || position > this.size) {
            throw new Error ('Position out range');
        }
        //創(chuàng)建新節(jié)點
        let node = new Node (item)
        //頭部追加
        //如果插入下標(biāo)為0則直接將head指向新創(chuàng)建的節(jié)點
        if (position === 0) {
            node.next = this.head;
            this.head = node
        } else {//中間追加
            let prevNode = this.getNode (position - 1)
            //將插入下標(biāo)的指向域指向插入下標(biāo)的上一個節(jié)點的指向指向域(下一個節(jié)點)
            node.next = prevNode.next
            //將插入下標(biāo)的上一個節(jié)點的指向域，指向當(dāng)前節(jié)點
            prevNode.next = node
        }
        //插入成功，長度加一
        this.size++
    }
    delete (position) {
        //刪除下標(biāo)合法判斷
        if (position < 0 || position >= this.size) {
            throw new Error ('position out range')
        }
        //獲取當(dāng)前鏈表（head）
        let linkList = this.head
        //如果刪除的是鏈表的第一個元素則將head指向第一個元素的指針域（下一個元素）
        if (position === 0) {
            this.head = linkList.next;
        } else {//中間刪除
            //獲取刪除元素的上一個節(jié)點
            let prevNode = this.getNode (position - 1)
            //將鏈表指向被刪除元素上一個節(jié)點
            linkList = prevNode.next
            //將鏈表的的上一個節(jié)點指向被刪除元素的下一個節(jié)點
            prevNode.next = linkList.next
        }
        //長度減一
        this.size--
    }
    //查找指定元素下標(biāo)
    findIndex (item) {
        //獲取當(dāng)前鏈表
        let current  = this.head
        //進行遍歷操作依次比對獲取查找元素下標(biāo)
        for(let i=0;i<this.size;i++){
            if (current.item === item) {//如果current.item === item則說明該元素為需要查找的元素，返回下標(biāo)
                return i
            }
            //使聊表指向他的下一個元素，使循環(huán)可以繼續(xù)
           current = current.next
        }
        return null
    }
    getNode (index) {
        if (index < 0 || index >= this.size) {
            throw new Error ('out range')
        }
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next
        }
        return current
    }
    //修改操作
    //position為需要修改元素的下標(biāo),item為修改的值
    update(position,item){
        let current = this.getNode(position)
        current.item = item
    }
}

寫在最后

對于鏈表的使用感受，我覺得我們不能將鏈表看成一個整體的數(shù)據(jù)結(jié)構(gòu)，而是要將它單元化，通過指針域來靈活的使用它。其實我更加傾向于將鏈表理解成一種設(shè)計思路，我們也沒必要將每個指針域命名為next，我們可以通過指針域的不同來構(gòu)建千變?nèi)f化的數(shù)據(jù)結(jié)構(gòu)，它也可以擁有不止一個指針域，如果我們添加一個prev指針指向上一個節(jié)點那么這個鏈表就是一個雙向鏈表，如果鏈表的最底層next指向的不是null而是當(dāng)前鏈表中任意一個節(jié)點，那么它就是一個環(huán)形鏈表；當(dāng)然我們也可以使一個節(jié)點擁有l(wèi)eft和right兩個指針域，指向不同的節(jié)點，那么它就是一個二叉樹，甚至我們可以用鏈表的指針域概念來實現(xiàn)一個優(yōu)先隊列，雖然在前端開發(fā)中鏈表的操作非常少，但是在閱讀源碼當(dāng)中我不止一次的看到鏈表這種數(shù)據(jù)結(jié)構(gòu)。說白了，這是一個無用的知識，因為你在開發(fā)當(dāng)中基本上用不到，但是鏈表的指針域概念卻能提升你的思維，讓你對數(shù)據(jù)結(jié)構(gòu)有更廣的思考；本來我是想再講講雙向鏈表與環(huán)形鏈表的，但是我實在不知道如何用文字表達(dá)用快慢指針來判斷環(huán)形鏈表中是否存在一個環(huán)，因此便沒有繼續(xù)；

原文鏈接：https://juejin.cn/post/7147339126692380709

欄目分類
最近更新