Doubly Linked List

A doubly linked list is an extension of a linked list. In a doubly linked list, a list item points to both the next element and previous element in the list. We can perform all the same operations that we performed for a linked list:

Append

let currentNode = this.start;
while (currentNode.next !== null) {
  currentNode = currentNode.next;
}
currentNode.next = new DoublyLinkedListNode(item, currentNode===this.start ? null : currentNode, null);

Prepend

let currentNode = new DoublyLinkedListNode(item, this.start, this.start.next);
this.start.next.prev = currentNode;
this.start.next = currentNode;

Insert at an index

let currentNode = this.start;
let i = 0;
while (i !== index) {
  i++;
  currentNode = currentNode.next;
}
let nextNode = currentNode.next;
currentNode.next = new DoublyLinkedListNode(item, currentNode, nextNode);
nextNode.prev = currentNode.next;

Delete

let currentNode = this.start;
while (currentNode.next !== null) {
  if (currentNode.next.item === item) {
    currentNode.next = currentNode.next.next;
    currentNode.next.prev = currentNode;
    break;
  }
  currentNode = currentNode.next;
}

Search

let currentNode = this.start.next;
let index = 0;
while (currentNode !== null) {
  if (currentNode.item === item) {
    break;
  }
  index++;
  currentNode = currentNode.next;
}
return index < this.length() ? index : -1;

A doubly linked list gives the user more freedom while iterating the list. Let's take an example of music player where user is playing a song from a playlist.

Here user can navigate to the next or previous song. Let's say user plays the next song. We can handle this scenario by:

currentNode = currentNode.next;

User can also re-arrange the playlist. Let's say the user rearranges the above playlist:

We can achieve this by:

songsList.delete('Song 4');
songsList.insert('Song 4', 1);

This will delete the song from index 3 and add it to index 1.

Check out this link for implementation of this data structure using JavaScript.

Follow me on Twitter, Linkedin

Check out my portfolio at https://tejender-singh.github.io/