Search code examples
javascriptdata-structureslinked-listsingly-linked-list

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

Solution

  • 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