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 be 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?
Top comments (2)
i dont really see a use case for linked lists in a language like JS. In C/C++ you can't dynamically expand an array like you can in JS, so there is a use case there, but JS is more flexible and the cost of access is really high, so you're probably better off with JS alternatives like a simple array.
I'm curious what kind of use case exists for linked lists in JS :)
When you want to insert n delete from the beginning of a large array; it will be better to make use of a linked list instead because insertion n deletion from the beginning happen in constant time O(1) as compare to arrays which is O(n)