LinkedList (DSA - 6)

Linked lists are a fundamental data structure in computer science, used to store a collection of elements. They consist of nodes, where each node contains a value and a reference (or link) to the next node in the sequence.

• Dynamically resized
• No copying overhead

Basics of Linked Lists

Node Structure:

Each node typically contains two parts:

Data: The value stored in the node.
Next: A reference to the next node in the list.

Types of Linked Lists:

Singly Linked List:

Each node points to the next node in the sequence.

Structure

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

Traversal

void traverse() {
    Node* current = head;
    while (current) {
        cout << current->data;
        current = current->next;
    }
}

Reverse Traversal

// Using stack
void traverseReverse(Node* head) {
    std::stack<int> nodeStack;

    // Traverse the linked list and push data onto the stack
    Node* current = head;
    while (current != nullptr) {
        nodeStack.push(current->data);
        current = current->next;
    }

    // Pop data from the stack to print in reverse order
    while (!nodeStack.empty()) {
        std::cout << nodeStack.top() << " ";
        nodeStack.pop();
    }
    std::cout << std::endl;
}

void traverseReverseRecursive(Node* head) {
    if (head == nullptr) return;

    traverseReverseRecursive(head->next); 

    std::cout << head->data << " "; 
}

Insert

void insert_at_beginning(int data) {
    Node* new_node = new Node(data);
    new_node->next = head;
    head = new_node;
}

void insert_at_middle(int data, int position) {
    if (position == 0) {
        insert_at_beginning(data);
        return;
    }

    Node* new_node = new Node(data);
    Node* current = head;
    for (int i = 0; i < position - 1 && current != nullptr; ++i) {
        current = current->next;
    }

    if (current == nullptr) {
        cout << "Position out of bounds" << endl;
        delete new_node;
        return;
    }

    new_node->next = current->next;
    current->next = new_node;
}

void insert_at_end(int data) {
    Node* new_node = new Node(data);
    if (!head) {
        head = new_node;
        return;
    }

    Node* current = head;
    while (current->next) {
        current = current->next;
    }

    current->next = new_node;
}

Delete

void delete_at_beginning() {
    if (!head) return;

    Node* temp = head;
    head = head->next;
    delete temp;
}

void LinkedList::delete_at_middle(int position) {
    if (!head) return;

    if (position == 0) {
        delete_at_beginning();
        return;
    }

    Node* current = head;
    for (int i = 0; i < position - 1 && current->next != nullptr; ++i) {
        current = current->next;
    }

    if (current->next == nullptr) {
        std::cerr << "Position out of bounds" << std::endl;
        return;
    }

    Node* temp = current->next;
    current->next = current->next->next;
    delete temp;
}


void delete_at_end() {
    if (!head) return;

    if (!head->next) {
        delete head;
        head = nullptr;
        return;
    }

    Node* current = head;
    while (current->next && current->next->next) {
        current = current->next;
    }

    delete current->next;
    current->next = nullptr;
}

Doubly Linked List:
Each node has two references, one to the next node and one to the previous node.

Structure

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

Construct DLL

    Node* constructDLL(vector<int>& arr) {
        // code here
        Node* head=new Node(arr[0]);
        Node* temp=head;
        for(int i=1;i<arr.size();i++){
            Node * nn=new Node(arr[i]);
            nn->prev=temp;
            temp->next=nn;
            temp=nn;
        }
        return head;
    }

Insert

void DoublyLinkedList::insert_at_beginning(int data) {
    Node* new_node = new Node(data);
    if (head) {
        new_node->next = head;
        head->prev = new_node;
    }
    head = new_node;
}

void DoublyLinkedList::insert_at_middle(int data, int position) {
    if (position == 0) {
        insert_at_beginning(data);
        return;
    }

    Node* new_node = new Node(data);
    Node* current = head;

    for (int i = 0; i < position - 1 && current != nullptr; ++i) {
        current = current->next;
    }

    if (current == nullptr) {
        cout << "Position out of bounds";
        delete new_node;
        return;
    }

    new_node->next = current->next;
    if (current->next != nullptr) {
        current->next->prev = new_node;
    }
    current->next = new_node;
    new_node->prev = current;
}

void insert_at_end(int data) {
    Node* new_node = new Node(data);
    if (!head) {
        head = new_node;
        return;
    }

    Node* current = head;
    while (current->next) {
        current = current->next;
    }

    current->next = new_node;
    new_node->prev = current;
}

Delete

void delete_at_beginning() {
    if (!head) {
        std::cerr << "List is empty" << std::endl;
        return;
    }
    Node* temp = head;
    head = head->next;
    if (head) {
        head->prev = nullptr;
    }
    delete temp;
}

void DoublyLinkedList::delete_at_middle(int position) {
    if (!head) {
        std::cerr << "List is empty" << std::endl;
        return;
    }
    if (position == 0) {
        delete_at_beginning();
        return;
    }

    Node* current = head;
    for (int i = 0; i < position && current != nullptr; ++i) {
        current = current->next;
    }

    if (current == nullptr) {
        std::cerr << "Position out of bounds" << std::endl;
        return;
    }

    if (current->prev) {
        current->prev->next = current->next;
    }
    if (current->next) {
        current->next->prev = current->prev;
    }
    delete current;
}

void DoublyLinkedList::delete_at_end() {
    if (!head) {
        std::cerr << "List is empty" << std::endl;
        return;
    }

    Node* current = head;
    while (current->next) {
        current = current->next;
    }

    if (current->prev) {
        current->prev->next = nullptr;
    } else {
        head = nullptr; // List had only one node
    }
    delete current;
}

Circular Linked List: The last node points back to the first node, forming a circle.

Important Algorithms

Tortoise Hare

bool detect_cycle() {
    if (!head || !head->next) {
        return false;
    }

    Node* slow = head;
    Node* fast = head;

    while (fast && fast->next) {
        slow = slow->next;        
        fast = fast->next->next

        if (fast == slow) {
            return true;
        }
    }
    return false;
}

Middle of an element

Node* find_middle() {
    if (!head) {
        return nullptr;
    }

    Node* slow = head;
    Node* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

Reverse a linkedlist (3 - pointer approach)

    ListNode* reverseList(ListNode* head) {

        ListNode* prev = NULL;
        ListNode* curr = head;

        while(curr != NULL){
            ListNode* forward = curr->next;
            curr->next = prev;
            prev = curr;
            curr = forward;

        }
        return prev;
    }

Merge Sorted Lists

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // Create a dummy node to act as the start of the merged list
    ListNode dummy(0);
    ListNode* tail = &dummy;

    // Traverse both lists
    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // If one of the lists is not empty, append the remaining nodes
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }

    return dummy.next;
}

Applications:

1. Dynamic Memory Management
2. Implementing Queues and Stacks
3. Graph Representations
4. Routing Tables in Networking

Stay Connected!
If you enjoyed this post, don’t forget to follow me on social media for more updates and insights:

Twitter: madhavganesan
Instagram: madhavganesan
LinkedIn: madhavganesan