JavaScript Data Structures: Singly Linked List: Unshift

Intro

Last time, we learned how to pop a new node from the end of our Singly Linked List.

Today, we learn how to unshift something to the list. Unshift means add something to the beginning.

Current Code

We start with the code from the setup, without push and pop, because we want to keep the code as simple as possible to understand.

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

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

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):

create a new node
set the new node as the Singly Linked List's tail
set the new node as the Singly Linked List's head
increase the Singly Linked List's length by 1
return the new node

If there is at least 1 node in the Singly Linked List:

create a new node
set the new node's next to the Singly Linked List's current head
set the new node as the Singly Linked List's head
increase the Singly Linked List's length by 1
return the new node

Examples:

0 nodes: before: null (head & tail) => after: A (head & tail)
1 node: before: A (head & tail) => after: A-1 (head) -> A (tail)
n nodes: before: A (head) -> ... -> n (tail) => after: A-1 (head) -> A -> ... -> n (tail)

Differences:

there is only one difference: the step after creating a new node

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

  unshift(value) {
    // create a new node
    const newNode = new Node(value);

    // check if Singly Linked List is empty
    if (!this.length) {
      // set the new node as the Singly Linked List's `tail`
      this.tail = newNode;
    } else {
      // set the new node's `next` to the Singly Linked List's current `head`
      newNode.next = this.head;
    }

    // set the new node as the Singly Linked List's `head`
    this.head = newNode;

    // increase the Singly Linked List's length by 1
    this.length += 1;

    // return the new node
    return newNode;
  }
}

Result

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

const newSLL = new SinglyLinkedList();

// should be empty
console.log(newSLL);
// SinglyLinkedList { length: 0, head: null, tail: null }

console.log(newSLL.unshift("1"));
// Node { value: '1', next: null }

// should be a list with the new node with value 1
console.log(newSLL);
/*
 *  SinglyLinkedList {
 *    length: 1,
 *    head: Node { value: '1', next: null },
 *    tail: Node { value: '1', next: null }
 *  }
 */

console.log(newSLL.unshift("2"));
// Node { value: '2', next: Node { value: '1', next: null } }

// should be a list with the new node with value 2 and 1 (from the last unshift)
console.log(newSLL);
/*
 *  SinglyLinkedList {
 *    length: 2,
 *    head: Node { value: '2', next: Node { value: '1', next: null } },
 *    tail: Node { value: '1', next: null }
 *  }
 */