Efficiently sorting linked list in Javascript?

Question

What's the most efficient way to sort a linked list in Javascript/NodeJS? If I have an array of objects with an id and comesAfter which refers to the id of the previous item in the list, how can I put it in order?

ES6 features in the solution are fine to use. And it shouldn't modify the original array but return a new one. (But if it's not difficult to show how to do it in place that could help to see too.)

// before sorting
[
  { id: "three", comesAfter: "two" },
  { id: "one", comesAfter: null },
  { id: "four", comesAfter: "three" },
  { id: "two", comesAfter: "one" },
]

// after sorting
[
  { id: "one", comesAfter: null },
  { id: "two", comesAfter: "one" },
  { id: "three", comesAfter: "two" },
  { id: "four", comesAfter: "three" },
]

Lajos Arpad · Accepted Answer · 2020-04-16 10:45:59Z

1

It seems reasonable to create an object, like this:

var obj = {};
for (var i = 0; i < input.length; i++) {
    obj[input[i].comesAfter] = input[i];
}

Now, let's generate the output:

var index = 0;
var output = [obj.null];
while (++index < input.length) {
    output[index] = obj[output[index - 1].id];
}

answered Apr 16, 2020 at 10:45

Lajos Arpad

80.4k42 gold badges122 silver badges234 bronze badges

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

Collectives™ on Stack Overflow

Efficiently sorting linked list in Javascript?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related