miku86

Posted on Dec 5, 2019

JavaScript Data Structures: Doubly Linked List: Push / Add data to the end

#webdev #tutorial #beginners #javascript

Intro

Last time, we learned how to setup our Doubly Linked List.

Today, we'll learn how to push a new node to the end of our Doubly Linked List.

Starter Code

We start with the setup code from the last post.

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
the new node should become the head and the tail
increase the List's length by 1
return new node

All remaining cases:

create a new node
the current tail should point forward (= next) to the new node
the new node should point back (= prev) to the current tail
the new node should become the new tail
increase the List's length by 1
return new node

Example: empty list

current List: empty (no head & tail)
desired List: A (head & tail)

Example 2: list with 1 node

current List: A (head & tail)
desired List: A (head) <===> B (tail)

Steps:

current List: A (head & tail)
desired List: A (head) <===> B (tail)
the current tail should point forward (= next) to the new node: A (head & tail) => B
the new node should point back (= prev) to the current tail: A (head & tail) <===> B
the new node should become the new tail: A (head) <===> B (tail)

=> list after last step equals the desired list

Implementation

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

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

    // if the list is empty,the new node should become the head and the tail
    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // the current tail should point forward (= next) to the new node
      this.tail.next = newNode;

      // the new node should point back (= prev) to the current tail
      newNode.prev = this.tail;

      // the new node should become the new tail
      this.tail = 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 push method and its results.

// empty list
const newDLL = new DoublyLinkedList();
console.log(newDLL);
// DoublyLinkedList { length: 0, head: null, tail: null }

// push first new node
console.log(newDLL.push("new node 1"));
//  Node { value: 'new node 1', prev: null, next: null }

console.log(newDLL);
//  DoublyLinkedList {
//    length: 1,
//    head: Node { value: 'new node 1', prev: null, next: null },
//    tail: Node { value: 'new node 1', prev: null, next: null }
//  }

// push second new node
console.log(newDLL.push("new node 2"));
// <ref *1> Node {
//   value: 'new node 2',
//   prev: Node { value: 'new node 1', prev: null, next: [Circular *1] },
//   next: null
// }

console.log(newDLL);
// DoublyLinkedList {
//   length: 2,
//   head: <ref *1> Node {
//     value: 'new node 1',
//     prev: null,
//     next: Node { value: 'new node 2', prev: [Circular *1], next: null }
//   },
//   tail: <ref *2> Node {
//     value: 'new node 2',
//     prev: <ref *1> Node {
//       value: 'new node 1',
//       prev: null,
//       next: [Circular *2]
//     },
//     next: null
//   }
// }

Next Part

We will implement our next method for the Doubly Linked List: pop / remove a node from the end.

If you want to get notified, subscribe!

Tasks

Do you spot some new stuff in the results?
What do they mean?

DEV Community