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

更新時(shí)間：2022年10月29日 14:14:30 作者：龍騎士尹道長

這篇文章主要為大家介紹了React前端解鏈表數(shù)據(jù)結(jié)構(gòu)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

什么是鏈表

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

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

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

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

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

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

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

不知道鏈表這種數(shù)據(jù)結(jié)構(gòu)能否讓你想起數(shù)組，這兩種都是用于存儲(chǔ)數(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)建一個(gè)數(shù)組的時(shí)候會(huì)在內(nèi)存種開辟一串連續(xù)的內(nèi)存空間用于存儲(chǔ)，數(shù)組就是依靠這串連續(xù)的內(nèi)存空間來維持線性鏈路，而鏈表則是有一連串無序的內(nèi)存保存node(節(jié)點(diǎn)) 通過node(節(jié)點(diǎn)) 的指針域指向下一個(gè)節(jié)點(diǎn)來維持線性鏈路

鏈表有什么作用？

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

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

鏈表的優(yōu)缺點(diǎn)

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

缺點(diǎn)：

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

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

而對(duì)于鏈表操作我們大致可以分為

新增
插入
刪除
查看
修改

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

創(chuàng)建Node輔助類

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

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

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

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

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

單向鏈表新增操作

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

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 {
            //查找需要?jiǎng)?chuàng)建的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)(最末端節(jié)點(diǎn))
            let prevNode = this.getNode (this.size - 1)
            //將末端節(jié)點(diǎn)的next指向新創(chuàng)建的node
            prevNode.next = node
        }
        //新增成功則size+1
        this.size++
    }
    //節(jié)點(diǎn)查找方法傳入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')
        }
        //獲取第一個(gè)節(jié)點(diǎn)，從第一個(gè)節(jié)點(diǎn)進(jìn)行遍歷
        let current = this.head;
        for (let i = 0; i < index; i++) {
            //依次將當(dāng)前節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)，直到獲取最后一個(gè)節(jié)點(diǎn)
            current = current.next
        }
        return current
    }
}

單向鏈表插入操作

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

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

單向鏈表刪除操作

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

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
        //如果刪除的是鏈表的第一個(gè)元素則將head指向第一個(gè)元素的指針域（下一個(gè)元素）
        if (position === 0) {
            this.head = linkList.next;
        } else {//中間刪除
            //獲取刪除元素的上一個(gè)節(jié)點(diǎn)
            let prevNode = this.getNode (position - 1)
            //將鏈表指向被刪除元素上一個(gè)節(jié)點(diǎn)
            linkList = prevNode.next
            //將鏈表的的上一個(gè)節(jié)點(diǎn)指向被刪除元素的下一個(gè)節(jié)點(diǎn)
            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
    }
 }

單向鏈表查找操作

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

class Linked {
    constructor () {
        this.size = 0
        this.head = null
    }
    //查找指定元素下標(biāo)
    findIndex (item) {
        //獲取當(dāng)前鏈表
        let current  = this.head
        //進(jìn)行遍歷操作依次比對(duì)獲取查找元素下標(biāo)
        for(let i=0;i<this.size;i++){
            if (current.item === item) {//如果current.item === item則說明該元素為需要查找的元素，返回下標(biāo)
                return i
            }
            //使聊表指向他的下一個(gè)元素，使循環(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
    }
}

單向鏈表修改操作

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

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é)點(diǎn)
        let node = new Node (item)
        //頭部追加
        //如果插入下標(biāo)為0則直接將head指向新創(chuàng)建的節(jié)點(diǎn)
        if (position === 0) {
            node.next = this.head;
            this.head = node
        } else {//中間追加
            let prevNode = this.getNode (position - 1)
            //將插入下標(biāo)的指向域指向插入下標(biāo)的上一個(gè)節(jié)點(diǎn)的指向指向域(下一個(gè)節(jié)點(diǎn))
            node.next = prevNode.next
            //將插入下標(biāo)的上一個(gè)節(jié)點(diǎn)的指向域，指向當(dāng)前節(jié)點(diǎn)
            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
        //如果刪除的是鏈表的第一個(gè)元素則將head指向第一個(gè)元素的指針域（下一個(gè)元素）
        if (position === 0) {
            this.head = linkList.next;
        } else {//中間刪除
            //獲取刪除元素的上一個(gè)節(jié)點(diǎn)
            let prevNode = this.getNode (position - 1)
            //將鏈表指向被刪除元素上一個(gè)節(jié)點(diǎn)
            linkList = prevNode.next
            //將鏈表的的上一個(gè)節(jié)點(diǎn)指向被刪除元素的下一個(gè)節(jié)點(diǎn)
            prevNode.next = linkList.next
        }
        //長度減一
        this.size--
    }
    //查找指定元素下標(biāo)
    findIndex (item) {
        //獲取當(dāng)前鏈表
        let current  = this.head
        //進(jìn)行遍歷操作依次比對(duì)獲取查找元素下標(biāo)
        for(let i=0;i<this.size;i++){
            if (current.item === item) {//如果current.item === item則說明該元素為需要查找的元素，返回下標(biāo)
                return i
            }
            //使聊表指向他的下一個(gè)元素，使循環(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
    }
}

寫在最后

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

以上就是React前端解鏈表數(shù)據(jù)結(jié)構(gòu)示例詳解的詳細(xì)內(nèi)容，更多關(guān)于React 解鏈表數(shù)據(jù)結(jié)構(gòu)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: