如何用JavaScript實(shí)現(xiàn)功能齊全的單鏈表詳解

更新時(shí)間：2019年02月11日 10:47:35 作者：王文健

這篇文章主要給大家介紹了關(guān)于如何用JavaScript實(shí)現(xiàn)功能齊全的單鏈表的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧

前言

前端也要搞好數(shù)據(jù)結(jié)構(gòu)哦！

用JavaScript實(shí)現(xiàn)了個(gè)單鏈表，通過LinkedList構(gòu)造函數(shù)可實(shí)例化一個(gè)單鏈表數(shù)據(jù)結(jié)構(gòu)的對象，所有的方法放到LinkedList構(gòu)造函數(shù)的原型對象上，寫了暫時(shí)能想到的所有方法

GitHub源碼地址，下載可運(yùn)行

實(shí)現(xiàn)

通過LinkedList的類創(chuàng)建鏈表實(shí)例，鏈表下有添加，查找，刪除，顯示節(jié)點(diǎn)等方法
鏈表初始默認(rèn)有一個(gè)"_head"頭部節(jié)點(diǎn)，使用時(shí)隱藏
按元素/索引添加、刪除，未找到時(shí)返回錯(cuò)誤，查找未找到時(shí)返回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元素查找上一個(gè)節(jié)點(diǎn)元素

添加

obj.insert(item,newElement)在item元素后插入新元素
obj.push(item)在鏈表末尾插入item元素
obj.insertIndex(index,newElement)在index索引處插入新元素

刪除

obj.remove(item)刪除item元素
obj.removeIndex(index)刪除index索引處節(jié)點(diǎn)

其他

obj.size()返回該鏈表的長度
obj.display()數(shù)組形式返回該鏈表，便于觀察，測試
obj.reversal()鏈表順序反轉(zhuǎn)（遞歸）

方法代碼

鏈表類LinkedList

 function LinkedList (...rest) {
 this._head = new Node('_head') // 鏈表頭節(jié)點(diǎn)
 // 如果new時(shí)有傳進(jìn)值，則添加到實(shí)例中
 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é)點(diǎn)類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位置，返回當(dāng)前節(jié)點(diǎn)，出去頭結(jié)點(diǎn)
 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)

// 尋找目標(biāo)節(jié)點(diǎn)item的上一個(gè)節(jié)點(diǎn)，未找到返回-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é)點(diǎn)，找到要插入到的item的節(jié)點(diǎn)位置，把新節(jié)點(diǎn)插到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é)點(diǎn)`)
 }
 }

obj.insertIndex(index,newElement)

// 插入節(jié)點(diǎn)，新節(jié)點(diǎn)插到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é)點(diǎn)`)
 }
 }

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é)點(diǎn)，找到刪除的位置，刪除，未找到提示錯(cuò)誤
 function remove (item) {
 // 找到當(dāng)前和上一個(gè)節(jié)點(diǎn)，讓上一個(gè)節(jié)點(diǎn)的next指向item下一個(gè)節(jié)點(diǎn)
 let tmpPrev = this.findPrev(item)
 let tmpNext = this.find(item)
 if (tmpPrev && tmpNext) {
 tmpPrev.next = tmpNext.next
 } else {
 console.error(`remove error：鏈表中不存在「${item}」節(jié)點(diǎn)`)
 }
 }

obj.removeIndex(index)

// 刪除某個(gè)索引下的節(jié)點(diǎn)
 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é)點(diǎn)`)
 }
 }

obj.size()

 function size () {
 let currNode = this._head
 let tmpSize = 0
 while (currNode.next !== null) {
 tmpSize += 1
 currNode = currNode.next
 }
 return tmpSize // 不計(jì)算頭部節(jié)點(diǎn)
 }

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 () {
 // 鏈表展示和使用，默認(rèn)頭部不存在
 let currNode = this._head.next
 let tmpArr = []
 while (currNode !== null) {
 tmpArr.push(currNode)
 currNode = currNode.next
 }
 return tmpArr
 }

實(shí)例測試

 // 運(yùn)行測試
 let obj = new LinkedList('節(jié)點(diǎn)0', '節(jié)點(diǎn)1', '節(jié)點(diǎn)2', '節(jié)點(diǎn)3', '節(jié)點(diǎn)4', '節(jié)點(diǎn)5')
 console.log('---實(shí)例對象')
 console.log(obj)
 console.log('---末尾插入元素')
 obj.push('push插入')
 console.log(obj.display())
 console.log('---元素后插入元素')
 obj.insert('元素插入', '節(jié)點(diǎn)2')
 console.log(obj.display())
 console.log('---索引處插入元素')
 obj.insertIndex('索引插入', 5)
 console.log(obj.display())
 console.log('---查找元素位置')
 console.log(obj.find('節(jié)點(diǎn)4'))
 console.log('---移除元素')
 obj.remove('節(jié)點(diǎn)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é)點(diǎn)3'))
 console.log('---反轉(zhuǎn)鏈表')
 obj.reversal()
 console.log(obj.display())

測試結(jié)果