成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

用 JavaScript 實(shí)現(xiàn)鏈表操作 - 01 Push & Build List

Scorpion / 1306人閱讀

摘要：寫兩個(gè)幫助函數(shù)來(lái)創(chuàng)建鏈表。用于把一個(gè)節(jié)點(diǎn)插入到鏈表的頭部。這個(gè)方法應(yīng)該始終返回一個(gè)新的鏈表。接收一個(gè)數(shù)組為參數(shù)，創(chuàng)建對(duì)應(yīng)的鏈表。參考資料的代碼實(shí)現(xiàn)的測(cè)試

TL;DR

寫兩個(gè)幫助函數(shù)來(lái)創(chuàng)建鏈表。系列目錄見 前言和目錄 。

需求

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

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

push 用于把一個(gè)節(jié)點(diǎn)插入到鏈表的頭部。它接受兩個(gè)參數(shù) head 和 data ，head 可以是一個(gè)節(jié)點(diǎn)對(duì)象或者 null 。這個(gè)方法應(yīng)該始終返回一個(gè)新的鏈表。

buildList 接收一個(gè)數(shù)組為參數(shù)，創(chuàng)建對(duì)應(yīng)的鏈表。

buildList([1, 2, 3]) === 1 -> 2 -> 3 -> null
定義節(jié)點(diǎn)對(duì)象

作為鏈表系列的第一課，我們需要先定義節(jié)點(diǎn)對(duì)象是什么樣子。按照 Codewars 上的設(shè)定，一個(gè)節(jié)點(diǎn)對(duì)象有兩個(gè)屬性 data 和 next 。data 是這個(gè)節(jié)點(diǎn)的值，next 是下一個(gè)節(jié)點(diǎn)的引用。這是默認(rèn)的類模板。

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

這是 push 的基本實(shí)現(xiàn)：

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

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

我更傾向于修改一下 Node 的構(gòu)造函數(shù)，把 next 也當(dāng)成參數(shù)，并且加上默認(rèn)值，這會(huì)讓后面的事情簡(jiǎn)化很多：

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

新的 push 實(shí)現(xiàn)：

function push(head, data) {
  return new Node(head, data)
}
buildList 遞歸版本

這個(gè)函數(shù)非常適合用遞歸實(shí)現(xiàn)。這是遞歸的版本：

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

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

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

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

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

到第三輪就已經(jīng)是最基本的情況了，數(shù)組為空，這時(shí)返回 null 代表空節(jié)點(diǎn)。

循環(huán)版本

依照上面的思路，循環(huán)也很容易實(shí)現(xiàn)，只要反向遍歷數(shù)組就行。因?yàn)檠h(huán)已經(jīng)考慮了數(shù)組為空的情況，這里就不用進(jìn)行邊界判斷了。

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

結(jié)合循環(huán)版本的思路和 JavaScript 的數(shù)組迭代器，我們可以得出一個(gè) one-liner 版本。

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

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

參考資料

Codewars Kata
GitHub 的代碼實(shí)現(xiàn)
GitHub 的測(cè)試

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/81069.html

相關(guān)文章

  • 用 JavaScript 實(shí)現(xiàn)鏈表操作 - 04 Insert Nth Node

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

    894974231 評(píng)論0 收藏0

  • Stack & Queue 棧和隊(duì)列的學(xué)習(xí)筆記

    摘要：的前部分內(nèi)容講的是棧和隊(duì)列的實(shí)現(xiàn)。學(xué)習(xí)環(huán)境在學(xué)習(xí)這門課之前，先引入的概念，即抽象數(shù)據(jù)類型。鏈表實(shí)現(xiàn)學(xué)習(xí)，鏈表實(shí)現(xiàn)簡(jiǎn)單的數(shù)組實(shí)現(xiàn)鏈表實(shí)現(xiàn)簡(jiǎn)單的數(shù)組實(shí)現(xiàn)解決使用?；蛘哧?duì)列時(shí)，的數(shù)據(jù)類型指定問(wèn)題。 Week2 的前部分內(nèi)容講的是棧和隊(duì)列的Java實(shí)現(xiàn)。學(xué)習(xí)環(huán)境：mac, inteliJ, java version 1.8.0_77 在學(xué)習(xí)這門課之前，先引入Abstract Data Type...

    peixn 評(píng)論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 線性表（數(shù)組、棧、隊(duì)列、鏈表）

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

    kaka 評(píng)論0 收藏0

  • 用 JavaScript 實(shí)現(xiàn)鏈表

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

    appetizerio 評(píng)論0 收藏0

  • 用 JavaScript 實(shí)現(xiàn)鏈表操作 - 02 Length & Count

    摘要：計(jì)算鏈表的長(zhǎng)度和指定元素的重復(fù)次數(shù)。需求實(shí)現(xiàn)一個(gè)函數(shù)來(lái)計(jì)算鏈表的長(zhǎng)度。遞歸版本遞歸是最有表達(dá)力的版本。注意因?yàn)橐谕獠孔鳛榉祷刂凳褂?，我們只能用而不是聲明變量。參考資料的代碼實(shí)現(xiàn)的測(cè)試 TL;DR 計(jì)算鏈表的長(zhǎng)度和指定元素的重復(fù)次數(shù)。系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)一個(gè) length() 函數(shù)來(lái)計(jì)算鏈表的長(zhǎng)度。 length(null) === 0 length(1 -> 2 -...

    Batkid 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<