<dl id="opymh"></dl>

<div id="opymh"></div>
      <div id="opymh"><tr id="opymh"></tr></div>

        <em id="opymh"><ins id="opymh"><mark id="opymh"></mark></ins></em><sup id="opymh"><menu id="opymh"></menu></sup>

        <em id="opymh"></em>

        <em id="opymh"><ol id="opymh"></ol></em>

              頻道欄目
              首頁 > 程序開發 > web前端 > HTML/CSS > 正文
              用JavaScript實現功能齊全的單鏈表
              2019-02-13 13:52:51           
              收藏   我要投稿

              前言

              前端也要搞好數據結構哦!!

              JavaScript實現了個單鏈表,通過LinkedList構造函數可實例化一個單鏈表數據結構的對象,所有的方法放到LinkedList構造函數的原型對象上,寫了暫時能想到的所有方法

              GitHub源碼地址,下載可運行

              實現

              通過LinkedList的類創建鏈表實例,鏈表下有添加,查找,刪除,顯示節點等方法 鏈表初始默認有一個"_head"頭部節點,使用時隱藏 按元素/索引 添加、刪除,未找到時返回錯誤,查找未找到時返回null或-1 let obj = new LinkedList()

              方法介紹

              查找

              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())

              測試結果

              [email protected]

              結尾

              最近遇到單鏈表反轉的問題,所有加了一個單鏈表反轉的方法,用遞歸實現

              相關鏈接

              實現單鏈表反轉的幾種方法

              如何用JavaScript實現一個功能齊全的單鏈表

              點擊復制鏈接 與好友分享!回本站首頁
              上一篇:webworker的傳值方式以及耗時對比
              下一篇:你可能不熟悉的JS總結
              相關文章
              圖文推薦
              點擊排行

              關于我們 | 聯系我們 | 廣告服務 | 投資合作 | 版權申明 | 在線幫助 | 網站地圖 | 作品發布 | Vip技術培訓 | 舉報中心

              版權所有: 紅黑聯盟--致力于做實用的IT技術學習網站

              极速飞艇好假
              <dl id="opymh"></dl>

              <div id="opymh"></div>
                  <div id="opymh"><tr id="opymh"></tr></div>

                    <em id="opymh"><ins id="opymh"><mark id="opymh"></mark></ins></em><sup id="opymh"><menu id="opymh"></menu></sup>

                    <em id="opymh"></em>

                    <em id="opymh"><ol id="opymh"></ol></em>

                          <dl id="opymh"></dl>

                          <div id="opymh"></div>
                              <div id="opymh"><tr id="opymh"></tr></div>

                                <em id="opymh"><ins id="opymh"><mark id="opymh"></mark></ins></em><sup id="opymh"><menu id="opymh"></menu></sup>

                                <em id="opymh"></em>

                                <em id="opymh"><ol id="opymh"></ol></em>