techmore.in

C++ Linked List

In C++, a linked list is a fundamental data structure consisting of a sequence of elements, where each element points to the next one. Unlike arrays, linked lists do not require contiguous memory allocation. Each element, known as a node, contains data and a pointer to the next node in the sequence.

Types of Linked Lists

  1. Singly Linked List: Each node points to the next node and has no reference to the previous 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, forming a circle.

Implementing a Singly Linked List

Here's a basic implementation of a singly linked list in C++:

1. Node Structure

cpp
#include 

struct Node {
    int data;
    Node* next;

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

2. Linked List Class

cpp
#include 

class LinkedList {
private:
    Node* head;

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

    ~LinkedList() {
        clear();
    }

    // Add a node at the end
    void append(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
    }

    // Add a node at the beginning
    void prepend(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Remove the first occurrence of a value
    void remove(int value) {
        Node* temp = head;
        Node* prev = nullptr;

        // Check if head needs to be removed
        if (temp && temp->data == value) {
            head = temp->next;
            delete temp;
            return;
        }

        // Find the node to remove
        while (temp && temp->data != value) {
            prev = temp;
            temp = temp->next;
        }

        // Node not found
        if (!temp) return;

        // Remove the node
        prev->next = temp->next;
        delete temp;
    }

    // Print all nodes
    void print() const {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

    // Clear all nodes
    void clear() {
        Node* temp = head;
        while (temp) {
            Node* nextNode = temp->next;
            delete temp;
            temp = nextNode;
        }
        head = nullptr;
    }
};

3. Example Usage

cpp
#include 

int main() {
    LinkedList list;

    list.append(1);
    list.append(2);
    list.append(3);
    list.prepend(0);

    std::cout << "List: ";
    list.print(); // Output: 0 1 2 3

    list.remove(2);
    std::cout << "After removing 2: ";
    list.print(); // Output: 0 1 3

    list.clear();
    std::cout << "After clearing: ";
    list.print(); // Output: (empty)

    return 0;
}

Implementing a Doubly Linked List

A doubly linked list has nodes with pointers to both the next and previous nodes. Here’s a basic implementation:

1. Node Structure

cpp
#include 

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

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

2. Doubly Linked List Class

cpp
#include 

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

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

    ~DoublyLinkedList() {
        clear();
    }

    // Add a node at the end
    void append(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    // Add a node at the beginning
    void prepend(int value) {
        Node* newNode = new Node(value);
        if (!head) {
            head = newNode;
            tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
    }

    // Remove a node
    void remove(int value) {
        Node* temp = head;
        while (temp && temp->data != value) {
            temp = temp->next;
        }

        if (!temp) return; // Node not found

        // Remove the node
        if (temp->prev) {
            temp->prev->next = temp->next;
        } else {
            head = temp->next; // Removing the head
        }

        if (temp->next) {
            temp->next->prev = temp->prev;
        } else {
            tail = temp->prev; // Removing the tail
        }

        delete temp;
    }

    // Print all nodes from head to tail
    void printForward() const {
        Node* temp = head;
        while (temp) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

    // Print all nodes from tail to head
    void printBackward() const {
        Node* temp = tail;
        while (temp) {
            std::cout << temp->data << " ";
            temp = temp->prev;
        }
        std::cout << std::endl;
    }

    // Clear all nodes
    void clear() {
        Node* temp = head;
        while (temp) {
            Node* nextNode = temp->next;
            delete temp;
            temp = nextNode;
        }
        head = nullptr;
        tail = nullptr;
    }
};

3. Example Usage

cpp
#include 

int main() {
    DoublyLinkedList list;

    list.append(1);
    list.append(2);
    list.append(3);
    list.prepend(0);

    std::cout << "List forward: ";
    list.printForward(); // Output: 0 1 2 3

    std::cout << "List backward: ";
    list.printBackward(); // Output: 3 2 1 0

    list.remove(2);
    std::cout << "After removing 2 (forward): ";
    list.printForward(); // Output: 0 1 3

    list.clear();
    std::cout << "After clearing (forward): ";
    list.printForward(); // Output: (empty)

    return 0;
}

Key Points

  • Singly Linked List: Simple and efficient for basic operations but lacks bidirectional traversal.
  • Doubly Linked List: Allows bidirectional traversal and can handle complex operations more flexibly but uses more memory due to extra pointers.

Use Cases

  • Singly Linked List: Suitable for scenarios where you need efficient insertions/deletions at the head or tail but do not need bidirectional traversal.
  • Doubly Linked List: Useful when you need efficient insertions/deletions and bidirectional traversal.

Summary

Linked lists are powerful data structures that provide dynamic sizing and efficient insertions/deletions. Depending on your needs, you can choose between singly linked lists for simpler use cases or doubly linked lists for more complex scenarios requiring bidirectional traversal.