Doubly Linked List

A doubly linked list is a linear data structure where each element (called a node) contains a data field and two pointers: one opinting to the next node, and another pointing to the previous node. This structure enabled bidirectional traversal, allowing you to move both forward and backward through the sequence.

Advantages and Disadvantages

Advantages

Bidirectional Deletion

The list can be iterated from head-to-tail or tail-to-head seamlessly.

Efficient Deletion

Removing a node is faster than a singly linked list if you already have a pointer to it, as yo udo not need to look up its predecessor.

Dynamic Allocation

Memory grows and shrinks at runtime without needing costly resizes like arrays.

Disadvantages

Memory Overhead

Every node consumes extra memory to store the additional pointer

Complex Bookkeeping

Insertion and deletion oeprations require adjusting up to four pointers, increasing the risk of code bugs.

No Random Access

Elements cannot be instanly reached via an index like arrays.

Node Structure

Every node in a doubly linked list consists of three distinct parts:

1. Previous Pointer

   Stores the memory address of the preceding node.

2. Data

   Holds the actual value or payload.

3. Next Pointer

   Stores the memory address of the succeeding node.

The previous poitner of the first node (head) and the next pointer of the last node (tail) point to Null to signify the boundaries of the list.

Time Complexity of Operations

Access/Search: \(O(n)\)

Must traverse nodes sequentially.

Insertion at Head/Tail: \(O(1)\)

Immediate insertion if pointers are maintained.

Insertion in Middle: \(O(n)\)

Requires finding the target location first.

Deletion of Given Node: \(O(1)\)

No sequential lookup needed to find the preceding node.

Implementation

C++Python

#include <iostream>

struct Node {
  int data;
  Node *next;
  Node *previous;

  Node(int data) : data(data), next(nullptr), previous(nullptr) {}
};

class LinkedList {
  private:
    Node *head;
    Node *tail;

  public:
    LinkedList() : head(nullptr), tail(nullptr) {}

    ~LinkedList() {
      clear();
    }

    void append(int data) {
      Node *node = new Node(data);
      if (head == nullptr) {
        head = node;
        tail = node;
        return;
      }
      tail->next = node;
      node->previous = tail;
      tail = node;
    }

    void clear() {
      Node *current = head;
      while (current != nullptr) {
        Node *next = current->next;
        delete current;
        current = next;
      }
      head = nullptr;
    }

    void deleteNode(int data) {
      Node *current = head;
      while (current != nullptr) {
        if (current->data != data) {
          current = current->next;
          continue;
        }
        if (current == head) {
          head = current->next;
          if (head != nullptr) {
            head->previous = nullptr;
          } else {
            tail = nullptr;
          }
        } else if (current == tail) {
          tail = current->previous;
          tail->next = nullptr;
        } else {
          current->previous->next = current->next;
          current->next->previous = current->previous;
        }
        delete current;
        return;
      }
    }

    void displayBackward() {
      Node *current = tail;
      while (current != nullptr) {
        std::cout << current->data << " <-> ";
        current = current->previous;
      }
      std::cout << "nullptr" << std::endl;
    }

    void displayForward() {
      Node *current = head;
      while (current != nullptr) {
        std::cout << current->data << " <-> ";
        current = current->next;
      }
      std::cout << "nullptr" << std::endl;
    }

    void prepend(int data) {
      Node *node = new Node(data);
      if (head == nullptr) {
        head = node;
        tail = node;
        return;
      }
      head->previous = node;
      node->next = head;
      head = node;
    }
};