DEV Community

Cover image for LinkedList (DSA - 6)
Madhav Ganesan
Madhav Ganesan

Posted on

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) {}
};
Enter fullscreen mode Exit fullscreen mode

Traversal

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

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;
}
Enter fullscreen mode Exit fullscreen mode
void traverseReverseRecursive(Node* head) {
    if (head == nullptr) return;

    traverseReverseRecursive(head->next); 

    std::cout << head->data << " "; 
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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) {}
};
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}

Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)