Linked List and Its Various Types

Linked List

A linked list is a linear data structure where elements, called nodes, are stored in a sequence, and each node points to the next node in the list. Unlike arrays, linked lists do not store data in contiguous memory locations, which makes it dynamic and flexible in terms of memory management.

Node Structure:

A node in a linked list typically contains two parts:

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

In C++, a typical node structure can look like this:

struct Node {
    int data;
    Node* next;  // Pointer to the next node
};

Types of Linked Lists

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Circular Doubly Linked List

1. Singly Linked List

A singly linked list is the simplest type of linked list. In this structure, each node has a single pointer to the next node. The last node points to nullptr, marking the end of the list.

Operations:

• Insertion: Adding a new node to the list (at the beginning, end, or a specified position).
• Deletion: Removing a node (from the beginning, end, or a specified position).
• Traversal: Accessing each node starting from the head node.

C++ Implementation:

#include <iostream>
using namespace std;

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

class SinglyLinkedList {
    Node* head;

public:
    SinglyLinkedList() {
        head = nullptr;
    }

    // Function to insert at the end
    void insertAtEnd(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = nullptr;

        if (head == nullptr) {
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
        cout << value << " inserted at end.\n";
    }

    // Function to display the linked list
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "nullptr\n";
    }

    // Function to delete a node from the beginning
    void deleteFromBeginning() {
        if (head == nullptr) {
            cout << "List is empty.\n";
            return;
        }

        Node* temp = head;
        head = head->next;
        cout << "Node with value " << temp->data << " deleted.\n";
        delete temp;
    }
};

int main() {
    SinglyLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.display();
    list.deleteFromBeginning();
    list.display();
    return 0;
}

2. Doubly Linked List

A doubly linked list is a more complex structure where each node contains two pointers:

• Next: Points to the next node in the sequence.
• Prev: Points to the previous node in the sequence.

This allows traversal in both directions (forward and backward).

C++ Implementation:

#include <iostream>
using namespace std;

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

class DoublyLinkedList {
    Node* head;

public:
    DoublyLinkedList() {
        head = nullptr;
    }

    // Function to insert at the beginning
    void insertAtBeginning(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = head;
        newNode->prev = nullptr;

        if (head != nullptr) {
            head->prev = newNode;
        }

        head = newNode;
        cout << value << " inserted at beginning.\n";
    }

    // Function to display the list
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " <-> ";
            temp = temp->next;
        }
        cout << "nullptr\n";
    }

    // Function to delete a node from the end
    void deleteFromEnd() {
        if (head == nullptr) {
            cout << "List is empty.\n";
            return;
        }

        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }

        if (temp->prev != nullptr) {
            temp->prev->next = nullptr;
        } else {
            head = nullptr;  // The list becomes empty
        }

        cout << "Node with value " << temp->data << " deleted.\n";
        delete temp;
    }
};

int main() {
    DoublyLinkedList list;
    list.insertAtBeginning(10);
    list.insertAtBeginning(20);
    list.insertAtBeginning(30);
    list.display();
    list.deleteFromEnd();
    list.display();
    return 0;
}

3. Circular Linked List

A circular linked list is a variation of the singly linked list where the last node points back to the head, forming a loop. There is no nullptr to signify the end of the list.

Operations:

• Traversal becomes continuous, and care is needed to avoid infinite loops.

C++ Implementation:

#include <iostream>
using namespace std;

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

class CircularLinkedList {
    Node* head;

public:
    CircularLinkedList() {
        head = nullptr;
    }

    // Function to insert at the end
    void insertAtEnd(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = head;

        if (head == nullptr) {
            head = newNode;
            newNode->next = head;  // Circular link
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
        cout << value << " inserted in circular list.\n";
    }

    // Function to display the circular list
    void display() {
        if (head == nullptr) {
            cout << "List is empty.\n";
            return;
        }

        Node* temp = head;
        do {
            cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != head);
        cout << "head\n";
    }
};

int main() {
    CircularLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.display();
    return 0;
}

4. Circular Doubly Linked List

A circular doubly linked list combines the features of both circular and doubly linked lists. Each node has two pointers (next and prev), and the last node points to the first node, forming a circle in both directions.

Operations:

• Like a doubly linked list, you can traverse forward and backward, but the list has no clear start or end.

C++ Implementation:

#include <iostream>
using namespace std;

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

class CircularDoublyLinkedList {
    Node* head;

public:
    CircularDoublyLinkedList() {
        head = nullptr;
    }

    // Function to insert at the beginning
    void insertAtBeginning(int value) {
        Node* newNode = new Node();
        newNode->data = value;

        if (head == nullptr) {
            head = newNode;
            newNode->next = head;
            newNode->prev = head;
        } else {
            Node* tail = head->prev;
            newNode->next = head;
            newNode->prev = tail;
            head->prev = newNode;
            tail->next = newNode;
            head = newNode;
        }
        cout << value << " inserted in circular doubly list.\n";
    }

    // Function to display the list
    void display() {
        if (head == nullptr) {
            cout << "List is empty.\n";
            return;
        }

        Node* temp = head;
        do {
            cout << temp->data << " <-> ";
            temp = temp->next;
        } while (temp != head);
        cout << "head\n";
    }
};

int main() {
    CircularDoublyLinkedList list;
    list.insertAtBeginning(10);
    list.insertAtBeginning(20);
    list.insertAtBeginning(30);
    list.display();
    return 0;
}

Comparison of Linked List Types

Conclusion:

Linked lists are a dynamic data structure that offers flexibility in memory management. Each type of linked list is suited to different use cases, with trade-offs in terms of complexity and performance.