如何用JavaScript實現(xiàn)功能齊全的單鏈表詳解
更新時間：2019年02月11日 10:47:35 作者：王文健
這篇文章主要給大家介紹了關于如何用JavaScript實現(xiàn)功能齊全的單鏈表的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧
前言
前端也要搞好數(shù)據(jù)結(jié)構(gòu)哦！
用JavaScript實現(xiàn)了個單鏈表，通過LinkedList構(gòu)造函數(shù)可實例化一個單鏈表數(shù)據(jù)結(jié)構(gòu)的對象，所有的方法放到LinkedList構(gòu)造函數(shù)的原型對象上，寫了暫時能想到的所有方法
實現(xiàn)
- 通過LinkedList的類創(chuàng)建鏈表實例，鏈表下有添加，查找，刪除，顯示節(jié)點等方法
- 鏈表初始默認有一個"_head"頭部節(jié)點，使用時隱藏
- 按元素/索引 添加、刪除，未找到時返回錯誤，查找未找到時返回null或-1
- let obj = new LinkedList()
方法介紹
查找
obj.find(item)通過item元素內(nèi)容查找到該元素obj.findIndex(index)通過index索引查找到該元素obj.findIndexOf(item)通過item元素內(nèi)容查找到該元素索引obj.findPrev(item)通過item元素查找上一個節(jié)點元素
添加
obj.insert(item,newElement)在item元素后插入新元素obj.push(item)在鏈表末尾插入item元素obj.insertIndex(index,newElement)在index索引處插入新元素
刪除
obj.remove(item)刪除item元素obj.removeIndex(index)刪除index索引處節(jié)點
其他
obj.size()返回該鏈表的長度obj.display()數(shù)組形式返回該鏈表，便于觀察，測試obj.reversal()鏈表順序反轉(zhuǎn)（遞歸）
方法代碼
鏈表類LinkedList
function LinkedList (...rest) {
this._head = new Node('_head') // 鏈表頭節(jié)點
// 如果new時有傳進值，則添加到實例中
if (rest.length) {
this.insert(rest[0], '_head')
for (let i = 1; i < rest.length; i++) {
this.insert(rest[i], rest[i - 1])
}
}
}
LinkedList.prototype.find = find
LinkedList.prototype.findPrev = findPrev
LinkedList.prototype.findIndex = findIndex
LinkedList.prototype.findIndexOf = findIndexOf
LinkedList.prototype.push = push
LinkedList.prototype.insert = insert
LinkedList.prototype.insertIndex = insertIndex
LinkedList.prototype.remove = remove
LinkedList.prototype.removeIndex = removeIndex
LinkedList.prototype.size = size
LinkedList.prototype.display = display
LinkedList.prototype.reversal = reversal
創(chuàng)建新節(jié)點類Node
function Node (element) {
this.element = element
this.next = null
}
obj.find(item)
// 查找函數(shù)，在鏈表中查找item的位置，并把它返回，未找到返回-1
function find (item) {
let currNode = this._head
while (currNode !== null && currNode.element !== item) {
currNode = currNode.next
}
if (currNode !== null) {
return currNode
} else {
return null
}
}
obj.findIndex(index)
// 通過元素的索引返回該元素
function findIndex (index) {
let currNode = this._head
let tmpIndex = 0
while (currNode !== null) {
// 找到該index位置，返回當前節(jié)點，出去頭結(jié)點
if (tmpIndex === index + 1) {
return currNode
}
tmpIndex += 1
currNode = currNode.next
}
return null
}
obj.findIndexOf(item)
function findIndexOf (item) {
let currNode = this._head
let tmpIndex = 0
while (currNode.next !== null && currNode.next.element !== item) {
tmpIndex += 1
currNode = currNode.next
}
if (currNode !== null) {
return tmpIndex
} else {
return -1
}
}
obj.findPrev(item)
// 尋找目標節(jié)點item的上一個節(jié)點，未找到返回-1
function findPrev (item) {
let currNode = this._head
while (currNode.next !== null && currNode.next.element !== item) {
currNode = currNode.next
}
if (currNode.next !== item) {
return currNode
} else {
return null
}
}
obj.insert(item,newElement)
// 插入節(jié)點，找到要插入到的item的節(jié)點位置，把新節(jié)點插到item后面
function insert (newElement, item) {
let newNode = new Node(newElement)
let currNode = this.find(item)
if (currNode) {
newNode.next = currNode.next
currNode.next = newNode
} else {
console.error(`insert error：鏈表中不存在「${item}」節(jié)點`)
}
}
obj.insertIndex(index,newElement)
// 插入節(jié)點，新節(jié)點插到index索引下
function insertIndex (newElement, index) {
let newNode = new Node(newElement)
let currNode = this.findIndex(index)
if (currNode) {
newNode.next = currNode.next
currNode.next = newNode
} else {
console.error(`insertIndex error：鏈表中不存在「${index}」索引節(jié)點`)
}
}
obj.push(item)
// 在鏈表最后一位添加元素
function push (element) {
let newNode = new Node(element)
let currNode = this._head
while (currNode.next !== null) {
currNode = currNode.next
}
currNode.next = newNode
}
obj.remove(item)
// 刪除節(jié)點，找到刪除的位置，刪除，未找到提示錯誤
function remove (item) {
// 找到當前和上一個節(jié)點，讓上一個節(jié)點的next指向item下一個節(jié)點
let tmpPrev = this.findPrev(item)
let tmpNext = this.find(item)
if (tmpPrev && tmpNext) {
tmpPrev.next = tmpNext.next
} else {
console.error(`remove error：鏈表中不存在「${item}」節(jié)點`)
}
}
obj.removeIndex(index)
// 刪除某個索引下的節(jié)點
function removeIndex (index) {
let tmpPrev = this.findIndex(index - 1)
let currNode = this.findIndex(index)
if (tmpPrev && currNode) {
tmpPrev.next = currNode.next
} else {
console.error(`removeIndex error：鏈表中不存在「${index}」索引節(jié)點`)
}
}
obj.size()
function size () {
let currNode = this._head
let tmpSize = 0
while (currNode.next !== null) {
tmpSize += 1
currNode = currNode.next
}
return tmpSize // 不計算頭部節(jié)點
}
obj.reversal()
// 鏈表反轉(zhuǎn)=>遞歸
function reversal () {
function reversalList (item) {
if (item.next) {
let tmpItem = reversalList(item.next)
item.next = null
tmpItem.next = item
return item
} else {
obj._head.next = item
return item
}
}
reversalList(obj._head.next)
}
obj.display()
function display () {
// 鏈表展示和使用，默認頭部不存在
let currNode = this._head.next
let tmpArr = []
while (currNode !== null) {
tmpArr.push(currNode)
currNode = currNode.next
}
return tmpArr
}
實例測試
// 運行測試
let obj = new LinkedList('節(jié)點0', '節(jié)點1', '節(jié)點2', '節(jié)點3', '節(jié)點4', '節(jié)點5')
console.log('---實例對象')
console.log(obj)
console.log('---末尾插入元素')
obj.push('push插入')
console.log(obj.display())
console.log('---元素后插入元素')
obj.insert('元素插入', '節(jié)點2')
console.log(obj.display())
console.log('---索引處插入元素')
obj.insertIndex('索引插入', 5)
console.log(obj.display())
console.log('---查找元素位置')
console.log(obj.find('節(jié)點4'))
console.log('---移除元素')
obj.remove('節(jié)點5')
console.log(obj.display())
console.log('---移除索引元素')
obj.removeIndex(5)
console.log(obj.display())
console.log('---元素長度')
console.log(obj.size())
console.log('---索引查找')
console.log(obj.findIndex(2))
console.log('---元素查找索引')
console.log(obj.findIndexOf('節(jié)點3'))
console.log('---反轉(zhuǎn)鏈表')
obj.reversal()
console.log(obj.display())
測試結(jié)果
結(jié)尾
最近遇到單鏈表反轉(zhuǎn)的問題，所有加了一個單鏈表反轉(zhuǎn)的方法，用遞歸實現(xiàn)
相關鏈接
總結(jié)
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。
相關文章
這篇文章主要為大家詳細介紹了js實現(xiàn)放大鏡特效，簡單實用的代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-05-05
這篇文章主要為大家詳細介紹了微信小程序?qū)崿F(xiàn)自定義拍攝組件，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要介紹了關于js內(nèi)存泄露的一個好例子。需要的朋友可以過來參考下，希望對大家有所幫助2013-12-12
JS前端開發(fā)之exec()和match()的對比使用
match()方法可在字符串內(nèi)檢索指定的值,或找到一個或多個正則表達式的匹配,下面這篇文章主要給大家介紹了關于JS前端開發(fā)之exec()和match()的對比使用的相關資料,需要的朋友可以參考下2022-09-09
JavaScript ES6 Class類實現(xiàn)原理詳解
這篇文章主要介紹了JavaScript ES6 Class類實現(xiàn)原理詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-05-05
有時候是只想告知用戶這個地方是可以進行勾選操作的而不想讓用戶在此處勾選（比如在信息展示頁面），這時候就需要將復選框設置成只讀的效果，具體實現(xiàn)方法如下2013-08-08
懶加載（Lazy Loading）是一種在軟件開發(fā)中常用的優(yōu)化技術,它主要用于延遲加載資源,直到真正需要使用的時候才進行加載,這樣可以減少初始加載的時間和資源消耗,并提升用戶體驗,本文給大家詳細介紹了JavaScript的懶加載是如何實現(xiàn)的,需要的朋友可以參考下2024-01-01
這篇文章主要為大家詳細介紹了js實現(xiàn)貪吃蛇游戲簡易版，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-09-09
這篇文章主要介紹了在線所見即所得HTML編輯器的實現(xiàn)原理淺析,本文用初始化、打開編輯功能、獲取編輯器的內(nèi)容、增加樣式設置、再進一步等步驟闡述在線編輯器的基本實現(xiàn)原理,需要的朋友可以參考下2015-04-04
IFrame對象占用的內(nèi)存資源在窗體關閉后不會釋放。彈出關閉反復多次后，IE瀏覽器內(nèi)存占用可超過數(shù)百M，嚴重時IE瀏覽器報錯2014-08-08