溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
前言
前端也要搞好數據結構哦！
用JavaScript實現了個單鏈表，通過LinkedList構造函數可實例化一個單鏈表數據結構的對象，所有的方法放到LinkedList構造函數的原型對象上，寫了暫時能想到的所有方法
GitHub源碼地址，下載可運行
實現
方法介紹
查找
obj.find(item)通過item元素內容查找到該元素obj.findIndex(index)通過index索引查找到該元素obj.findIndexOf(item)通過item元素內容查找到該元素索引obj.findPrev(item)通過item元素查找上一個節點元素添加
obj.insert(item,newElement)在item元素后插入新元素obj.push(item)在鏈表末尾插入item元素obj.insertIndex(index,newElement)在index索引處插入新元素刪除
obj.remove(item)刪除item元素obj.removeIndex(index)刪除index索引處節點其他
obj.size()返回該鏈表的長度obj.display()數組形式返回該鏈表，便于觀察，測試obj.reversal()鏈表順序反轉（遞歸）方法代碼
鏈表類LinkedList
function LinkedList (...rest) {
this._head = new Node('_head') // 鏈表頭節點
// 如果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
創建新節點類Node
function Node (element) {
this.element = element
this.next = null
}
obj.find(item)
// 查找函數，在鏈表中查找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位置，返回當前節點，出去頭結點
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)
// 尋找目標節點item的上一個節點，未找到返回-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)
// 插入節點，找到要插入到的item的節點位置，把新節點插到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}」節點`)
}
}
obj.insertIndex(index,newElement)
// 插入節點，新節點插到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}」索引節點`)
}
}
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)
// 刪除節點，找到刪除的位置，刪除，未找到提示錯誤
function remove (item) {
// 找到當前和上一個節點，讓上一個節點的next指向item下一個節點
let tmpPrev = this.findPrev(item)
let tmpNext = this.find(item)
if (tmpPrev && tmpNext) {
tmpPrev.next = tmpNext.next
} else {
console.error(`remove error：鏈表中不存在「${item}」節點`)
}
}
obj.removeIndex(index)
// 刪除某個索引下的節點
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}」索引節點`)
}
}
obj.size()
function size () {
let currNode = this._head
let tmpSize = 0
while (currNode.next !== null) {
tmpSize += 1
currNode = currNode.next
}
return tmpSize // 不計算頭部節點
}
obj.reversal()
// 鏈表反轉=>遞歸
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('節點0', '節點1', '節點2', '節點3', '節點4', '節點5')
console.log('---實例對象')
console.log(obj)
console.log('---末尾插入元素')
obj.push('push插入')
console.log(obj.display())
console.log('---元素后插入元素')
obj.insert('元素插入', '節點2')
console.log(obj.display())
console.log('---索引處插入元素')
obj.insertIndex('索引插入', 5)
console.log(obj.display())
console.log('---查找元素位置')
console.log(obj.find('節點4'))
console.log('---移除元素')
obj.remove('節點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('節點3'))
console.log('---反轉鏈表')
obj.reversal()
console.log(obj.display())
測試結果
結尾
最近遇到單鏈表反轉的問題，所有加了一個單鏈表反轉的方法，用遞歸實現
相關鏈接
實現單鏈表反轉的幾種方法
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
