JavaScript Data Structures: Doubly Linked List: Intro and Setup

Intro

After completing the series about the Singly Linked List,

we start with the Doubly Linked List.

What is a Doubly Linked List?

  • the Doubly Linked List consists of nodes
  • each node has a value
  • each node has a pointer to the previous node (or null at the beginning of the list)
  • each node has a pointer to the next node (or null at the end of the list)
  • the List has a head (= beginning)
  • the List has a tail (= end)
  • the List has a length (= how many nodes are in the List)
  • the List has no index like an Array
  • "doubly" means every node has two connections (one to the previous node and one to the next node)

Example

A <===> B <===> C

  • A: prev: null
  • A: next: B
  • B: prev: A
  • B: next: C
  • C: prev: B
  • C: next: null

Big O of Doubly Linked List

  • Access: O(N)
  • Search: O(N)
  • Insert: O(1)
  • Delete: O(1)

Setup

// a Node has a value, a pointer to the previous node (= prev), a pointer to the next node (= next)
class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

// a Doubly Linked List has a length, a beginning (= head), an end (= tail)
class DoublyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }
}

Result

const newNode = new Node(1);
console.log(newNode);
// Node { value: 1, prev: null, next: null }

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

Next Part

We will implement our first method to the list.

If you want to get notified, subscribe!


Questions

  • What do you think is a suitable use case for a Doubly Linked List?
  • Can you find some advantages against a Singly Linked List?
  • Can you find some disadvantages against a Singly Linked List?