用 JavaScript 實現鏈表操作 - 前言和目錄

BetaRabbit 發布于2019-08-20 12:25 / 1250人閱讀

摘要：我打算寫一個鏈表操作的系列，來自的系列，實現語言是。通過自己實現一個鏈表和常用操作，可以加深理解這類數據結構的優缺點。鏈表經常用來訓練指針操作，雖然這只對適用，但等高級語言中控制引用的思路其實也差不多。

TL;DR

我打算寫一個鏈表操作的系列，來自 Codewars 的 Linked List 系列 kata ，實現語言是 JavaScript 。這篇是開篇，簡單描述了一下我寫這個的目的，也作為系列的目錄。

為什么要學習鏈表

我的年度目標之一就是學習一些數據結構和算法，用于打基礎和培養邏輯思維能力。Codewars 上的這個系列同時符合這兩點。

鏈表是常用數據結構之一，它甚至是某些語言（比如 Elixir）的內置數據結構。通過自己實現一個鏈表和常用操作，可以加深理解這類數據結構的優缺點。

鏈表經常用來訓練指針操作，雖然這只對 C 適用，但 JavaScript 等高級語言中控制引用的思路其實也差不多。而且鏈表也是練習遞歸的理想數據結構之一。

基于此，每個 kata 我都會盡量提供遞歸和循環兩個版本，某些操作會實現尾遞歸以符合題目要求。這是一個很有意思的過程，有時候遞歸更好，有時候循環更好，也有少數時候兩者都不是最優化的方案。

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

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云服務器云服務器用javascript操作xml 多鏈表c語言實現 java實現鏈表插入遍歷c語言實現鏈表

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

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

用 JavaScript 實現鏈表操作 - 06 Insert Sort

摘要：需求實現一個函數對鏈表進行升序排列插入排序。關于插入排序插入排序的介紹可以看，大體邏輯為建立一個新的空鏈表。遍歷完成，返回新鏈表。代碼如下總結因為有上個的函數的幫助，這個插入排序實現起來非常簡單。 TL;DR 2016 年末最后一篇，對鏈表進行插入排序。系列目錄見前言和目錄。需求實現一個 insertSort() 函數對鏈表進行升序排列（插入排序）。實現過程中可以使用上一個 ...

doodlewind 2019-08-21 11:28 評論0 收藏0
用 JavaScript 實現鏈表操作 - 15 Merge Sort

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

X_AirDu 2019-08-20 14:23 評論0 收藏0
用 JavaScript 實現鏈表操作 - 13 Shuffle Merge

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

shiguibiao 2019-08-20 14:21 評論0 收藏0
用 JavaScript 實現鏈表操作 - 09 Move Node

摘要：需求實現一個函數，把源鏈表的頭節點移到目標鏈表。當源鏈表為空時函數應拋出異常。為了簡化起見，我們會用一個對象來存儲改變后的源鏈表和目標鏈表的引用。它也是函數的返回值。解法配合，這個非常簡單，注意這個函數沒有改變兩個鏈表本身。 TL;DR 把一個鏈表的首節點移到另一個鏈表。系列目錄見前言和目錄。需求實現一個 moveNode() 函數，把源鏈表的頭節點移到目標鏈表。當源鏈表為空時...

suosuopuo 2019-08-20 13:35 評論0 收藏0
用 JavaScript 實現鏈表操作 - 16 Sorted Intersect

摘要：需求實現函數取兩個已排序的鏈表的交集，交集指兩個鏈表都有的節點，節點不一定連續。每個鏈表應該只遍歷一次。結果鏈表中不能包含重復的節點。當我們對比和的值時，有這幾種情況，這時節點肯定交集，加入結果鏈表中。 TL;DR 一次遍歷取兩個排序鏈表的交集，系列目錄見前言和目錄。需求實現函數 sortedIntersect() 取兩個已排序的鏈表的交集，交集指兩個鏈表都有的節點，節點不一定...

zhigoo 2019-08-20 14:25 評論0 收藏0