網站首頁 編程語言 正文
什么是鏈表
在面試中只要被問到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兩個指針域，指向不同的節點，那么它就是一個二叉樹，甚至我們可以用鏈表的指針域概念來實現一個優先隊列，雖然在前端開發中鏈表的操作非常少，但是在閱讀源碼當中我不止一次的看到鏈表這種數據結構。說白了，這是一個無用的知識，因為你在開發當中基本上用不到，但是鏈表的指針域概念卻能提升你的思維，讓你對數據結構有更廣的思考；本來我是想再講講雙向鏈表與環形鏈表的，但是我實在不知道如何用文字表達用快慢指針來判斷環形鏈表中是否存在一個環，因此便沒有繼續；
原文鏈接：https://juejin.cn/post/7147339126692380709
相關推薦
- 2022-06-22 Android開發保存QQ密碼功能_Android
- 2023-04-22 GO的range如何使用詳解_Golang
- 2022-08-20 C#?Chart折線圖使用鼠標滾輪放大、縮小和平移曲線方式_C#教程
- 2022-03-28 Easyx實現窗口自動碰撞的小球_C 語言
- 2022-07-11 Verilog中$display和$write任務以及格式化輸出
- 2022-04-22 Error:Module “./antd/es/badge/style“ does not exis
- 2022-06-02 Go語言中定時任務庫Cron使用方法介紹_Golang
- 2022-10-30 數據庫加密字段進行模糊查詢詳解_數據庫其它
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速