Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

LinkedList push() method in JavaScript with a tail

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 } }
like image 775
Elchin Avatar asked Aug 01 '26 03:08

Elchin


1 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
like image 111
trincot Avatar answered Aug 02 '26 18:08

trincot



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!