Singly Linked Lists

A singly linked list is a data structure where each node contains a piece of data and a pointer to the next node in the sequence. The final node in the list points to null, signifying the end of the list. This structure is linear and unidirectional, meaning traversal is only possible from the first node to the last.

Here is a simple illustration of a singly linked list:
[Data] -> [Data] -> [Data] -> null

Key Components of a Singly Linked List:

1. Data: The value stored in the node.
2. Next Pointer: A reference to the next node in the sequence.

Doubly Linked Lists

A doubly linked list is a type of linked list in which each node contains three components:

1. Data: The value stored in the node.
2. Next Pointer: A pointer to the next node in the list.
3. Previous Pointer: A pointer to the previous node in the list.

Unlike a singly linked list, a doubly linked list allows traversal in both directions — forward and backward — making it a versatile data structure for a variety of applications.

Advantages of Doubly Linked Lists

1. Bidirectional Traversal: You can traverse the list in both forward and backward directions.
2. Ease of Deletion: Given a pointer to a node, it is easier to delete that node since you can access its predecessor.
3. Insertion Operations: Inserting a node before or after a given node is simpler because you have access to both neighboring nodes.
4. More Flexibility: Useful in scenarios like implementing undo operations in software, navigating back and forth between web pages, etc.

Disadvantages of Doubly Linked Lists:

1. Increased Memory Usage: Each node requires extra memory for the backward pointer, which can be a drawback for memory-constrained environments.
2. Complexity: The implementation is more complex compared to singly linked lists due to the additional pointer and the need to maintain pointers in both directions.

Implementation of Doubly Linked List

Doubly Linked List is quite similar to Singly Linked List except it contains extra pointer to previous node. Similar to Singly Linked List we can implement Doubly Linked List using either structure or class.

1️⃣ Using Structure:

// Define the Node structure for a doubly linked list
struct Node {
    int data;            // Data stored in the node
    Node* next;          // Pointer to the next node in the list
    Node* prev;          // Pointer to the previous node in the list

    // Constructor to initialize a new node with data
    Node(int value) : data(value), next(nullptr), prev(nullptr) {}
};

Complete Example:

// Example program
#include <iostream>
#include <string>

using namespace std;

struct Node{
    int data;
    Node* next;
    Node* previous;
    
    Node(int data) {
        this->data = data;
        next = nullptr;
        previous = nullptr;
    }

};

void traverse(Node* head) {
    Node* curr = head;
    while(curr != nullptr) {
        
        cout << curr->data << " -> ";
        curr = curr->next;
        
    }
    cout << "nullptr" << endl;
}

int main()
{
  Node* head = new Node(0);
  
  Node* first = new Node(1);
  
  Node* second = new Node(2);
  
  Node* third = new Node(3);
  
  Node* fourth  = new Node(4);
  
  Node* fifth = new Node(5);
  
  head->next = first;

  first->next = second;
  first->previous = head;
  
  second->next = third;
  second->previous = first;
  
  third->next = fourth;
  third->previous = second;
  
  fourth->next = fifth;
  fourth->previous = third;

  traverse(head);
  
}

2️⃣ Using Class:

// Define the Node class for a doubly linked list
class Node {
public:
    int data;            // Data stored in the node
    Node* next;          // Pointer to the next node in the list
    Node* prev;          // Pointer to the previous node in the list

    // Constructor to initialize a new node with data
    Node(int value) : data(value), next(nullptr), prev(nullptr) {}
};

Complete Example:

// Example program
#include <iostream>
#include <string>

using namespace std;

// Define the Node class for a doubly linked list
class Node {
public:
    int data;            // Data stored in the node
    Node* next;          // Pointer to the next node in the list
    Node* previous;          // Pointer to the previous node in the list

    // Constructor to initialize a new node with data
    Node(int value) : data(value), next(nullptr), previous(nullptr) {}
};

void traverse(Node* head) {
    Node* curr = head;
    while(curr != nullptr) {
        
        cout << curr->data << " -> ";
        curr = curr->next;
        
    }
    cout << "nullptr" << endl;
}

int main()
{
  Node* head = new Node(0);
  
  Node* first = new Node(1);
  
  Node* second = new Node(2);
  
  Node* third = new Node(3);
  
  Node* fourth  = new Node(4);
  
  Node* fifth = new Node(5);
  
  head->next = first;

  first->next = second;
  first->previous = head;
  
  second->next = third;
  second->previous = first;
  
  third->next = fourth;
  third->previous = second;
  
  fourth->next = fifth;
  fourth->previous = third;

  traverse(head);
  
}