定場詩 前言 本章為重讀《學習JavaScript數據結構與演算法》的系列文章，該章節主要講述數據結構 鏈表，以及實現鏈表的過程和原理。 鏈表 鏈表 ，為什麼要有這種數據結構呢？當然，事出必有因！ 數組 最常用、最方便的數據結構， But ，當我們從數組的起點或中間插入或移動項的成本很高，因為我們需要 ...
定場詩
傷情最是晚涼天，憔悴廝人不堪言；
邀酒摧腸三杯醉.尋香驚夢五更寒。
釵頭鳳斜卿有淚，荼蘼花了我無緣；
小樓寂寞新雨月.也難如鉤也難圓。前言
本章為重讀《學習JavaScript數據結構與演算法》的系列文章，該章節主要講述數據結構-鏈表，以及實現鏈表的過程和原理。
鏈表
鏈表，為什麼要有這種數據結構呢？當然，事出必有因！
數組-最常用、最方便的數據結構，But，當我們從數組的起點或中間插入或移動項的成本很高，因為我們需要移動數組元素。
鏈表，是存儲有序的元素集合。鏈表中的元素在記憶體中並不是連續放置的，每個元素由一個存儲自身的元素節點和一個指向下一個元素的引用(指針或鏈接)組成。
這個是重點，註意，圈起來，面試肯定考！
實現鏈表
我們要實現鏈表的結構以及對應的方法，大致為：元素插入、移除、獲取鏈表長度、查詢元素、是否為空等等...更詳細可看代碼實現邏輯。
數據結構越來越複雜嘍...註意領會精神...
/**
* Node 節點類，用於生成自身節點與下一個元素的引用
*/
class Node {
constructor(element) {
this.element = element
this.next = undefined
}
}
/**
* defaultEquals() 用於比較兩個非對象類的值是否相等
*/
function defaultEquals (a, b) {
return a === b
}
/**
* LinkedList 鏈表
* 特點：鏈表存儲有序的元素集合，但元素在記憶體中並不連續存放。每個元素有一個存儲元素本身的節點和一個指向下一個元素的引用
*/
class LinkedList {
constructor (equalsFn = defaultEquals) {
// 鏈表長度
this.count = 0
// 第一個元素引用
this.head = undefined
// 用於比較元素是否相等，預設為defaultEquals，允許傳入自定義的函數來比較兩個對象是否相等。
this.equalsFn = equalsFn
}
}註意：equalsFn參數，在比較對象類元素時，需要傳遞自定義方法來比較兩個對象的的值是否相等。
push()
向鏈表的尾部添加元素
/**
* push() 添加元素到鏈表
* @param {*} element 待添加的元素
*/
push (element) {
let node = new Node(element)
let current
// 判斷鏈表是否為空
if (this.head == null) {
this.head = node
} else {
// 查詢最後的元素 - 特點 current.next == null
current = this.head
while (current.next != null) {
current = current.next
}
// 將最後元素的下一個元素引用指向node
current.next = node
}
this.count++
} getElementAt()
獲取指定索引位置的元素
/**
* getElementAt() 返回索引位置元素
* @param {Number} index 索引位置
* @returns {*} node
*/
getElementAt (index) {
// 判斷索引是否有效
if (index < 0 || index > this.count) {
return undefined
}
let node = this.head
for (let i = 0; i < index && node != null; i++) {
node = node.next
}
return node
}insert()
在任意索引位置插入元素
/**
* insert() 在任意位置插入元素
* @param {*} element 待插入的元素
* @param {Number} index 指定的索引位置
* @returns {Boolean}
*/
insert (element, index) {
// 判斷是否為合法index
if (index < 0 || index > this.count) {
return false
}
// 實例化節點
let node = new Node(element)
// 插入-第一個位置
if (index === 0) {
let current = this.head
node.next = current
this.head = node
} else {
// 查找到指定索引位置的前一個元素
let previous = this.getElementAt(index - 1)
let current = previous.next
// 將上一個元素的next引用指向當前新添加的node，將node的next引用指向current，則完成插入
previous.next = node
node.next = current
}
// 鏈表長度+1
this.count++
return true
}removeAt()
移除指定索引位置的元素
實現邏輯：判斷是否為鏈表第一項，若為第一項，則將this.head指向第二個元素即可；如果不是第一項，則獲取索引index位置的上一位置索引元素previous，以及下一位置索引元素current.next，將previous.next指向current.next即可
/**
* removeAt() 移除指定位置的元素
* @param {Number} index
* @returns {*} element 移除的元素
*/
removeAt (index) {
// 判斷是否是合法索引
if (index < 0 || index > this.count) {
return undefined
}
let current = this.head
// 考慮是否是鏈表第一項
if (index === 0) {
this.head = current.next
} else {
// 方法一、 使用for迴圈迭代獲取指定索引位置的元素
// 用於獲取上一位置元素
// let previous
// for (let i = 0; i < index; i++) {
// previous = current
// current = current.next
// }
// // 跳過當前元素，將上一個元素的next指向下一個元素
// previous.next = current.next
// 方法二、藉助getElementAt()方法
// 查詢該索引位置的上一個元素
let previous = this.getElementAt(index - 1)
// 跳過中間元素，將上一個元素的next指向下一個元素
current = previous.next
previous.next = current.next
}
this.count--
return current.element
}indexOf()
查詢元素的索引位置
實現邏輯：迭代元素，比較每一個元素與目標元素是否相等；特別需要註意的是，對象類的值請傳入自定義的方法進行比較是否相等s
/**
* indexOf() 查詢元素的索引位置
* @param {*} element 待查詢的元素
* @returns {Number} index 索引位置，不存在則返回-1
*/
indexOf (element) {
let current = this.head
for (let i = 0; i < this.count && current != null; i++) {
// 判斷兩個元素是否相同
if (this.equalsFn(element, current.element)) {
return i
}
current = current.next
}
return - 1
}remove()
移除指定的元素
/**
* remove() 移除元素
* @param {*} element 待移除的元素
* @returns {*} element 移除的元素
*/
remove (element) {
// 獲取索引位置
let index = this.indexOf(element)
// 移除指定索引位置的元素
return this.removeAt(index)
}size()
獲取鏈表長度
/**
* size() 返回鏈表長度
* @returns {Number} 鏈表長度
*/
size () {
return this.count
}isEmpty()
判斷鏈表是否為空
/**
* isEmpty() 判斷鏈表是否為空
* @returns {Boolean}
*/
isEmpty () {
return this.count === 0
}getHead()
獲取鏈表首位元素
/**
* getHead() 獲取鏈表首位元素
* @returns {*}
*/
getHead () {
if (this.head != null) {
return this.head.element
}
return undefined
}clear()
清空鏈表
/**
* clear() 清空鏈表
*/
clear () {
this.count = 0
this.head = undefined
}toString()
鏈表字元串處理
/**
* toString() 鏈表字元串化展示
* @returns {String}
*/
toString () {
// 判斷是否為空
if (this.isEmpty()) {
return ''
}
let objStr = `${this.head.element}`
let current = this.head.next
for (let i = 1; i < this.count; i++) {
objStr = `${objStr},${current.element}`
current = current.next
}
return objStr
}使用鏈表
let linkedList = new LinkedList()
console.log(linkedList.isEmpty()) // true
// push 尾部壓入元素
linkedList.push(15)
linkedList.push(20)
/*
LinkedList {
count: 2,
head: Node {
element: 15,
next: Node {
element: 20,
next: undefined
}
},
equalsFn: [Function: defaultEquals]
}
*/
console.log(linkedList)
console.log(linkedList.isEmpty()) // false
// getElementAt() 指定索引位置的元素
let node = linkedList.getElementAt(1)
console.log(node)
// insert() 任意索引位置插入元素
linkedList.insert(22, 1)
linkedList.insert(33, 1)
console.log(linkedList.toString()) // 15,33,22,20
// removeAt() 移除指定索引位置的元素
console.log(linkedList.removeAt(1)) // 33
// remove() 移除元素
console.log(linkedList.remove(15)) // 15
console.log(linkedList.toString()) // 22,20
console.log(linkedList.getHead()) // 22
console.log(linkedList.size()) // 2
console.log(linkedList.toString()) // 22,20
console.log(linkedList.isEmpty()) // false
linkedList.clear()
console.log(linkedList.isEmpty()) // true再次強調下：如果鏈表中存儲的是對象類型值，請務必傳入指定的比較函數equalsFn自行進行比較，You should know why!
後記
以上就是胡哥今天給大家分享的內容，喜歡的小伙伴記得收藏、轉發、點擊右下角按鈕在看，推薦給更多小伙伴呦，歡迎多多留言交流...
胡哥有話說，一個有技術，有情懷的胡哥！京東開放平臺首席前端攻城獅。與你一起聊聊大前端，分享前端系統架構，框架實現原理，最新最高效的技術實踐！
長按掃碼關註，更帥更漂亮呦！關註胡哥有話說公眾號，可與胡哥繼續深入交流呦！
