How to make a linked list from an array in Javascript

Question

Here's the basic code

function ListNode(x) {
  this.value = x;
  this.next = null;
}

function linkedList(arr){
  let list = new ListNode(arr[0]);
  
  let selectedNode = list;
  for(let i = 1; i < arr.length; i++){
    selectedNode.next = new ListNode(arr[i]);
    selectedNode = selectedNode.next
  } 

  return list
}

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

console.log(linkedList(l));

For some reason, it just works. I don't get how the 'list' variable is changing/updating in linkedList(arr) function. I see selectedNode = list, but list never changes. list initializes with the constructor new ListNode(arr[0]) but after that, the only variable that's changing is selectedNode. There isn't even code for list.next to change to something.

So how is it that return list returns the full linked list?

The list variable points to the head of the list. Then it sets selectednode to point to the head also. By setting select nodes next to point to a new node, it is changing the same top node that list is pointing to. The. Selectnode moved to that new next node and it keeps linking more and more nodes. All the while list is still pointing to that first node. — Mike Wodarczyk, Mar 25 '18 at 01:58
It's just how `LinkedList` works, concept-wise. You only need to have a pointer to the **head** node. The *list* results by setting new nodes to the `next` pointer of nodes. So in the end you have a chain where your `head` points with `head.next` to another node and this node again points to some node with its `next` variable and so on. You can also clearly see this in the output, it's a *nested structure*. — Zabuzard, Mar 25 '18 at 02:02

score 17 · Answer 1 · answered Mar 25 '18 at 02:27

17

function linkedList(arr){
  return arr.reduceRight((next, value) => ({value, next}), null);
}

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

console.log(linkedList(l));

you don't need the class ListNode for such a simple object.

answered Mar 25 '18 at 02:27

Thomas

11,958
1
14
23

1

Please give explanation... – Battledash2 Dec 30 '21 at 22:06

Ele · Accepted Answer · 2018-03-25T02:28:05.637

When you do this let selectedNode = list; two variables are pointing to the same value in memory, in this case, list and selectedNode. So, the chain of modifications starts with list and downstream adding new linked nodes.

The author has initialized the selectedNode with list as a starting point (root node) of the linked list.

This how looks like the memory with this let selectedNode = list;

  +-----------------+------------------+
  |       list      |  selectedNode    |
  +-----------------+------------------+
  |                 |         |        |
  |   {value: 3,    |         |        |
  |    next: null } <---------+        |
  |                 |                  |    
  +-----------------+------------------+

So, every iteration will modify the same list object because the next node is bound/linked with the previous nodes:

selectedNode.next = new ListNode(arr[i]);  i = 1
+-------------------+------------------+
|       list        |  selectedNode    |
+-------------------+------------------+
|                   |            |     |
|   {               |            |     |
|     value: 3,     | Points to  |     |
|     next: {       | next       |     |
|        value: 1   <------------+     |
|        next: null |                  |
|      }            |                  |
|   }               |                  |
|                   |                  |    
+-------------------+------------------+

selectedNode.next = new ListNode(arr[i]);  i = 2
+-----------------------+------------------+
|       list            |  selectedNode    |
+-----------------------+------------------+
|                       |            |     |
|   {                   |            |     |
|     value: 3,         |            |     |
|     next: {           |            |     |
|        value: 1       | Points to  |     |
|        next: {        | next       |     |
|           value: 2,   <------------+     |
|           next: null  |                  |
|         }             |                  |
|     }                 |                  |
|   }                   |                  |
|                       |                  |    
+-----------------------+------------------+

And so on.

I think I see. So by adding new to list, you make it a constructor instead of a variable containing a value. Still trying to figure out how returning list returns all the other variables, but I'll keep re-reading until I understand — Tyler L, Mar 25 '18 at 02:01
It returns the whole thing because when you `selectedNode = selectedNode.next`, it is also still the same in memory. In the next iteration, when you change the new `selectedNode`, you're actually changing the old `selectedNode`'s `next` key, which is actually changing `list`. — Oliver Ni, Mar 25 '18 at 02:05
lol thanks Oliver. This is so confusing. I've never seen javascript share variables like this. Edit: Is there a tutorial/similar SO question I can read to elaborate on this? — Tyler L, Mar 25 '18 at 02:06
@TylerL hold on, I think with a graphic you will understand. — Ele, Mar 25 '18 at 02:08
@TylerL take a look at the updated answer. Let me know if you understand. — Ele, Mar 25 '18 at 02:28
Ah! That's super helpful! Thank you for helping me understand this. — Tyler L, Mar 25 '18 at 02:37

score 1 · Answer 3 · answered Mar 25 '18 at 02:10

1

When you assign an object type to a variable, the variable's value isn't the actual object but rather a reference to it. Therefore, when you do selectedNode = list both variables reference the same object and any changes to this object, using any of the references to it, will be visible from any of its references.
In short: the list variable doesn't change but the object it's referencing does.

answered Mar 25 '18 at 02:10

Lennholm

7,205
1
21
30

So in the loop, when selectedNode.next changes, it's really changing list! What about having multiple linked lists using the same constructor function? Not possible? – Tyler L Mar 25 '18 at 02:13
1

@TylerL Oh, it's definitely possible. If by constructor function you're talking about the `linkedList(arr) {}` function (which is more of a factory function), every call to it creates a new linked list since the `list` variable is local to the function and every function call has its own instance. – Lennholm Mar 25 '18 at 02:21

How to make a linked list from an array in Javascript

3 Answers3