用 JavaScript 實(shí)現(xiàn)鏈表操作 - 前言和目錄

BetaRabbit 發(fā)布于2019-08-20 12:25 / 1252人閱讀

摘要：我打算寫一個(gè)鏈表操作的系列，來自的系列，實(shí)現(xiàn)語言是。通過自己實(shí)現(xiàn)一個(gè)鏈表和常用操作，可以加深理解這類數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)。鏈表經(jīng)常用來訓(xùn)練指針操作，雖然這只對(duì)適用，但等高級(jí)語言中控制引用的思路其實(shí)也差不多。

TL;DR

我打算寫一個(gè)鏈表操作的系列，來自 Codewars 的 Linked List 系列 kata ，實(shí)現(xiàn)語言是 JavaScript 。這篇是開篇，簡(jiǎn)單描述了一下我寫這個(gè)的目的，也作為系列的目錄。

為什么要學(xué)習(xí)鏈表

我的年度目標(biāo)之一就是學(xué)習(xí)一些數(shù)據(jù)結(jié)構(gòu)和算法，用于打基礎(chǔ)和培養(yǎng)邏輯思維能力。Codewars 上的這個(gè)系列同時(shí)符合這兩點(diǎn)。

鏈表是常用數(shù)據(jù)結(jié)構(gòu)之一，它甚至是某些語言（比如 Elixir）的內(nèi)置數(shù)據(jù)結(jié)構(gòu)。通過自己實(shí)現(xiàn)一個(gè)鏈表和常用操作，可以加深理解這類數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)。

鏈表經(jīng)常用來訓(xùn)練指針操作，雖然這只對(duì) C 適用，但 JavaScript 等高級(jí)語言中控制引用的思路其實(shí)也差不多。而且鏈表也是練習(xí)遞歸的理想數(shù)據(jù)結(jié)構(gòu)之一。

基于此，每個(gè) kata 我都會(huì)盡量提供遞歸和循環(huán)兩個(gè)版本，某些操作會(huì)實(shí)現(xiàn)尾遞歸以符合題目要求。這是一個(gè)很有意思的過程，有時(shí)候遞歸更好，有時(shí)候循環(huán)更好，也有少數(shù)時(shí)候兩者都不是最優(yōu)化的方案。

Codewars 上沒有總綱，但每一個(gè) kata 都有整個(gè)系列的目錄。我列舉如下，一共 18 個(gè) kata 。每篇的博客鏈接會(huì)在更新后附上。另外，所有代碼都放在 GitHub 上，代碼的更新比博客要快，如果覺得對(duì)你有幫助，請(qǐng)幫我點(diǎn)個(gè)贊！

Push & BuildOneTwoThree

Length & Count

Get Nth Node

Insert Nth Node

Sorted Insert

Insert Sort

Append

Remove Duplicates

Move Node

Move Node In-place

Alternating Split

Front back split

Shuffle Merge

Sorted Merge

Merge sort

Sorted Intersect

Iterative Reverse

Recursive Reverse

GPU云服務(wù)器云服務(wù)器用javascript操作xml 多鏈表c語言實(shí)現(xiàn) java實(shí)現(xiàn)鏈表插入遍歷c語言實(shí)現(xiàn)鏈表

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

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

相關(guān)文章

用 JavaScript 實(shí)現(xiàn)鏈表操作 - 06 Insert Sort

摘要：需求實(shí)現(xiàn)一個(gè)函數(shù)對(duì)鏈表進(jìn)行升序排列插入排序。關(guān)于插入排序插入排序的介紹可以看，大體邏輯為建立一個(gè)新的空鏈表。遍歷完成，返回新鏈表。代碼如下總結(jié)因?yàn)橛猩蟼€(gè)的函數(shù)的幫助，這個(gè)插入排序?qū)崿F(xiàn)起來非常簡(jiǎn)單。 TL;DR 2016 年末最后一篇，對(duì)鏈表進(jìn)行插入排序。系列目錄見前言和目錄。需求實(shí)現(xiàn)一個(gè) insertSort() 函數(shù)對(duì)鏈表進(jìn)行升序排列（插入排序）。實(shí)現(xiàn)過程中可以使用上一個(gè) ...

doodlewind 2019-08-21 11:28 評(píng)論0 收藏0
用 JavaScript 實(shí)現(xiàn)鏈表操作 - 15 Merge Sort

摘要：需求實(shí)現(xiàn)函數(shù)進(jìn)行歸并排序。解法歸并排序的運(yùn)行方式是，遞歸的把一個(gè)大鏈表切分成兩個(gè)小鏈表。切分到最后就全是單節(jié)點(diǎn)鏈表了，而單節(jié)點(diǎn)鏈表可以被認(rèn)為是已經(jīng)排好序的。這時(shí)候再兩兩合并，最終會(huì)得到一個(gè)完整的已排序鏈表。用把排好序的兩個(gè)鏈表合并起來。 TL;DR 對(duì)鏈表進(jìn)行歸并排序，系列目錄見前言和目錄。需求實(shí)現(xiàn)函數(shù) mergeSort() 進(jìn)行歸并排序。注意這種排序法需要使用遞歸。在 fr...

X_AirDu 2019-08-20 14:23 評(píng)論0 收藏0
用 JavaScript 實(shí)現(xiàn)鏈表操作 - 13 Shuffle Merge

摘要：需求實(shí)現(xiàn)函數(shù)把兩個(gè)鏈表合并成一個(gè)。新鏈表的節(jié)點(diǎn)是交叉從兩個(gè)鏈表中取的。通過行的調(diào)換指針，我們可以保證下一次循環(huán)就是對(duì)另一個(gè)鏈表進(jìn)行操作了。這樣一直遍歷到兩個(gè)鏈表末尾，返回結(jié)束。參考資料的代碼實(shí)現(xiàn)的測(cè)試 TL;DR 把兩個(gè)鏈表洗牌合并成一個(gè)，系列目錄見前言和目錄。需求實(shí)現(xiàn)函數(shù) shuffleMerge() 把兩個(gè)鏈表合并成一個(gè)。新鏈表的節(jié)點(diǎn)是交叉從兩個(gè)鏈表中取的。這叫洗牌合并。舉...

shiguibiao 2019-08-20 14:21 評(píng)論0 收藏0
用 JavaScript 實(shí)現(xiàn)鏈表操作 - 09 Move Node

摘要：需求實(shí)現(xiàn)一個(gè)函數(shù)，把源鏈表的頭節(jié)點(diǎn)移到目標(biāo)鏈表。當(dāng)源鏈表為空時(shí)函數(shù)應(yīng)拋出異常。為了簡(jiǎn)化起見，我們會(huì)用一個(gè)對(duì)象來存儲(chǔ)改變后的源鏈表和目標(biāo)鏈表的引用。它也是函數(shù)的返回值。解法配合，這個(gè)非常簡(jiǎn)單，注意這個(gè)函數(shù)沒有改變兩個(gè)鏈表本身。 TL;DR 把一個(gè)鏈表的首節(jié)點(diǎn)移到另一個(gè)鏈表。系列目錄見前言和目錄。需求實(shí)現(xiàn)一個(gè) moveNode() 函數(shù)，把源鏈表的頭節(jié)點(diǎn)移到目標(biāo)鏈表。當(dāng)源鏈表為空時(shí)...

suosuopuo 2019-08-20 13:35 評(píng)論0 收藏0
用 JavaScript 實(shí)現(xiàn)鏈表操作 - 16 Sorted Intersect

摘要：需求實(shí)現(xiàn)函數(shù)取兩個(gè)已排序的鏈表的交集，交集指兩個(gè)鏈表都有的節(jié)點(diǎn)，節(jié)點(diǎn)不一定連續(xù)。每個(gè)鏈表應(yīng)該只遍歷一次。結(jié)果鏈表中不能包含重復(fù)的節(jié)點(diǎn)。當(dāng)我們對(duì)比和的值時(shí)，有這幾種情況，這時(shí)節(jié)點(diǎn)肯定交集，加入結(jié)果鏈表中。 TL;DR 一次遍歷取兩個(gè)排序鏈表的交集，系列目錄見前言和目錄。需求實(shí)現(xiàn)函數(shù) sortedIntersect() 取兩個(gè)已排序的鏈表的交集，交集指兩個(gè)鏈表都有的節(jié)點(diǎn)，節(jié)點(diǎn)不一定...

zhigoo 2019-08-20 14:25 評(píng)論0 收藏0