CODEWITHSUNDEEP
javascriptdata-structures
fatih.jsx
fatih.jsx

Reputation: 88

how does this.tail.next adds node to this.head?

I am currently watching a tutorial about singly linked list and the tutor's implementation of singly linked list made me pretty confused for push method and i couldnt figure out what's going on.

here it is:

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(val) {
    let node = new Node(val);
    if (!this.head) {
      this.head = node;
      this.tail = this.head;
    } else {
      this.tail.next = node;
      this.tail = node;
    }

    this.length++;
    return this;
  }

let list = new SinglyLinkedList();
list.push('hello');
list.push('goodbye');
}

In this code, i am having really hard time to understand how this.tail.next inserts a new node to this.head. For the first insertion it's clear that both head and tail point to same object which is the first node. But after the first push, this.tail is assigned a new object and is not same with this.head but this.tail.next still adds new node to the last next property of this.head How is this happening?

Upvotes: 1

Views: 1344

Answers (2)

trincot
trincot

Reputation: 350310

It may help to visualise how things get done by the push method.

When the (empty) linked list is constructed with let list = new SinglyLinkedList(), we have this situation (I omit the length property, as it does not relate to the question):

 list (this)
  ↓
┌────────────┐
│ head: null │
│ tail: null │
└────────────┘

The main code then calls list.push('hello'). This starts with creating a node instance, and the local variable node references it:

 list              node
  ↓                 ↓
┌────────────┐    ┌──────────────┐
│ head: null │    │ val: "hello" │
│ tail: null │    │ next: null   │
└────────────┘    └──────────────┘

As this.head is null, the if block gets executed. First this.head = node results in this state:

 list              node
  ↓                 ↓
┌────────────┐    ┌──────────────┐
│ head: ────────> │ val: "hello" │
│ tail: null │    │ next: null   │
└────────────┘    └──────────────┘

And then that reference is copied into this.tail:

 list              node
  ↓                 ↓
┌────────────┐    ┌──────────────┐
│ head: ────────> │ val: "hello" │
│ tail: ────────> │ next: null   │
└────────────┘    └──────────────┘

After the length is updated, the push('hello') call has done its job and the node variable is disposed. Then list.push('goodbye') is executed. We again start by creating a node:

 list                                  node
  ↓                                     ↓
┌────────────┐    ┌──────────────┐    ┌────────────────┐
│ head: ────────> │ val: "hello" │    │ val: "goodbye" │
│ tail: ────────> │ next: null   │    │ next: null     │
└────────────┘    └──────────────┘    └────────────────┘

Now this.head is not null and so we get into the else block. this.tail.next = node is executed, and so we get (just follow the arrows from this to tail to next where the null is replaced with a reference to node):

 list                                  node
  ↓                                     ↓
┌────────────┐    ┌──────────────┐    ┌────────────────┐
│ head: ────────> │ val: "hello" │    │ val: "goodbye" │
│ tail: ────────> │ next: ──────────> │ next: null     │
└────────────┘    └──────────────┘    └────────────────┘

Then this.tail = node gets executed. This replaces an existing reference with another, restoring the invariant that list.tail always references the last node:

 list                                  node
  ↓                                     ↓
┌────────────┐    ┌──────────────┐    ┌────────────────┐
│ head: ────────> │ val: "hello" │    │ val: "goodbye" │
│ tail: ───────┐  │ next: ──────────> │ next: null     │
└────────────┘ │  └──────────────┘┌─> └────────────────┘ 
               └──────────────────┘

Again, the node variable's life ends at the end of the execution, and so we are left with list and the dependent structure depicted above.

Upvotes: 4

Felix Kling
Felix Kling

Reputation: 816522

But after the first push, this.tail is assigned a new object and is not same with this.head

That's not correct. After the first insertion, this.head and this.tail point to the same object:

if (!this.head) {
  this.head = node;
  this.tail = this.head;
}

For any subsequent insertion, this.tail points to the previously inserted node. this.tail.next is updated before the new node is assigned to this.tail:

this.tail.next = node;
this.tail = node;

That means when the second insertion happens, this.tail and this.head still point to the same object. this.tail.next = node is executed thus updating this.head.next as well. Only after that assignment is this.tail updated to point to the new node.

Upvotes: 2

Related Questions