Doubly Linked List

Explore the ins and outs of Doubly Linked List data structure in our latest blog post. From understanding the fundamentals to advanced techniques, discover how to leverage doubly linked list for optimal efficiency in your coding projects.

Series: Data Structures

Episodes: (5/6)

Introduction

A doubly linked list is a type of linked list where each node contains not only a reference or pointer to the next node in the sequence but also a reference or pointer to the previous node. This bidirectional connectivity allows traversal in both forward and backward directions within the list.

Implementation

class DoublyListNode<T> {
  val: T;
  left: DoublyListNode<T> | null;
  right: DoublyListNode<T> | null;
  constructor(val: T) {
      this.val = val;
      this.left = null;
      this.right = null;
  }
}
 
class DoublyLinkedList<T> {
  head: DoublyListNode<T> | null;
 
  constructor() {
    this.head = null;
  }
 
  append(val: T) {
    const newNode = new DoublyListNode(val);
    if (!this.head) {
        this.head = newNode;
        return;
    }
    let current = this.head;
    while (current.right) {
        current = current.right;
    }
    newNode.left = current;
    current.right = newNode;
  }
 
  display() {
    let current = this.head;
    while (current) {
      console.log(current.val);
      current = current.right;
    }
  }
 
  search(val: T): DoublyListNode<T> | null {
    let current = this.head;
    while (current) {
      if (current.val === val) return current;
      current = current.right;
    }
    return null
  }
 
  insertAtHead(val: T) {
    const newNode = new DoublyListNode(val);
    if (!this.head) {
        this.head = newNode;
        return;
    }
    newNode.right = this.head;
    this.head.left = newNode;
    this.head = newNode
  }
 
  deleteAtHead(): DoublyListNode<T> | null {
    if (this.head) {
      const deletedNode = this.head;
      this.head = this.head.right;
      return deletedNode;
    }
    return null;
  }
 
}