用 JavaScript 实现链表操作 - 01 Push & Build List

Scorpion 发布于2019-08-20 12:35 / 1297人阅读

摘要：写两个帮助函数来创建链表。用于把一个节点插入到链表的头部。这个方法应该始终返回一个新的链表。接收一个数组为参数，创建对应的链表。参考资料的代码实现的测试

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语言实现

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

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