React前端解鏈表數據結構示例詳解
什麼是鏈表
在面試中隻要被問到React Hooks就常被問到為什麼Hooks不能在循環和條件判斷嵌套函數當中使用；相信很多人都知道標準答案，【因為聲明的Hooks保存在鏈表當中】，但是你真的知道鏈表嗎？
我們先看來看一個簡單的單向鏈表結構
如上圖所示我們可以分析出，鏈表是由多個 node(節點) 組成的，而node(節點) 指向(保存)不同的內存空間，每個node(節點) 由item(數據域) 和next(指針域) (雙向鏈表還包括prev指針域)構成，其中item(數據域) 用於存儲數據，next(指針域) 指向下一個節點從而形成一個存儲數據的線性鏈路
總結：鏈表是一個用於存儲數據的無序線性數據結構
而通過指針域指向鏈路的差異我們大致可以分為：
- 單向鏈表
- 雙向鏈表
- 環形鏈表
鏈表與數組的比較
不知道鏈表這種數據結構能否讓你想起數組，這兩種都是用於存儲數據的線性數據結構，而不同的是鏈表是一種無序線性數據結構，而數組是一種有序線性數據結構，我們都知道數組是一種引用類型數據結構，當我們創建一個數組的時候會在內存種開辟一串連續的內存空間用於存儲，數組就是依靠這串連續的內存空間來維持線性鏈路，而鏈表則是有一連串無序的內存保存node(節點) 通過node(節點) 的指針域指向下一個節點來維持線性鏈路
鏈表有什麼作用？
假設現在有一百條客戶的數據你需要對這一百條數據進行增、刪、插入你會怎麼做？
創建一個數組將100條數據存入數組當中，通過數組的push，splice，findIndex，indexOf等方法對數組進行操作，對於少量數據答案是顯而易見的，我們直接通過數組就能解決；但是如果現在有一百萬條數據讓你操作呢？我們已經提到數組是通過連續內存地址來維持線性鏈路的一種有序線性結構，如果你在頭部插入一條數據的話則後面的一系列元素都要向後移動一位，一百萬條數據則要移動一百萬次，如果你要刪除第一萬個元素則後面的九十九萬個元素要向前移動一個位置，如果要將第一條數據替換為最後一條數據則要先刪除再插入先將第一條數據與最後一條數據取出其餘所有數據要向前移動一個位(除頭部數據與尾部數據)，然後再替換插入，所有數據再向後移動一位；在數據量龐大的情況下這絕對不是一個明智的方案，因為時間維度的不允許；但是如果換成鏈表你隻需要操作node(節點) 指針域的指向便可以完成以上工作；
鏈表的優缺點
優點：相較於數組，鏈表操作更加的靈活，不受存儲空間的限制；
缺點：
- 鏈表不能通過下標獲取值，每次要獲取鏈表當中的node(節點) 都需要經過遍歷
- 對於存儲基本類型的數據結構因為需要通過指針域的指向則需要多分配一塊內存進行存儲(雙向鏈表則乘以2)
通過JS簡單實現一個單向鏈表
而對於鏈表操作我們大致可以分為
- 新增
- 插入
- 刪除
- 查看
- 修改
我們以單項鏈表為例依次實現他們
創建Node輔助類
我們已經知道鏈表的大致概念也就是鏈表是一種以多個node(節點) 通過指針域連接的無序線性數據結構，因此首先我們需要創建輔助類Node用於創建node(節點)
//輔助類Node用於創建保存在鏈表中的node
class Node {
constructor (item) {
//數據域，用於保存數據
this.item = item
//指針域，用於指向下一個節點
this.next = null
}
}
而在鏈表中始終有一個head屬性，這個屬性是鏈表的開端，用於存放整個鏈表的線性鏈路；我們還需要一個size用於保存鏈表的長度，用於遍歷鏈表；
//用於創建一個鏈表
class Linked{
constructor () {
//size屬性用於保存鏈表的長度用於遍歷
this.size = 0
//用於存放線性鏈路
this.head = null
}
}
至此我們已經完成瞭創建一個鏈表的準備工作；那麼讓我們看看鏈表的基本操作方法是如何實現的
單向鏈表新增操作
對於單向鏈表新增如果當前鏈表為空我們需要將鏈表的head屬性直接指向創建的node(節點)，如果鏈表不為空則我們需要將最末端的node(節點)的next(指針域) 指向新創建的 node(節點)
class Linked {
constructor () {
this.size = 0
this.head = null
}
//新增node方法
add (item) {
//創建node
let node = new Node (item)
//this.head === null則代表鏈表為空需要將新head指向新創建的node
if (this.head === null) {
this.head = node
} else {
//查找需要創建的節點的上一個節點(最末端節點)
let prevNode = this.getNode (this.size - 1)
//將末端節點的next指向新創建的node
prevNode.next = node
}
//新增成功則size+1
this.size++
}
//節點查找方法傳入index類似於數組下標用於標記查找
getNode (index) {
//如果index < 0 || index >= this.size則說明下標越界需要在此限制
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
}
}
單向鏈表插入操作
對於單向鏈表插入操作如果需要插入的位置為下標為0的位置(頭部)，我們需要將需要插入的node(節點) 的next(指向域),指向未改變之前的第一個node(節點)，也就是head，如果是中間追加則我們需要 將插入node（節點） 的指向域指向插入下標的上一個節點的指向域(插入節點的下一個節點)，並將插入node(節點) 的上一個節點的指向域，指向當前節點
class Linked {
constructor () {
this.size = 0
this.head = null
}
//追加插入
//position為插入位置下標，item為需要保存到節點的元素
insert (position, item) {
//下標值越位判斷
if (position < 0 || position > this.size) {
throw new Error ('Position out range');
}
//創建新節點
let node = new Node (item)
//頭部追加
//如果插入下標為0則直接將head指向新創建的節點
if (position === 0) {
node.next = this.head;
this.head = node
} else {//中間追加
//獲取追加節點的上一個節點
let prevNode = this.getNode (position - 1)
//將插入下標的指向域指向插入下標的上一個節點的指向指向域(下一個節點)
node.next = prevNode.next
//將插入下標的上一個節點的指向域，指向當前節點
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 {//中間刪除
//獲取刪除元素的上一個節點
let prevNode = this.getNode (position - 1)
//將鏈表指向被刪除元素上一個節點
linkList = prevNode.next
//將鏈表的的上一個節點指向被刪除元素的下一個節點
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
}
//使聊表指向他的下一個元素，使循環可以繼續
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');
}
//創建新節點
let node = new Node (item)
//頭部追加
//如果插入下標為0則直接將head指向新創建的節點
if (position === 0) {
node.next = this.head;
this.head = node
} else {//中間追加
let prevNode = this.getNode (position - 1)
//將插入下標的指向域指向插入下標的上一個節點的指向指向域(下一個節點)
node.next = prevNode.next
//將插入下標的上一個節點的指向域，指向當前節點
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 {//中間刪除
//獲取刪除元素的上一個節點
let prevNode = this.getNode (position - 1)
//將鏈表指向被刪除元素上一個節點
linkList = prevNode.next
//將鏈表的的上一個節點指向被刪除元素的下一個節點
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
}
//使聊表指向他的下一個元素，使循環可以繼續
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指針指向上一個節點那麼這個鏈表就是一個雙向鏈表，如果鏈表的最底層next指向的不是null而是當前鏈表中任意一個節點，那麼它就是一個環形鏈表；當然我們也可以使一個節點擁有left和right兩個指針域，指向不同的節點，那麼它就是一個二叉樹，甚至我們可以用鏈表的指針域概念來實現一個優先隊列，雖然在前端開發中鏈表的操作非常少，但是在閱讀源碼當中我不止一次的看到鏈表這種數據結構。說白瞭，這是一個無用的知識，因為你在開發當中基本上用不到，但是鏈表的指針域概念卻能提升你的思維，讓你對數據結構有更廣的思考；本來我是想再講講雙向鏈表與環形鏈表的，但是我實在不知道如何用文字表達用快慢指針來判斷環形鏈表中是否存在一個環，因此便沒有繼續；
以上就是React前端解鏈表數據結構示例詳解的詳細內容，更多關於React 解鏈表數據結構的資料請關註WalkonNet其它相關文章！