用JavaScript實現功能齊全的單鏈表
前言
前端也要搞好資料結構哦!!
用JavaScript實現了個單鏈表,通過 LinkedList
建構函式可例項化一個 單鏈表 資料結構的物件,所有的方法放到 LinkedList
建構函式的原型物件上,寫了暫時能想到的所有方法
實現
- 通過
LinkedList
的類建立連結串列例項,連結串列下有新增,查詢,刪除,顯示節點等方法 - 連結串列初始預設有一個"_head"頭部節點,使用時隱藏
- 按 元素/索引 新增、刪除,未找到時返回 錯誤 ,查詢未找到時返回null或-1
-
let obj = new LinkedList()
方法介紹
查詢
obj.find(item) obj.findIndex(index) obj.findIndexOf(item) obj.findPrev(item)
新增
obj.insert(item,newElement) obj.push(item) obj.insertIndex(index,newElement)
刪除
obj.remove(item) obj.removeIndex(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())
測試結果
結尾
最近遇到單鏈表反轉的問題,所有加了一個單鏈表反轉的方法,用遞迴實現