Linked Lists

A Linked List is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element (called a Node) contains its data and a memory pointer to the next node in the sequence.

         Singly vs. Doubly:
        In a Singly Linked List, nodes only point forward. In a
        Doubly Linked List, each node holds two pointers: one pointing to the next node,
        and one pointing back to the previous node.
      

Advantages over Arrays

Unlike standard arrays, linked lists do not have a fixed size. Inserting or deleting a node in the middle of a list does not require shifting all subsequent elements in memory; you simply update the pointers of the neighboring nodes to bypass or include the new node.

Complexity

Operation	Complexity	Explanation
Access / Search	$O(n)$	You cannot access elements by index. You must start at the Head and traverse the list one by one.
Insertion (at Head)	$O(1)$	Creating a new node and pointing it to the current Head is instantaneous.
Deletion (given pointer)	$O(1)$	If you already hold the reference to the node, rerouting the pointers takes constant time.