The idea is create a list of nodes that connects each other using 2 pointers: the pointer to next element and the pointer to preview element.

Doubly Linked Lists

doubly linked lists

Characteristics

The first node is called HEAD
Last node is called TAIL
The element points to the next element
The element points to the preview element
The first element previewPointer is null
The last element nextPointer is null

Performance in worst case

Fast insertion, fast deletion, ordered, flexible size, but It's slow to lookup and consumes more memory

O(n): Insert
O(n): Delete
O(n): lookup
O(1): append
O(1): prepend

Implementation

Let's start the implementation, the base logic of linked lists is find a way to update the head and tail pointer without lose information of preview and next.

Create a Node Class

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

Create a DoublyLinkedList class and set a constructor

class DoublyLinkedList {
  constructor (value) {
    this.head = {
      value: value,
      next: null,
      preview: null
    }
    this.tail = this.head;
    this.length = 1;
  }
}

Append method: Adding in the end of linked list

The logic here is follow these steps:

The new current node preview point to the last element(in this case, just point to tail pointer).
The current last element next pointer is updated with the new element to insert.
The tail node is updated with the new element.

  append (value) {
    const newNode = new Node(value);

    newNode.preview = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;

    this.length++;
    return this;
  }

Prepend method: Adding in the beginning

The logic to add in the beginning is:

Update the first element preview pointer of the list to new element.
Point the new element next pointer to the current first element (head pointer)
Update the head with the new element

  prepend (value) {
    const newNode = new Node(value);

    this.head.preview = newNode;
    newNode.next = this.head;
    this.head = newNode;
    this.length++;

    return this;
  }

TraverseToIndex method: find the Node by index

TraverseToIndex was created to make our insert and delete simple, the idea here is walk through each node until find the index passed as parameter.

Create a pointer and point to the first element (in case of linked. lists the first element is the head).
Create an auxiliary var to count each interaction of a loop that ends if auxiliary is same as index(passed as parameter).
In each interaction, update the currentPointer to the next element
After concludes the loop, currentNode will have the element of the index and we can return this Node

  traverseToIndex (index) {
    let counter = 0;
    let currentNode = this.head;

    while (counter !== index) {
      counter++;
      currentNode = currentNode.next;
    }

    return currentNode;
  }

Insert method: Add element in specified index

Check the particular cases: if the index indicates the first or last Node, use the append and prepend method to don't repeat this logic.
Use the tranverseToIndex function to find the preview element pointer(leaderNode) that you can add the new element.
Create a auxiliary var to get the next element pointer(followerNode) that you can add the new element
Point leaderNode.next to new element.
Point the new element preview pointer to leaderNode.
Point the new element next pointer to followerNode.
Point the followerNode.preview to new element.

  insert (index, value) {
    if (index >= this.length) {
      return this.append(value);
    } else if (index == 0) {
      return this.prepend(value);
    }

    const newNode = new Node(value);

    let leaderNode = this.traverseToIndex(index - 1);
    const followerNode = leaderNode.next

    leaderNode.next = newNode;
    newNode.preview = leaderNode;
    newNode.next = followerNode;
    followerNode.preview = newNode;

    return this;
  }

Remove Method: Remove Node from specified index

Check the particular cases: if the index indicates the first or last Node. Updates de head to be the next or tail to be the preview.
Use the traverseToIndex to find the leaderNode.
Create an auxiliary pointer to keep the node to remove.
Update the leaderNode.next with nodeToRemove.next.

  remove (index) {
    if (index == 0) {
      this.head = this.head.next
      this.head.preview = null
    } else if (index == this.length - 1) {
      const lasPos = this.length - 1
      const lastUpdatedLastNode = this.traverseToIndex(lasPos - 1);
      lastUpdatedLastNode.next = null;
    } else {
      const leaderNode = this.traverseToIndex(index - 1);
      const nodeToRemove = leaderNode.next;

      leaderNode.next = nodeToRemove.next;
    }
    this.length--;
  }

Reverse method: Invert the current linked list

The idea here is create auxiliary pointers and pass though the list inverting. the pointer values.

The particular case occurs if the list have just one element, in this case, just return the head
Create an auxiliary pointer that points to the first element (first).
We know that the first element will be the last, let's update the tail to the first element setting tail pointer to head.
Create an. auxiliary pointer that points to the second element (second).
Create a loop that iterates until second points will not be null(last element)
Each interaction, keep the second in a temp var to don't lost information of this pointer and keep the loop correctly.
Invert the position of second and first - step 1: Update the second next pointer to first.
Invert the position of second and first - step 2: Update the first element points to second.
Invert the position of second and first - step 3: Update the second element to be the temp(the next element)

  reverse () {
    if (!this.head.next) {
      return this.head;
    }

    let first = this.head;
    this.tail = this.head;
    let second = first.next;

    while (second) {
      const temp = second.next;
      second.next = first;
      first = second;
      second = temp;
    }

    this.head.next = null;
    this.head = first;

  }

PrintList method: Show the current linked list

Create an auxiliary pointer (currentNode) to points to the first element of the list.
Pass through each element until currentNode will not be the last element(null).
Update the currentNode to the next element.
To print the list you can just print element by element or save information in auxiliary array var and print then in the final.

  printList () {
    const array = [];
    let currentNode = this.head;

    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.next;
    }

    console.log(array);
  }

Example

const myLinkedList = new DoublyLinkedList(0);
myLinkedList.append(1);
myLinkedList.append(2);
myLinkedList.append(3);
myLinkedList.append(4);
myLinkedList.prepend(1);
myLinkedList.prepend(2);
myLinkedList.prepend(3);
myLinkedList.prepend(4);

myLinkedList.insert(5, 99);
myLinkedList.remove(4)
myLinkedList.reverse();
myLinkedList.printList();

Output

[ 4, 3, 2, 1, 0 ]

Visit Github implementation

References