React前端解鏈表數據結構示例詳解
什么是鏈表
在面試中只要被問到React Hooks就常被問到為什么Hooks不能在循環(huán)和條件判斷嵌套函數當中使用；相信很多人都知道標準答案，【因為聲明的Hooks保存在鏈表當中】，但是你真的知道鏈表嗎？
我們先看來看一個簡單的單向鏈表結構
如上圖所示我們可以分析出，鏈表是由多個 node(節(jié)點) 組成的，而node(節(jié)點) 指向(保存)不同的內存空間，每個node(節(jié)點) 由item(數據域) 和next(指針域) (雙向鏈表還包括prev指針域)構成，其中item(數據域) 用于存儲數據，next(指針域) 指向下一個節(jié)點從而形成一個存儲數據的線性鏈路
總結：鏈表是一個用于存儲數據的無序線性數據結構
而通過指針域指向鏈路的差異我們大致可以分為：
- 單向鏈表
- 雙向鏈表
- 環(huán)形鏈表
鏈表與數組的比較
不知道鏈表這種數據結構能否讓你想起數組，這兩種都是用于存儲數據的線性數據結構，而不同的是鏈表是一種無序線性數據結構，而數組是一種有序線性數據結構，我們都知道數組是一種引用類型數據結構，當我們創(chuàng)建一個數組的時候會在內存種開辟一串連續(xù)的內存空間用于存儲，數組就是依靠這串連續(xù)的內存空間來維持線性鏈路，而鏈表則是有一連串無序的內存保存node(節(jié)點) 通過node(節(jié)點) 的指針域指向下一個節(jié)點來維持線性鏈路
鏈表有什么作用？
假設現在有一百條客戶的數據你需要對這一百條數據進行增、刪、插入你會怎么做？
創(chuàng)建一個數組將100條數據存入數組當中，通過數組的push，splice，findIndex，indexOf等方法對數組進行操作，對于少量數據答案是顯而易見的，我們直接通過數組就能解決；但是如果現在有一百萬條數據讓你操作呢？我們已經提到數組是通過連續(xù)內存地址來維持線性鏈路的一種有序線性結構，如果你在頭部插入一條數據的話則后面的一系列元素都要向后移動一位，一百萬條數據則要移動一百萬次，如果你要刪除第一萬個元素則后面的九十九萬個元素要向前移動一個位置，如果要將第一條數據替換為最后一條數據則要先刪除再插入先將第一條數據與最后一條數據取出其余所有數據要向前移動一個位(除頭部數據與尾部數據)，然后再替換插入，所有數據再向后移動一位；在數據量龐大的情況下這絕對不是一個明智的方案，因為時間維度的不允許；但是如果換成鏈表你只需要操作node(節(jié)點) 指針域的指向便可以完成以上工作；
鏈表的優(yōu)缺點
優(yōu)點：相較于數組，鏈表操作更加的靈活，不受存儲空間的限制；
缺點：
- 鏈表不能通過下標獲取值，每次要獲取鏈表當中的node(節(jié)點) 都需要經過遍歷
- 對于存儲基本類型的數據結構因為需要通過指針域的指向則需要多分配一塊內存進行存儲(雙向鏈表則乘以2)
通過JS簡單實現一個單向鏈表
而對于鏈表操作我們大致可以分為
- 新增
- 插入
- 刪除
- 查看
- 修改
我們以單項鏈表為例依次實現他們
創(chuàng)建Node輔助類
我們已經知道鏈表的大致概念也就是鏈表是一種以多個node(節(jié)點) 通過指針域連接的無序線性數據結構，因此首先我們需要創(chuàng)建輔助類Node用于創(chuàng)建node(節(jié)點)
//輔助類Node用于創(chuàng)建保存在鏈表中的node
class Node {
constructor (item) {
//數據域，用于保存數據
this.item = item
//指針域，用于指向下一個節(jié)點
this.next = null
}
}
而在鏈表中始終有一個head屬性，這個屬性是鏈表的開端，用于存放整個鏈表的線性鏈路；我們還需要一個size用于保存鏈表的長度，用于遍歷鏈表；
//用于創(chuàng)建一個鏈表
class Linked{
constructor () {
//size屬性用于保存鏈表的長度用于遍歷
this.size = 0
//用于存放線性鏈路
this.head = null
}
}
至此我們已經完成了創(chuà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類似于數組下標用于標記查找
getNode (index) {
//如果index < 0 || index >= this.size則說明下標越界需要在此限制
if (index < 0 || index >= this.size) {
throw new Error ('out range')
}
//獲取第一個節(jié)點，從第一個節(jié)點進行遍歷
let current = this.head;
for (let i = 0; i < index; i++) {
//依次將當前節(jié)點指向下一個節(jié)點，直到獲取最后一個節(jié)點
current = current.next
}
return current
}
}
單向鏈表插入操作
對于單向鏈表插入操作如果需要插入的位置為下標為0的位置(頭部)，我們需要將需要插入的node(節(jié)點) 的next(指向域),指向未改變之前的第一個node(節(jié)點)，也就是head，如果是中間追加則我們需要 將插入node（節(jié)點） 的指向域指向插入下標的上一個節(jié)點的指向域(插入節(jié)點的下一個節(jié)點)，并將插入node(節(jié)點) 的上一個節(jié)點的指向域，指向當前節(jié)點
class Linked {
constructor () {
this.size = 0
this.head = null
}
//追加插入
//position為插入位置下標，item為需要保存到節(jié)點的元素
insert (position, item) {
//下標值越位判斷
if (position < 0 || position > this.size) {
throw new Error ('Position out range');
}
//創(chuàng)建新節(jié)點
let node = new Node (item)
//頭部追加
//如果插入下標為0則直接將head指向新創(chuàng)建的節(jié)點
if (position === 0) {
node.next = this.head;
this.head = node
} else {//中間追加
//獲取追加節(jié)點的上一個節(jié)點
let prevNode = this.getNode (position - 1)
//將插入下標的指向域指向插入下標的上一個節(jié)點的指向指向域(下一個節(jié)點)
node.next = prevNode.next
//將插入下標的上一個節(jié)點的指向域，指向當前節(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) {
//刪除下標合法判斷
if (position < 0 || position >= this.size) {
throw new Error ('position out range')
}
//獲取當前鏈表（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
}
}
單向鏈表查找操作
對于查找操作我們需要對鏈表進行遍歷比對獲取下標
class Linked {
constructor () {
this.size = 0
this.head = null
}
//查找指定元素下標
findIndex (item) {
//獲取當前鏈表
let current = this.head
//進行遍歷操作依次比對獲取查找元素下標
for(let i=0;i<this.size;i++){
if (current.item === item) {//如果current.item === item則說明該元素為需要查找的元素，返回下標
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
}
}
單向鏈表修改操作
對于單向鏈表的修改操作我們只需用下標獲取需要修改的元素，并對其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為需要修改元素的下標,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) {
//下標值越位判斷
if (position < 0 || position > this.size) {
throw new Error ('Position out range');
}
//創(chuàng)建新節(jié)點
let node = new Node (item)
//頭部追加
//如果插入下標為0則直接將head指向新創(chuàng)建的節(jié)點
if (position === 0) {
node.next = this.head;
this.head = node
} else {//中間追加
let prevNode = this.getNode (position - 1)
//將插入下標的指向域指向插入下標的上一個節(jié)點的指向指向域(下一個節(jié)點)
node.next = prevNode.next
//將插入下標的上一個節(jié)點的指向域，指向當前節(jié)點
prevNode.next = node
}
//插入成功，長度加一
this.size++
}
delete (position) {
//刪除下標合法判斷
if (position < 0 || position >= this.size) {
throw new Error ('position out range')
}
//獲取當前鏈表（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--
}
//查找指定元素下標
findIndex (item) {
//獲取當前鏈表
let current = this.head
//進行遍歷操作依次比對獲取查找元素下標
for(let i=0;i<this.size;i++){
if (current.item === item) {//如果current.item === item則說明該元素為需要查找的元素，返回下標
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為需要修改元素的下標,item為修改的值
update(position,item){
let current = this.getNode(position)
current.item = item
}
}
寫在最后
對于鏈表的使用感受，我覺得我們不能將鏈表看成一個整體的數據結構，而是要將它單元化，通過指針域來靈活的使用它。其實我更加傾向于將鏈表理解成一種設計思路，我們也沒必要將每個指針域命名為next，我們可以通過指針域的不同來構建千變萬化的數據結構，它也可以擁有不止一個指針域，如果我們添加一個prev指針指向上一個節(jié)點那么這個鏈表就是一個雙向鏈表，如果鏈表的最底層next指向的不是null而是當前鏈表中任意一個節(jié)點，那么它就是一個環(huán)形鏈表；當然我們也可以使一個節(jié)點擁有l(wèi)eft和right兩個指針域，指向不同的節(jié)點，那么它就是一個二叉樹，甚至我們可以用鏈表的指針域概念來實現一個優(yōu)先隊列，雖然在前端開發(fā)中鏈表的操作非常少，但是在閱讀源碼當中我不止一次的看到鏈表這種數據結構。說白了，這是一個無用的知識，因為你在開發(fā)當中基本上用不到，但是鏈表的指針域概念卻能提升你的思維，讓你對數據結構有更廣的思考；本來我是想再講講雙向鏈表與環(huán)形鏈表的，但是我實在不知道如何用文字表達用快慢指針來判斷環(huán)形鏈表中是否存在一個環(huán)，因此便沒有繼續(xù)；
以上就是React前端解鏈表數據結構示例詳解的詳細內容，更多關于React 解鏈表數據結構的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了react中路由和按需加載的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
這篇文章主要為大家介紹了react-router?重新加回跳轉攔截功能詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-02-02
Redux是JavaScript狀態(tài)容器，提供可預測化的狀態(tài)管理，今天通過本文給大家分享redux在react中使用及配置redux到react項目中的方法，感興趣的朋友跟隨小編一起看看吧2021-06-06
mobx是一個輕量級的狀態(tài)管理器,所以很簡單(單一全局數據使用class)類有get 數據方法,本文通過示例代碼介紹react mobx 基本用法,感興趣的朋友有一起看看2023-11-11
React??memo允許你的組件在?props?沒有改變的情況下跳過重新渲染的問題記錄
使用?memo?將組件包裝起來,以獲得該組件的一個?記憶化?版本,只要該組件的?props?沒有改變,這個記憶化版本就不會在其父組件重新渲染時重新渲染,這篇文章主要介紹了React??memo允許你的組件在?props?沒有改變的情況下跳過重新渲染,需要的朋友可以參考下2024-06-06
這篇文章主要為大家介紹了React初始化渲染過程示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
這篇文章主要介紹了React項目動態(tài)設置title標題的方法示例，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-09-09
這篇文章主要介紹了react中引入less并支持antd主題換膚方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
react16+antd4 RangePicker組件實現時間禁選示例
這篇文章主要為大家介紹了react16+antd4 RangePicker 時間禁選示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-05-05
雖然一直有做react相關的優(yōu)化,按需加載、dll 分離、服務端渲染,但是從來沒有從路由代碼分割這一塊入手過,所以下面這篇文章主要給大家介紹了關于React中代碼分割的方式,需要的朋友可以參考下2022-12-12