LinkedList push() method in JavaScript with a tail

user_13910107 0
Viewed 808

I try to understand how push() method works with the use of tails in JS. here is the code:

class Node {
    constructor(val) {
      this.val = val;
      this.next = null;
    }
  }
  class SinglyLinkedList {
    constructor() {
      this.length = 0;
      this.head = null;
      this.tail = null;
    }
    push(val) {
      const newNode = new Node(val)
      if (this.head===null) { // happens only once
        this.head = newNode;
        this.tail = this.head;
      } else {
        this.tail.next = newNode;   // this.a.next = b node???
        this.tail = newNode;
      }
      this.length++
    }

specifically, I don't understand the else part inside the push() method. How does each next of a head gets assigned a new node if we say this.tail.next = newNode? Where is the relation between head and tail and how by saying this.tail.next = newNode we get access to the head property of the list? When I run this code, it works perfectly correct and it confuses me.

const myList = new SinglyLinkedList();
  myList.push("111");
  myList.push("222");
  myList.push("333");
  console.log(myList);

Output:

SinglyLinkedList {
  length: 3,
  head: Node { val: '111', next: Node { val: '222', next: [Node] } },
  tail: Node { val: '333', next: null } }
singly-linked-list data-structures linked-list javascript
2 Answers

How does each next of a head gets assigned a new node if we say this.tail.next = newNode? Where is the relation between head and tail and how by saying this.tail.next = newNode we get access to the head property of the list?

Lets go back to the empty list. The first time a node is added, we get into the if block, where both head and tail will reference the same new node. This means that from that moment on, whatever you mutate in tail will be mutating head, since they refer to the same object.

Now a second push is executed and we get in the else block. There we assign the new node to the next property of tail. But since this is the same object that head refers to, we actually set head.next here! This only happens with the second push, because right after this assignment, tail is assigned a new reference (next) so from then on head and tail refer to different nodes.

Graphically:

After push('111'):

head
 ↓
111
 ↑
tail

When push('222'), after this.tail.next = newNode;:

head
 ↓
111 → 222
 ↑
tail

...and after this.tail = newNode; during that same push:

head
 ↓
111 → 222
       ↑
     tail

When push('333'), after this.tail.next = newNode;:

head
 ↓
111 → 222 → 333
       ↑
     tail

...and after this.tail = newNode; during that same push:

head
 ↓
111 → 222 → 333
             ↑
           tail
user_54598390

Okay I'll give it a try in explaining why that is.

  1. When you push the first time, both head and tail refers to the same node.
  2. Then when you push the second time, this.tail.next = newNode adds the new node to both head and tail's next property.
  3. Then this.tail = newNode updates the tail's node which leaves the head's next to be the same as tail.

If you want to check step 2 above, comment out this.tail = newNode and push twice. You will see both head and tail's next property is same.

user_117642980
Related