Linked Lists

Linked Lists in C++

A linked list is a linear data structure where elements, called nodes, are stored in a sequence, and each node points to the next one in the list. Unlike arrays, linked lists do not require contiguous memory locations, making them more flexible for dynamic memory allocation. Linked lists are particularly useful when the size of the data structure is not known beforehand and frequent insertions and deletions are needed.

Structure of a Linked List

A node in a linked list typically contains:

1. Data: The value stored in the node.
2. Next: A pointer (or reference) to the next node in the list.

The head of the list points to the first node. The last node points to NULL (or nullptr in C++), indicating the end of the list.

Types of Linked Lists

1. Singly Linked List: Each node points only to the next node.
2. Doubly Linked List: Each node points to both the next node and the previous node.
3. Circular Linked List: The last node points back to the first node. It can be singly or doubly linked.

Basic Operations of a Linked List

1. Insertion:

   • At the beginning (head).
   • At the end (tail).
   • At a given position.

2. Deletion:

   • From the beginning (head).
   • From the end (tail).
   • At a given position.

3. Traversal: Accessing all nodes in the list, usually for printing or searching.

4. Search: Finding a node with a specific value.

5. Update: Modifying the data of a node.

1. Singly Linked List in C++

A singly linked list is the most basic type of linked list, where each node contains data and a reference (pointer) to the next node in the list. The last node’s reference points to NULL, signifying the end of the list.

Node Structure for Singly Linked List

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;
    
public:
    LinkedList() : head(nullptr) {}

    // Insertion at the beginning
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Insertion at the end
    void insertAtEnd(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // Deletion from the beginning
    void deleteFromBeginning() {
        if (head == nullptr) {
            cout << "List is empty!\n";
            return;
        }
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    // Traversing the list
    void traverse() {
        if (head == nullptr) {
            cout << "List is empty!\n";
            return;
        }
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    // Searching for an element
    bool search(int value) {
        Node* temp = head;
        while (temp != nullptr) {
            if (temp->data == value)
                return true;
            temp = temp->next;
        }
        return false;
    }

    // Destructor to free memory
    ~LinkedList() {
        Node* temp;
        while (head != nullptr) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    LinkedList list;
    
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtBeginning(5);
    
    cout << "List after insertions: ";
    list.traverse();  // Output: 5 10 20
    
    list.deleteFromBeginning();
    cout << "List after deletion from beginning: ";
    list.traverse();  // Output: 10 20
    
    cout << "Is 20 in the list? " << (list.search(20) ? "Yes" : "No") << endl;  // Yes

    return 0;
}

2. Doubly Linked List in C++

A doubly linked list is a variation of the singly linked list where each node has two pointers: one pointing to the next node and another pointing to the previous node. This allows traversal in both directions (forward and backward).

Node Structure for Doubly Linked List

#include <iostream>
using namespace std;

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

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

class DoublyLinkedList {
private:
    Node* head;

public:
    DoublyLinkedList() : head(nullptr) {}

    // Insertion at the beginning
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }

    // Insertion at the end
    void insertAtEnd(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }

    // Deletion from the beginning
    void deleteFromBeginning() {
        if (head == nullptr) {
            cout << "List is empty!\n";
            return;
        }
        Node* temp = head;
        head = head->next;
        if (head != nullptr) {
            head->prev = nullptr;
        }
        delete temp;
    }

    // Traversing the list from beginning
    void traverseForward() {
        if (head == nullptr) {
            cout << "List is empty!\n";
            return;
        }
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    // Traversing the list from end
    void traverseBackward() {
        if (head == nullptr) {
            cout << "List is empty!\n";
            return;
        }
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->prev;
        }
        cout << endl;
    }

    // Destructor to free memory
    ~DoublyLinkedList() {
        Node* temp;
        while (head != nullptr) {
            temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int main() {
    DoublyLinkedList list;

    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtBeginning(5);

    cout << "Forward traversal: ";
    list.traverseForward();  // Output: 5 10 20

    cout << "Backward traversal: ";
    list.traverseBackward();  // Output: 20 10 5

    return 0;
}

3. Circular Linked List

In a circular linked list, the last node points back to the first node, forming a loop. This structure can be either singly or doubly linked. Circular linked lists are used in applications where you need continuous looping, such as in circular buffers or scheduling systems.

Singly Circular Linked List Example

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;

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

class CircularLinkedList {
private:
    Node* head;

public:
    CircularLinkedList() : head(nullptr) {}

    // Insert at the beginning
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            newNode->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
            head = newNode;
        }
    }

    // Traversing the list
    void traverse() {
        if (head == nullptr) {
            cout << "List is empty!\n";
            return;
        }
        Node* temp = head;
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
        cout << endl;
    }

    // Destructor to free memory
    ~CircularLinkedList() {
        if (head == nullptr) return;
        Node* temp = head;
        do {
            Node* nextNode =