loading...

JavaScript Data Structures: Singly Linked List: Unshift

miku86 profile image miku86 Updated on ・3 min read

JavaScript Data Structures (40 Part Series)

1) JavaScript Data Structures: Singly Linked List 2) JavaScript Data Structures: Singly Linked List: Setup 3 ... 38 3) JavaScript Data Structures: Singly Linked List: Push 4) JavaScript Data Structures: Singly Linked List: Pop 5) JavaScript Data Structures: Singly Linked List: Unshift 6) JavaScript Data Structures: Singly Linked List: Shift 7) JavaScript Data Structures: Singly Linked List: Get 8) JavaScript Data Structures: Singly Linked List: Set 9) JavaScript Data Structures: Singly Linked List: Insert 10) JavaScript Data Structures: Singly Linked List: Remove 11) JavaScript Data Structures: Singly Linked List: Recap 12) JavaScript Data Structures: Doubly Linked List: Intro and Setup 13) JavaScript Data Structures: Doubly Linked List: Push / Add data to the end 14) JavaScript Data Structures: Doubly Linked List: Pop / Remove data from the end 15) JavaScript Data Structures: Doubly Linked List: Unshift / Add data to the beginning 16) JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning 17) JavaScript Data Structures: Doubly Linked List: Get a specific node by its index 18) JavaScript Data Structures: Doubly Linked List: Set / Update a specific node 19) JavaScript Data Structures: Doubly Linked List: Insert a new node at a specific index 20) JavaScript Data Structures: Doubly Linked List: Remove a node at a specific index 21) JavaScript Data Structures: Doubly Linked List: Recap 22) JavaScript Data Structures: Stack: Intro 23) JavaScript Data Structures: Stack: Push / Add a new node 24) JavaScript Data Structures: Stack: Pop / Remove the last node 25) JavaScript Data Structures: Stack: Recap 26) JavaScript Data Structures: Queue: Intro 27) JavaScript Data Structures: Queue: Enqueue 28) JavaScript Data Structures: Queue: Dequeue 29) JavaScript Data Structures: Queue: Recap 30) JavaScript Data Structures: Recap: Lists, Stack, Queue 31) JavaScript Data Structures: Hash Table: Intro 32) JavaScript Data Structures: Hash Table: Hash Function 33) JavaScript Data Structures: Hash Table: Collisions 34) JavaScript Data Structures: Hash Table: Setup 35) JavaScript Data Structures: Hash Table: Add data 36) JavaScript Data Structures: Hash Table: Get data 37) JavaScript Data Structures: Hash Table: Get keys 38) JavaScript Data Structures: Hash Table: Get values 39) JavaScript Data Structures: Hash Table: Get all entries 40) JavaScript Data Structures: Hash Table: Recap

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

Next Part

We will implement how to remove a node from the beginning of the Singly Linked List. If you want to be notified, subscribe :)


Questions:

  • Any ideas how to improve the post or code?
  • Any specific questions?
  • Do you like the series or is it useless? Why?

JavaScript Data Structures (40 Part Series)

1) JavaScript Data Structures: Singly Linked List 2) JavaScript Data Structures: Singly Linked List: Setup 3 ... 38 3) JavaScript Data Structures: Singly Linked List: Push 4) JavaScript Data Structures: Singly Linked List: Pop 5) JavaScript Data Structures: Singly Linked List: Unshift 6) JavaScript Data Structures: Singly Linked List: Shift 7) JavaScript Data Structures: Singly Linked List: Get 8) JavaScript Data Structures: Singly Linked List: Set 9) JavaScript Data Structures: Singly Linked List: Insert 10) JavaScript Data Structures: Singly Linked List: Remove 11) JavaScript Data Structures: Singly Linked List: Recap 12) JavaScript Data Structures: Doubly Linked List: Intro and Setup 13) JavaScript Data Structures: Doubly Linked List: Push / Add data to the end 14) JavaScript Data Structures: Doubly Linked List: Pop / Remove data from the end 15) JavaScript Data Structures: Doubly Linked List: Unshift / Add data to the beginning 16) JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning 17) JavaScript Data Structures: Doubly Linked List: Get a specific node by its index 18) JavaScript Data Structures: Doubly Linked List: Set / Update a specific node 19) JavaScript Data Structures: Doubly Linked List: Insert a new node at a specific index 20) JavaScript Data Structures: Doubly Linked List: Remove a node at a specific index 21) JavaScript Data Structures: Doubly Linked List: Recap 22) JavaScript Data Structures: Stack: Intro 23) JavaScript Data Structures: Stack: Push / Add a new node 24) JavaScript Data Structures: Stack: Pop / Remove the last node 25) JavaScript Data Structures: Stack: Recap 26) JavaScript Data Structures: Queue: Intro 27) JavaScript Data Structures: Queue: Enqueue 28) JavaScript Data Structures: Queue: Dequeue 29) JavaScript Data Structures: Queue: Recap 30) JavaScript Data Structures: Recap: Lists, Stack, Queue 31) JavaScript Data Structures: Hash Table: Intro 32) JavaScript Data Structures: Hash Table: Hash Function 33) JavaScript Data Structures: Hash Table: Collisions 34) JavaScript Data Structures: Hash Table: Setup 35) JavaScript Data Structures: Hash Table: Add data 36) JavaScript Data Structures: Hash Table: Get data 37) JavaScript Data Structures: Hash Table: Get keys 38) JavaScript Data Structures: Hash Table: Get values 39) JavaScript Data Structures: Hash Table: Get all entries 40) JavaScript Data Structures: Hash Table: Recap

Posted on Aug 24 '19 by:

miku86 profile

miku86

@miku86

Developer & Explorer with a passion for web development, learning and the world we live in | Need some mentoring? => https://miku86.com/mentoring

Discussion

markdown guide