Linked List

Linked list is one of the most basic data structure. Unlike arrays which are statically allocated, have fixed size in contigous memory, linked lists are just nodes (containing pointer to next node and data) that are dynamically allocated at runtime.

#include <iostream>
#include <stdexcept>

class Node {
public:
    int data;
    Node* next;

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

class LinkedList {
private:
    Node* head;

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

    ~LinkedList() { // Linear - O(n)
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    int length() const { // Linear - O(n)
        int count = 0;
        Node* curr = head;
        while (curr != nullptr) {
            count++;
            curr = curr->next;
        }
        return count;
    }

    void append(int val) { // Linear - O(n)
        Node* newnode = new Node(val);
        if (head == nullptr) {
            head = newnode;
            return;
        }

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

    void prepend(int val) { // Constant - O(1)
        Node* newnode = new Node(val);
        newnode->next = head;
        head = newnode;
    }

    int get(size_t index) const { // Linear - O(1)
        if (head == nullptr) {
            throw std::out_of_range("Index out of bounds");
        }

        Node* curr = head;
        while (index > 0 && curr != nullptr) {
            curr = curr->next;
            index--;
        }

        if (curr == nullptr) {
            throw std::out_of_range("Index out of bounds");
        }

        return curr->data;
    }

    void remove() { // Constant - O(1)
        if (head == nullptr) {
            throw std::out_of_range("Index out of bounds");
        }
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    void removeAt(size_t index) { // Linear - O(n)
        if (head == nullptr) {
            throw std::out_of_range("Index out of bounds");
        }

        if (index == 0) {
            remove();
            return;
        }

        Node* prev = nullptr;
        Node* curr = head;
        while (index > 0 && curr != nullptr) {
            prev = curr;
            curr = curr->next;
            index--;
        }

        if (curr == nullptr) {
            throw std::out_of_range("Index out of bounds");
        }

        prev->next = curr->next;
        delete curr;
    }

    void insertAt(int val, size_t index) { // Linear - O(n)
        if (index == 0) {
            prepend(val);
            return;
        }

        Node* prev = nullptr;
        Node* curr = head;
        while (index > 0 && curr != nullptr) {
            prev = curr;
            curr = curr->next;
            index--;
        }

        if (index > 0) {
            throw std::out_of_range("Index out of bounds");
        }

        Node* newnode = new Node(val);
        newnode->next = curr;
        prev->next = newnode;
    }

    void print() const { // Linear - O(n)
        Node* curr = head;
        while (curr != nullptr) {
            std::cout << curr->data << " -> ";
            curr = curr->next;
        }
        std::cout << "nullptr\n";
    }
};

int main() {
    LinkedList list;

    list.append(10);
    list.append(20);
    list.prepend(5);
    std::cout << "Initial list: ";
    list.print();

    list.insertAt(15, 2);
    std::cout << "After inserting 15 at index 2: ";
    list.print();
}