2

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);

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.

How do you iterate through a linked list in javascript?

Improve this question
9
  • 2
    Well you built that linked list. Give it those methods that you long for. Commented Mar 26, 2018 at 23:45
  • I'm not a javascript expert yet. Would I do that using list.prototype.MyMethod? (not sure if I'm using the right terms aka method) Commented Mar 26, 2018 at 23:46
  • No, since they're not instances with a shared prototype but just plain objects. You'd assign the method directly to the list (or rather, each node object). Probably you should just start to write static functions which take the list as their first argument (which could also handle null - the "empty list" - properly). Commented Mar 26, 2018 at 23:49
  • There's no "documentation" for this as your linked lists are not a native data type. You'll probably find many tutorials though - and they don't even need to be JS necessarily, the structure of linked lists and the approach to iterate them is the same everywhere. Commented Mar 26, 2018 at 23:51
  • 1
    OK those look pretty terrible indeed. Yes, you could use prototype methods on that ListNode constructor. I would recommend trying to create a new list to be returned, not manipulating the old nodes, that'll be much simpler. Commented Mar 26, 2018 at 23:57

1 Answer 1

Reset to default
4

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);
}

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:

Observe that the linked list itself is:

  • Either the value null, or
  • A plain object with two fields, one field "value" which can be anything, and one field "next" which is a linked list.

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

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.

EDIT: 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).

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.
}

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

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

(value, next)=>({value: next, next: value}) = (next, value)=>({value, next})
@Jaromanda Nice catch! However, now that I think of it, although your idea is better than mine, I think there is an even better way to avoid further obscuring the code, which would be to use the parameters from reduceRight's callback in a similar way to the MDN docs (i.e., "prev" and "cur"), let me fix it. Thanks for inspiring me to the change.
Thank you so much for this! I agree that your solution is more clear, especially for other coders to read. I'll be working on solving this tonight, with your help! Thanks again
Figured it out! It's so simple with recursion! Great work
@TylerL Nice! If you think my answer helped, please consider accepting my answer (green checkmark).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.