🔗 Linked Lists in Data Structures

A Linked List is a **dynamic data structure** where elements (nodes) are **linked using pointers**. Unlike arrays, linked lists **do not require contiguous memory allocation** and can **grow or shrink dynamically**.

⚡ Why Use Linked Lists?

📌 **Dynamic Memory Allocation** - Size **is not fixed**, unlike arrays.
🚀 **Efficient Insertions & Deletions** - Operations take **O(1) time** if a pointer is available.
📂 **Better Memory Utilization** - No memory wastage due to resizing.
🔄 **Used in Stacks, Queues, Graphs** - Backbone of **many advanced data structures**.

🛠️ Types of Linked Lists

🔹 1. Singly Linked List

Each node contains **data** and a **pointer** to the **next node**.


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

🔸 2. Doubly Linked List

Each node has **two pointers** – one to the **next node** and one to the **previous node**.


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

🔄 3. Circular Linked List

The **last node** points to the **first node**, making it circular.


                struct Node {
                    int data;
                    Node* next; // Last node points to first
                };

⚙️ Common Operations on Linked Lists

🆕 1. Insertion

Adding an element at the **beginning, middle, or end** of a linked list.

📌 Insert at Beginning (O(1))


                void insertAtHead(Node*& head, int value) {
                    Node* newNode = new Node();
                    newNode->data = value;
                    newNode->next = head;
                    head = newNode;
                }

📌 Insert at End (O(n))


                void insertAtTail(Node*& head, int value) {
                    Node* newNode = new Node();
                    newNode->data = value;
                    newNode->next = nullptr;
                    if (!head) { head = newNode; return; }
                    Node* temp = head;
                    while (temp->next) temp = temp->next;
                    temp->next = newNode;
                }

🗑️ 2. Deletion

Removing an element from a **specific position**.

❌ Delete a Node (O(n))


                void deleteNode(Node*& head, int key) {
                    if (!head) return;
                    if (head->data == key) { head = head->next; return; }
                    Node* temp = head;
                    while (temp->next && temp->next->data != key)
                        temp = temp->next;
                    if (temp->next) temp->next = temp->next->next;
                }

🔎 3. Searching

Finding an element in a linked list.

🔍 Linear Search (O(n))


                bool search(Node* head, int key) {
                    Node* temp = head;
                    while (temp) {
                        if (temp->data == key) return true;
                        temp = temp->next;
                    }
                    return false;
                }

🔄 4. Reversing a Linked List

Reversing the order of nodes in a linked list.


                Node* reverse(Node* head) {
                    Node* prev = nullptr, *curr = head, *next = nullptr;
                    while (curr) {
                        next = curr->next;
                        curr->next = prev;
                        prev = curr;
                        curr = next;
                    }
                    return prev;
                }

⏳ Time Complexity Analysis

Operation	Best Case	Worst Case
Access	O(n)	O(n)
Insertion at Beginning	O(1)	O(1)
Insertion at End	O(n)	O(n)
Search	O(1)	O(n)
Deletion	O(1)	O(n)