miku86

Intro

Last time, we learned how to pop / remove data from end of our Doubly Linked List.

Today, we'll learn how to unshift / add data to the beginning of our Doubly Linked List.

Starter Code

We start with the setup code.

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

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

Thoughts

First, we should think about the constraints and possibilities:

If the list is empty:

• create a new node
• set the new node as the new head and tail
• increase length by 1
• return the new node

All remaining cases:

• create a new node
• set new node's next to current head
• set the current head's prev to new node
• set list's head to new node
• increase length by 1
• return the new node

Differences:

• we can see some duplication (create node, increase length, return node)

Example: three nodes

// current list:
               A (head) <===> B (tail)

// desired list:
0 (head) <===> A        <===> B (tail)

Steps:

// current list:
               A (head) <===> B (tail)

// set new node's next to current head
0          ==> A (head) <===> B (tail)

// set the current head's prev to new node
0        <===> A (head) <===> B (tail)

// set list's head to new node
0 (head) <===> A        <===> B (tail)

// desired list:
0 (head) <===> A        <===> B (tail)

=> list after last step equals the desired list

Implementation (Short)

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

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

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

    // if list is empty: set head and tail to new node
    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // set new node's next to current head
      newNode.next = this.head;

      // set the current head's prev to new node
      this.head.prev = newNode;

      // set list's head to new node
      this.head = newNode;
    }

    // increase length by 1
    this.length += 1;

    // return new node
    return newNode;
  }
}

Result

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

const newDLL = new DoublyLinkedList();
newDLL.push("A");

// should be a list with one node
console.log(newDLL);
// DoublyLinkedList {
//   length: 1,
//   head: Node { value: 'A', prev: null, next: null },
//   tail: Node { value: 'A', prev: null, next: null }
// }

// should be the new node
console.log(newDLL.unshift("0"));
// <ref *1> Node {
//   value: '0',
//   prev: null,
//   next: Node { value: 'A', prev: [Circular *1], next: null }
// }

// should be a list with two nodes, node with value 0 at the beginning
console.log(newDLL);
// DoublyLinkedList {
//   length: 2,
//   head: <ref *1> Node {
//     value: '0',
//     prev: null,
//     next: Node { value: 'A', prev: [Circular *1], next: null }
//   },
//   tail: <ref *2> Node {
//     value: 'A',
//     prev: <ref *1> Node {
//       value: '0',
//       prev: null,
//       next: [Circular *2]
//     },
//     next: null
//   }
// }

Next Part

We will implement our next method for the Doubly Linked List: shift / remove data from the beginning.

If you want to get notified, subscribe!