I'm having trouble understanding where the first node / old head in a linked list goes.

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

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
  push(val) {
        var newNode = new Node(val);
        if (!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length  ;
        return this;
    }
  shift() {
        if (!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if (this.length === 0) {
            this.tail = null;
        }
        return currentHead;
    }
}

I understand that we add a new variable for the old head, then move the head up to the next node, but where does the old head / previous node go? I see we return it, is that what's deleting it / removing it from the list? I know the code works, I'm just curious where that node goes.

CodePudding user response：

I'm using your code to create a singlyLinkedList which will hold the values for my HTML list.

When you hit shift, it runs the shift function, where your shift function is called.

You can see I'm assigning the value of the returned node (the old head) to the textContent of an element so you can see the returned value at the top.

The update function just syncs the list from your class with the HTML list.

function push() {
  const value = document.getElementById('input').value;
  value && list.push(value);
  update();
}

function shift() {
  // Below i'm using the returned value of shift (the head of the list),
  // otherwise it would be lost, and there would be no reference to it,
  // so it would be collected by the Garbage collector
  document.getElementById('shifted').textContent = list.shift().val;
  update();
}

function update() {
    const li = document.getElementById('list');
    li.innerHTML = '';
    let index = list.head;
    while (index) {
      const node = document.createElement('li');
      node.textContent = index.val;
      li.appendChild(node);
      index = index.next;
    }
}

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push(val) {
    var newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length  ;
    return this;
  }
  shift() {
    if (!this.head) return undefined;
    var currentHead = this.head;
    this.head = currentHead.next;
    this.length--;
    if (this.length === 0) {
      this.tail = null;
    }
    return currentHead;
  }
}

document.getElementById('push').addEventListener('click', push);
document.getElementById('shift').addEventListener('click', shift);

const list = new SinglyLinkedList();

// Adding some initial items to the list and displaying the list
list.push("1"); list.push("2"); list.push("3"); update();

<p>The Shifted/Returned node value is <span id="shifted">Undefined</span></p>
<button id="shift">Shift</button>

<label for="add">Add a node to the list</label>
<input id="input" name="add" type="text" />
<button id="push">Push</button>
<ul id="list">
</ul>

CodePudding user response：

The future of that node is in the hands of the code that called shift. If the caller ignores the returned reference, that node will become unreachable, and the garbage collector could decide to free its memory.

Let's say we have a linked list mylist with three nodes (with values 1, 2 and 3). The we can visualise it as follows (I omit length as it is not relevant to the question):

mylist
  ↓  
┌───────────┐  ┌───────────┐  ┌───────────┐  ┌───────────┐  
│ head: ──────>│ val: 1    │  │ val: 2    │  │ val: 3    │
│ tail: ─────┐ │ next: ──────>│ next: ──────>│ next: null│
└───────────┘│ └───────────┘  └───────────┘┌>└───────────┘
             └─────────────────────────────┘

Now when we call mylist.shift(), we assign to currentHead and change the value of head as follows:

mylist          currentHead
  ↓              ↓
┌───────────┐  ┌───────────┐  ┌───────────┐  ┌───────────┐  
│ head: ──────┐│ val: 1    │  │ val: 2    │  │ val: 3    │
│ tail: ─────┐││ next: ──────>│ next: ──────>│ next: null│
└───────────┘││└───────────┘┌>└───────────┘┌>└───────────┘
             │└─────────────┘              │ 
             └─────────────────────────────┘

So unless any other code holds a reference to the node with value 1, there is now only a local variable currentHead that references it. This variable will meet its end of life when the function returns, and as its value is returned, it is now up to the caller of the method to capture it.

So let's say the caller had done let node = mylist.shift(), then we would have this situation (I moved the boxes a bit):

node
  ↓
┌───────────┐ 
│ val: 1    │
│ next: ─────┐
└───────────┘│
mylist       │   
  ↓          │    
┌───────────┐└>┌───────────┐  ┌───────────┐  
│ head: ──────>│ val: 2    │  │ val: 3    │
│ tail: ─────┐ │ next: ──────>│ next: null│
└───────────┘│ └───────────┘┌>└───────────┘
             └──────────────┘

If however, we would just call shift without capturing the return value, like mylist.shift(), then there would be no more reference to that node with value 1:

┌───────────┐ 
│ val: 1    │
│ next: ─────┐
└───────────┘│
mylist       │   
  ↓          │    
┌───────────┐└>┌───────────┐  ┌───────────┐  
│ head: ──────>│ val: 2    │  │ val: 3    │
│ tail: ─────┐ │ next: ──────>│ next: null│
└───────────┘│ └───────────┘┌>└───────────┘
             └──────────────┘

In other words, there would be no way in JavaScript to somehow access that node. In that case the node is still there -- maybe for another millisecond, or a minute, or an hour -- but it is invisible to the program, and its fate is now completely in the hands of the garbage collector, which may decide at any moment to free the memory occupied by that node.