JavaScript Data Structures: Singly Linked List: Shift

Intro

Last time, we learned how to unshift / add something to the beginning of our Singly Linked List.

Today, we learn how to shift something from the list. Shift means remove something from the beginning.

Current Code

We start with the code after we added push(), because we want to keep the code as simple as possible to understand. We need push() to add some nodes to the List.

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

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

  push(value) {
    const newNode = new Node(value);
    if (this.length > 0) {
      this.tail.next = newNode;
    } else {
      this.head = newNode;
    }
    this.tail = newNode;
    this.length += 1;
    return newNode;
  }
}

Thoughts

First, we should think about the constraints and possibilities:

If there is currently NO other node in the Singly Linked List (so it is currently empty):

return null, because we can't remove anything from the beginning of the Singly Linked list

If there is 1 node in the Singly Linked List:

set the current head as the node we want to remove (nodeToRemove)
set the the 2nd node as the new head
decrease the List's length by 1
set the tail to null, because the List is empty now
return the nodeToRemove

If there is more than 1 node in the Singly Linked List:

set the current head as the node we want to remove (nodeToRemove)
set the the 2nd node as the new head
decrease the List's length by 1
return the nodeToRemove

Examples:

0 nodes: before: null (head & tail) => after: null (head & tail) (couldn't remove anything)
1 node: before: A (head & tail) => after: null (head & tail)
n nodes: before: A (head) -> B -> ... -> n (tail) => after: B (head) -> ... -> n (tail)

Differences:

there is only one difference: an additional step if there's only 1 node in the List

Implementation (Short version, DRY)

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

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

  push(value) {
    const newNode = new Node(value);
    if (!this.length) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.length += 1;
    return newNode;
  }

  shift() {
    // we can't remove anything from an empty List
    if (!this.length) {
      return null;
    } else {
      // set the current `head` as the node we want to remove (`nodeToRemove`)
      const nodeToRemove = this.head;

      // set the 2nd node as the new `head`
      this.head = this.head.next;

      // decrease the List's length by 1
      this.length -= 1;

      // if the List is empty now, there isn't a tail anymore
      if (!this.length) {
        this.tail = null;
      }

      // return the `nodeToRemove`
      return nodeToRemove;
    }
  }
}

Result

Let's have a look how to use the Singly Linked List shift method and its results.

const newSLL = new SinglyLinkedList();

// we can't remove from an empty list
console.log(newSLL.shift());

// add one node and remove it
newSLL.push("1st node");
console.log(newSLL.shift()); // Node { value: '1st node', next: null }
console.log(newSLL); // SinglyLinkedList { length: 0, head: null, tail: null }

// add two nodes and remove the first
newSLL.push("new 1st node");
newSLL.push("2nd node");
console.log(newSLL);
// SinglyLinkedList {
//   length: 2,
//   head: Node {
//     value: 'new 1st node',
//     next: Node { value: '2nd node', next: null }
//   },
//   tail: Node { value: '2nd node', next: null }
// }

console.log(newSLL.shift());
// Node {
//  value: 'new 1st node',
//  next: Node { value: '2nd node', next: null }
// }

console.log(newSLL);
// SinglyLinkedList {
//   length: 1,
//   head: Node { value: '2nd node', next: null },
//   tail: Node { value: '2nd node', next: null }
// }