loading...

JavaScript Data Structures: Singly Linked List: Push

miku86 profile image miku86 ・4 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 setup our Singly Linked List.

Today, we learn how to push something to the list. Push means add something to the end.

Recap from last time

  • we created a class Node
  • we created a class Singly Linked List
  • we learned how to create an instance of the Node class
  • we learned how to create an instance of the Singly Linked List class

Current Code

// name of the class
class Node {
  // the constructor runs when using the class with `new` (see later)
  constructor(value) {
    // set this nodes value property to the instantiation value
    this.value = value;
    // set this nodes next property to `null`
    this.next = null;
  }
}

// name of the class
class SinglyLinkedList {
  // the constructor runs when using the class with `new`
  constructor() {
    // set this lists length property to `0`
    this.length = 0;
    // set this lists head property to `null`
    this.head = null;
    // set this lists tail property to `null`
    this.tail = null;
  }
}

Thoughts

First, we should think about the constraints and possibilities:

If there is already at least one other node in the Singly Linked List:

  • create a new node with an input value
  • point the current tails next property to the new node (so the new node comes after the current tail)
  • set the Singly Linked List's tail to the new node
  • increase the Singly Linked List's length by 1
  • return the new node (so that we knew what we added)

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

  • create a new node with an input value
  • set the Singly Linked List's head to the new node
  • set the Singly Linked List's tail to the new node
  • increase the Singly Linked List's length by 1
  • return the new node (so that we knew what we added)

The differences?

  • if the Singly Linked List is empty, we need a head (the new node, because it is the only node)
  • if the Singly Linked List already has at least one node, the last node should point to the new node and this new last node is the new tail

Example:

  • 0 nodes: before: null (head & tail) => after: A (head & tail)
  • 1 node: before: A (head & tail) => after: A (head) -> B (tail)
  • 2 nodes: before: A (head) -> B (tail) => after: A (head) -> B -> C (tail)
  • n nodes: before: A (head) -> ... -> n (tail) => after: A (head) -> ... -> n -> n+1 (tail)

So A always stays the head, only if we got 0 nodes, we have to set A as the new head.
In every other situation, we have to point the current tail to the new node and make the new node the new tail.

Implementation (Long version, no DRY)

  • Comments from section Thoughts
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  push(value) {
    /*
     * 1. If there is already at least one other node in the Singly Linked List
     */
    if (this.length > 0) {
      // create a new node with an input value
      const newNode = new Node(value);
      // point the current tails `next` property to the new node
      this.tail.next = newNode;
      // set the Singly Linked List's `tail` to the new node
      this.tail = newNode;
      // increase the Singly Linked List's length by 1
      this.length += 1;
      // return the new node
      return newNode;
    } else {
      /*
       * 2. If there is currently NO other node in the Singly Linked List (so it is currently empty):
       */
      // create a new node with an input value
      const newNode = new Node(value);
      // set the Singly Linked List's `head` to the new node
      this.head = newNode;
      // set the Singly Linked List's `tail` to the new node
      this.tail = newNode;
      // increase the Singly Linked List's length by 1
      this.length += 1;
      // return the new node (so that we knew what we added)
      return newNode;
    }
  }
}

Implementation (Short version, DRY)

  • we have a lot of duplicate code, because most of the logic is the same
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;
  }
}

Result

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

const newSLL = new SinglyLinkedList();
console.log(newSLL);
/*
 * SinglyLinkedList {
 *   length: 0,
 *   head: null,
 *   tail: null
 * }
 */

newSLL.push("A");
console.log(newSLL);
/*
 * SinglyLinkedList {
 *   length: 1,
 *   head: Node { value: 'A', next: null },
 *   tail: Node { value: 'A', next: null }
 * }
 */

newSLL.push("B");
console.log(newSLL);
/*
 * SinglyLinkedList {
 *   length: 2,
 *   head: Node { value: 'A', next: Node { value: 'B', next: null } },
 *   tail: Node { value: 'B', next: null }
 * }
 */

Next Part

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

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 Nov 16 '19 by:

miku86 profile

miku86

@miku86

Mentor & Educator & Web Developer - I help people to reach their (career) goals. => https://miku86.com/mentoring

Discussion

markdown guide