用 JavaScript 实现链表操作 - 前言和目录

BetaRabbit 发布于2019-08-20 12:25 / 1095人阅读

摘要：我打算写一个链表操作的系列，来自的系列，实现语言是。通过自己实现一个链表和常用操作，可以加深理解这类数据结构的优缺点。链表经常用来训练指针操作，虽然这只对适用，但等高级语言中控制引用的思路其实也差不多。

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

云服务器服务器托管用javascript操作xml 多链表c语言实现 java实现链表插入遍历c语言实现链表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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