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

---

Next Part

We will implement how to get a specific node by its index. If you want to be notified, subscribe :)

---

Questions:

• Any ideas how to improve the post or code?
• Any specific questions?

Comments

[Raushan Sharma]

Thanks for your work, just one thing I see which I find unnecessary is the else block after even though you are already returning above.

 //  instead of this
 if (!this.length) {
      return null;
    } else { 
   // do something
    }

// we can simply write 
if (!this.length) return null;
// do something

[🅖🅡🅔🅖🅞🅡🅨 🅞🅡🅣🅞🅝]

Been following along with this as I really needed a refresher on my data structures which I skipped / barely implemented all those years ago at uni!

Implemented a demo her using closures / functions rather than classes, for people to browse a live version of the code: runkit.com/ortonomy/linkedlist-v1