用 JavaScript 實現鏈表操作 - 01 Push & Build List

Scorpion 發布于2019-08-20 12:35 / 1302人閱讀

摘要：寫兩個幫助函數來創建鏈表。用于把一個節點插入到鏈表的頭部。這個方法應該始終返回一個新的鏈表。接收一個數組為參數，創建對應的鏈表。參考資料的代碼實現的測試

TL;DR

寫兩個幫助函數來創建鏈表。系列目錄見前言和目錄。

需求

寫兩個方法 push 和 buildList 來初始化鏈表。嘗試在 buildList 中使用 push 。下面的例子中我用 a -> b -> c 來表示鏈表，這是為了書寫方便，并不是 JavaScript 的有效語法。

let chained = null
chained = push(chained, 3)
chained = push(chained, 2)
chained = push(chained, 1)
push(chained, 8) === 8 -> 1 -> 2 -> 3 -> null

push 用于把一個節點插入到鏈表的頭部。它接受兩個參數 head 和 data ，head 可以是一個節點對象或者 null 。這個方法應該始終返回一個新的鏈表。

buildList 接收一個數組為參數，創建對應的鏈表。

buildList([1, 2, 3]) === 1 -> 2 -> 3 -> null

定義節點對象

作為鏈表系列的第一課，我們需要先定義節點對象是什么樣子。按照 Codewars 上的設定，一個節點對象有兩個屬性 data 和 next 。data 是這個節點的值，next 是下一個節點的引用。這是默認的類模板。

function Node(data) {
  this.data = data
  this.next = null
}

push

這是 push 的基本實現：

function push(head, data) {
  const node = new Node(data)

  if (head) {
    node.next = head
    return node
  } else {
    return node
  }
}

我更傾向于修改一下 Node 的構造函數，把 next 也當成參數，并且加上默認值，這會讓后面的事情簡化很多：

function Node(data = null, next = null) {
  this.data = data
  this.next = next
}

新的 push 實現：

function push(head, data) {
  return new Node(head, data)
}

buildList 遞歸版本

這個函數非常適合用遞歸實現。這是遞歸的版本：

function buildList(array) {
  if (!array || !array.length) return null
  const data = array.shift()
  return push(buildList(array), data)
}

遞歸的思路是，把大的復雜的操作逐步分解成小的操作，直到分解成最基本的情況。拿這個例子解釋，給定數組 [1, 2, 3]，遞歸的實現思路是逐步往鏈表頭部插入數據 3，2，1 ，一共三輪。第一輪相當于 push(someList, 3) 。這個 someList 是什么呢，其實就是 buildList([1, 2]) 的返回值。以此類推：

第一輪 push(buildList([1, 2]), 3)

第二輪 push(buildList([1]), 2)

第三輪 push(buildList([]), 3)

到第三輪就已經是最基本的情況了，數組為空，這時返回 null 代表空節點。

循環版本

依照上面的思路，循環也很容易實現，只要反向遍歷數組就行。因為循環已經考慮了數組為空的情況，這里就不用進行邊界判斷了。

function buildListV2(array) {
  let list = null
  for (let i = array.length - 1; i >= 0; i--) {
    list = push(list, array[i])
  }
  return list
}

One-liner

結合循環版本的思路和 JavaScript 的數組迭代器，我們可以得出一個 one-liner 版本。

function buildListV3(array) {
  return (array || []).reduceRight(push, null)
}

這個就不解釋了，留給各位自己思考下吧。

參考資料

Codewars Kata
GitHub 的代碼實現
GitHub 的測試

云服務器 GPU云服務器用javascript操作xml list&ampamp list&amplt 多鏈表c語言實現

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

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

用 JavaScript 實現鏈表操作 - 04 Insert Nth Node

摘要：給定一個鏈表，一個范圍在內的索引號，和一個數據，這個函數會生成一個新的節點并插入到指定的索引位置，并始終返回鏈表的頭。的返回值一定是個鏈表，我們把它賦值給就行。但這個例子的邊界情況是返回值不同如果，返回新節點。 TL;DR 插入第 N 個節點。系列目錄見前言和目錄。需求實現一個 insertNth() 方法，在鏈表的第 N 個索引處插入一個新節點。 insertNth() 可以...

894974231 2019-08-22 10:50 評論0 收藏0
Stack &amp; Queue 棧和隊列的學習筆記

摘要：的前部分內容講的是棧和隊列的實現。學習環境在學習這門課之前，先引入的概念，即抽象數據類型。鏈表實現學習，鏈表實現簡單的數組實現鏈表實現簡單的數組實現解決使用棧或者隊列時，的數據類型指定問題。 Week2 的前部分內容講的是棧和隊列的Java實現。學習環境：mac, inteliJ, java version 1.8.0_77 在學習這門課之前，先引入Abstract Data Type...

peixn 2019-08-14 17:12 評論0 收藏0
JavaScript 數據結構與算法之美 - 線性表（數組、棧、隊列、鏈表）

摘要：每個線性表上的數據最多只有前和后兩個方向。數組鏈表隊列棧等就是線性表結構。非線性表數據之間并不是簡單的前后關系。不包含任何元素的棧稱為空棧。移除棧頂的元素，同時返回被移除的元素。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言基礎知識就像是一座大樓的地基，它決定了我們的技術高度。我們應該多掌握一些可移值的...

kaka 2019-08-23 18:25 評論0 收藏0
用 JavaScript 實現鏈表

摘要：相反，雙向鏈表具有指向其前后元素的節點。另外，可以對鏈表進行排序。這個實用程序方法用于打印鏈表中的節點，僅用于調試目的。第行將更新為，這是從鏈表中彈出最后一個元素的行為。如果鏈表為空，則返回。 showImg(https://segmentfault.com/img/bVbsaI7?w=1600&h=228); 什么是鏈表單鏈表是表示一系列節點的數據結構，其中每個節點指向鏈表中的下一...

appetizerio 2019-08-26 13:51 評論0 收藏0
用 JavaScript 實現鏈表操作 - 02 Length &amp; Count

摘要：計算鏈表的長度和指定元素的重復次數。需求實現一個函數來計算鏈表的長度。遞歸版本遞歸是最有表達力的版本。注意因為要在外部作為返回值使用，我們只能用而不是聲明變量。參考資料的代碼實現的測試 TL;DR 計算鏈表的長度和指定元素的重復次數。系列目錄見前言和目錄。需求實現一個 length() 函數來計算鏈表的長度。 length(null) === 0 length(1 -> 2 -...

Batkid 2019-08-22 10:47 評論0 收藏0