✅ DSA Part 5 – Linked Lists: Single, Double & Reverse 🔁🔗📚

Linked Lists are dynamic data structures ideal for scenarios requiring frequent insertions and deletions. Unlike arrays, they don’t need contiguous memory and offer flexible memory usage.

1️⃣ What is a Linked List?
A Linked List is a linear data structure where each element (node) contains:
- Data
- Pointer to the next node (and optionally the previous node)

Types:
- Singly Linked List: Each node points to the next
- Doubly Linked List: Nodes point to both next and previous
- Circular Linked List: Last node points back to the head

2️⃣ Singly Linked List – Basic Structure

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Java

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

C++

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

3️⃣ Insert at Head (Singly)

Python

def insert_head(head, data):
    new_node = Node(data)
    new_node.next = head
    return new_node

Java

Node insertHead(Node head, int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    return newNode;
}

C++

Node* insertHead(Node* head, int data) {
    Node* newNode = new Node(data);
    newNode->next = head;
    return newNode;
}

4️⃣ Doubly Linked List – Bi-directional Pointers

Python

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

Java

class DNode {
    int data;
    DNode prev, next;
    DNode(int data) {
        this.data = data;
    }
}

C++

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

5️⃣ Insert at Head (Doubly)

Python

def insert_head(head, data):
    new_node = DNode(data)
    new_node.next = head
    if head:
        head.prev = new_node
    return new_node

Java

DNode insertHead(DNode head, int data) {
    DNode newNode = new DNode(data);
    newNode.next = head;
    if (head != null) head.prev = newNode;
    return newNode;
}

C++

DNode* insertHead(DNode* head, int data) {
    DNode* newNode = new DNode(data);
    newNode->next = head;
    if (head) head->prev = newNode;
    return newNode;
}

6️⃣ Reversing a Singly Linked List

Python

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

Java

Node reverseList(Node head) {
    Node prev = null, current = head;
    while (current != null) {
        Node next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

C++

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    while (current) {
        Node* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

7️⃣ Why Use Linked Lists?
✅ Dynamic memory allocation
✅ Efficient insert/delete (O(1) at head/tail)
❌ Slower access (O(n) for random access)
✅ Great for implementing stacks, queues, hash maps, etc.

8️⃣ Practice Tasks
✅ Implement singly linked list with insert/delete
✅ Implement doubly linked list with insert at tail
✅ Reverse a singly linked list