如何遍历JavaScript中的链表 [英] How to iterate through a linked list in javascript

问题描述

有人分享了这种精美绝妙的方法，可以从数组创建链接列表.

Someone shared this beautifully elegant way to create a linked list from an array.

function removeKFromList(l, k) {
  let list = l.reduceRight((value, next)=>({next, value}), null);
  console.log(list);
}

let l = [3, 1, 2, 3, 4, 5];
let k = 3;

removeKFromList(l, k);

迭代数组(用于，过滤，映射，缩小等)非常容易，但是链表没有这些功能.我需要遍历以从列表中删除k值.我猜我需要为当前节点创建一个变量并使用while循环，但是对此没有任何文档.我已经看到了一些repl代码来执行此操作，但它似乎不必要地复杂.

It's pretty easy to iterate arrays (for, filter, map, reduce, etc.) but a linked list has none of those features. I need to iterate through to remove k values from the list. I'm guessing I need to create a variable for the current node and use a while loop, but there's no documentation on this. I've seen some repl code doing it but it seems unnecessarily complicated.

您如何遍历javascript中的链接列表?

How do you iterate through a linked list in javascript?

推荐答案

首先，尽管使用reduce的想法确实很漂亮，但我必须说结果不是很好，因为结果节点具有一个字段""next"(下一个)是值，字段"value"(下一个是)，即它们被交换了.因此，我们来解决此问题:

First of all, although the idea of using reduce is indeed beautiful, I must say that the result is not so good, because the resulting nodes have a field "next" where the value is and a field "value" where the next is, i.e. they are swapped. So let's fix that:

function removeKFromList(l, k) {
    let list = l.reduceRight((value, next)=>({value: next, next: value}), null);
    console.log(list);
}

第二，该函数的名称太糟糕了，应将其命名为"arrayToLinkedList"或更具暗示性的名称.另外，记录结果没有意义，我们应该返回它.此外，参数k根本没有使用.解决这些问题:

Secondly, the name of that function is awful, it should be named "arrayToLinkedList" or something more suggestive. Also, logging the result does not make sense, we should return it instead. Moreover, the parameter k is simply unused. Fixing those things:

function arrayToLinkedList(array) {
    return array.reduceRight((prev, cur) => ({ value: cur, next: prev }), null);
}

现在，让我们研究如何对此进行迭代.你怎么看?我会给出一些提示，因为直接给出答案可能不会帮助您学到很多东西:

Now, let's work on how to iterate over this. What do you think? I will give some hints because giving the answer directly probably won't help you learn much:

观察到链表本身是:

• 值为 null 或
• 具有两个字段的普通对象，一个字段"value"可以是任何值，一个字段"next"是一个链表.

请注意，上面的(递归)定义是明确定义的，并且涵盖了所有情况.

Observe that the above (recursive) definition is well-defined and covers all cases.

现在，将其用于您的坚持.您如何获得第一价值?那就是 myList.value ，对吧?现在如何获得第二个值?通过应用 .next ，我们得到下一个链表，依此类推.如果 next 为null，则您必须停止.

Now, use that to your assistence. How do you get the first value? That would be simply myList.value, right? Now how do I get the second value? By applying .next, we get the next linked list, and so on. If next is null, you know you have to stop.

如果您需要进一步的帮助，请告诉我.

Let me know if you need further assistance.

编辑:我注意到您正在寻找一种正确的方法，以将其添加到原型"之类的方式在列表上进行迭代.因此，关于这一点:

I noticed that you're looking for the right way to make an iterating method on lists with an idea of "adding it to the prototype" or something. So, about that:

要通过原型添加实例方法，您需要将链接列表作为一个类.除非您确实有充分的理由为此定义一个类(这将围绕它创建多个方法和实用程序)，否则这将使情况变得复杂.

To add an instance method by a prototype, you'd need your linked lists to be a class. That would be overcomplicating, unless you really have a good reason to define a class for this (which would be creating several methods and utility things around it).

我认为，最好定义一个函数，该函数将一个链接列表作为第一个参数，并将回调函数作为第二个参数，类似于lodash的 .each :

It is much better, in my opinion, to just define a function that takes one linked list as the first parameter and a callback function as the second parameter, similarly to lodash's .each:

function forEachValueInLinkedList(linkedList, callback) {
     // here you loop through all values and call
     // callback(value)
     // for each value.
}

我想这将是最"javascriptonic"的方式.

I'd say this would be the most "javascriptonic" way to do it.

这篇关于如何遍历JavaScript中的链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！