国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JS數據結構學習:鏈表

XanaHopper / 1434人閱讀

摘要:在存儲多個元素時,我們最常用的數據結構可能是數組,究其原因可能是數組訪問方便,可以直接通過訪問,但是數組也存在一定的缺點,數組的大小是固定,數組在執行插入或者刪除的時候成本很高。

在存儲多個元素時,我們最常用的數據結構可能是數組,究其原因可能是數組訪問方便,可以直接通過[]訪問,但是數組也存在一定的缺點,數組的大小是固定,數組在執行插入或者刪除的時候成本很高。

鏈表存儲的是有序的元素集合,和數組不同的是,鏈表中的元素在內存并不是連續放置,每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用組成,結構如下圖所示:

和數組相比,鏈表的優勢在于:添加或者刪除元素不需要移動其他元素,劣勢在與鏈表相對于數組結構更復雜,需要一個指向下一個元素的指針,在訪問鏈表中的某個元素也需要從頭迭代,而不是像數組一樣直接訪問

鏈表的創建

首先讓我們來看一下鏈表的大概骨架,需要定義一些什么屬性:

function LinkedList() {
  let Node = function (element) {
    this.element = element
    this.next = null
  }
  let length = 0
  let head = null
  this.append = function (element) {
  }
  this.insert = function (position, element) {
  }
  this.removeAt = function (position) {
  }
  this.remove = function (element) {
  }
  this.indexOf = function (element) {
  }
  this.isEmpty = function () {
  }
  this.size = function () {
  }
  this.getHead = function () {
  }
  this.toString = function () {
  }
  this.print = function () {
  }
}

首先LinkedList里面需要定義一個Node輔助類,表示要加入鏈表的項,包含一個element屬性和一個指向下一個節點的指針next,接下來定義了一個指針的頭head和指針的長度length,然后就是最重要的類里面的方法,接下來就讓我們一起來看這些方法的職責和實現

append(向鏈表尾部追加元素)

鏈表在向尾部追加元素的時候有兩種情況:鏈表為空,添加的是第一個元素,或者鏈表不為空,追加元素,下面來看具體實現:

this.append = function (element) {
    let node = new Node(element), current
    if (head === null) {
      head = node // 鏈表為空時,插入
    } else {
      current = node
      while (current.next) { // 循環鏈表,直到最后一項
        current = current.next
      }
      current.next = node // 找到最后一項,將新增元素連接
    }
    length++
  }

現在讓我們先來看第一個種情況,鏈表為空時,插入就直接是頭,因此直接將node賦值給head就行,第二種情況,當鏈表有元素時,就需要先循環鏈表,找到最后一項,然后將最后一項的next指針指向node

removeAt(移除元素)

現在讓我們來看看怎么從指定位置移除元素,移除元素也有兩個場景,第一種是移除第一個元素,第二種是移除第一個以外的任意一個元素,來看具體實現:

this.removeAt = function (position) {
    if (position > -1 && position < length) { // 判斷邊界
      let previous, index = 0, current = head
      if (position === 0) { // 移除第一項
        head = current.next
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      length--
      return current.element
    } else {
      return null
    }
  }

接下來一起來分析一下上面的代碼,首先判斷要刪除的位置是不是有效的位置,然后來看第一種情況,當移除的元素是第一項是時,此時直接將head指向第二個元素就行了,第二種情況就會稍微復雜一點,首先需要一個index控制遞增,previous記錄前一個位置,移除當前元素,就是將前一個元素的next指向下一個元素,來看一個示意圖:

因此在while循環中始終用previous記錄上一個位置元素,current記錄下一個元素,跳出循環時,上一個元素的next指針指向當前元素的next指針指向的元素,就將當前元素移出鏈表

insert(任意位置插入)

接下來來看在任意位置插入的insert方法,這個方法同樣需要考慮兩種情況,插入位置在頭部和插入位置不在頭部,下面來看一下具體實現:

this.insert = function (position, element) {
    if (position > -1 && position <= length) {
      let node = new Node(element),previous, index = 0, current = head
      if (position === 0) {
        node.next = current
        head = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = node
        node.next = current
      }
      length++
      return true
    } else {
      return false
    }
  }

先來看第一種情況,鏈表起點添加一個元素,將node.next指向current,然后再將node的引用賦值給head,這樣就再鏈表的起點添加了一個元素,第二種情況,在其他位置插入一個元素,previous是插入元素的前一個元素,current為插入元素的后一個元素,想要插入一個元素,就需要將前一個元素的next指向要插入的元素,要插入元素的next指向下一個元素,來看示意圖:

如上圖所示:將新項node插入到previous和current之間,需要將previous.next指向node,node.next指向current,這樣就在鏈表中插入了一個新的項

toString

toString方法會把LinkedList對象轉換成一個字符串,下面來看具體實現:

this.toString = function () {
    let current = head, string = ""
    while (current) {
      string += current.element + (current.next ? "n" : "")
      current = current.next
    }
    return string
  }

循環遍歷所有元素,以head為起點,當存在下一個元素時,就將其拼接到字符串中,直到next為null

indexOf

indexOf方法返回對應元素的位置,存在就返回對應的索引,不存在返回-1,來看具體的實現:

this.indexOf = function (element) {
    let current = head, index = 0
    while (current) {
      if (current.element === element) {
        return index
      }
      index++
      current = current.next
    }
    return -1
  }

遍歷鏈表,當前元素的值與目標值一致時返回元素的位置index,遍歷完鏈表還沒找到則返回-1

remove、isEmpty、size、getHead

由于這幾個方法實現比較簡單,直接來看具體實現:

this.remove = function (element) { // 移除指定元素
    let index = this.indexOf(element)
    return this.removeAt(index)
  }
this.isEmpty = function () { // 判斷鏈表是否為空
    return length === 0
  }
this.size = function () { // 獲取鏈表長度
    return length
  }
this.getHead = function () { // 獲取鏈表頭
    return head
  }
總結

這篇文章主要對鏈表做了簡單介紹,對鏈表的簡單實現。如果有錯誤或不嚴謹的地方,歡迎批評指正,如果喜歡,歡迎點贊。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/102042.html

相關文章

  • 我對JS鏈表的簡單學習

    摘要:我對鏈表的學習什么是鏈表要存儲多個元素,數組可能是最常用的數據結構。鏈表的學習創建一個鏈表各種方法表示要加入列表的項,它包含一個屬性以及一個屬性,表示要添加到列表的值,表示指向列表下一個節點項的指針。 我對JS鏈表的學習 什么是鏈表 要存儲多個元素,數組可能是最常用的數據結構。這種數據結構非常方便,但是有一個缺點:從數組的起點或者中間插入或移除項的成本非常高,因為需要移動元素(比如你插...

    余學文 評論0 收藏0
  • 我對JS散列表的簡單學習

    摘要:對散列表的簡單學習類也叫類,是類的一種散列表實現方式。鍵值散列函數散列值形成散列表地址數據鍵值對相關操作方法創建一個散列表實現一個散列函數,即將碼值相加的方法。 對JS散列表的簡單學習 HashTable類也叫HashMap類,是Dictionary類的一種散列表實現方式。 散列算法的作用是盡可能快的在數據結構中找到一個值。 在之前的學習中,如果你想要獲得數據結構中的一個值,需要遍歷整...

    lindroid 評論0 收藏0
  • JS數據結構與算法_鏈表

    摘要:上一篇數據結構與算法棧隊列下一篇數據結構與算法集合字典寫在前面說明數據結構與算法系列文章的代碼和示例均可在此找到上一篇博客發布以后,僅幾天的時間竟然成為了我寫博客以來點贊數最多的一篇博客。 上一篇:JS數據結構與算法_棧&隊列下一篇:JS數據結構與算法_集合&字典 寫在前面 說明:JS數據結構與算法 系列文章的代碼和示例均可在此找到 上一篇博客發布以后,僅幾天的時間竟然成為了我寫博客以...

    NeverSayNever 評論0 收藏0
  • CSS技巧

    摘要:技巧使你的更加專業這是上關于技巧的一篇譯文,另外你也可以在本項目看到原文。列舉了一些很實用的技巧,比如給空內容的標簽添加內容,逗號分隔列表等等。排序算法看源碼,把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。 成為專業程序員路上用到的各種優秀資料、神器及框架 成為一名專業程序員的道路上,需要堅持練習、學習與積累,技術方面既要有一定的廣度,更要有自己的深度。 Java...

    DangoSky 評論0 收藏0

發表評論

0條評論

XanaHopper

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<