Linked List

A Linked List is a linear data structure in which every element (node) stores data and a pointer to the next node. Unlike an array, nodes do not need to be contiguous in memory.

Node and Pointer Concept

Each node contains two components:
- Data: The stored value.
- Next: A pointer to the next node (None if it is the last one).

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

# Creating nodes
node1 = Node(10)
node2 = Node(20)
node1.next = node2  # node1 -> node2

Linked List vs Array

Aspect	Array	Linked List
Memory	Contiguous block	Scattered
Access	O(1) by index	O(n) traversal
Insert at head	O(n) shift	O(1)
Insert in middle	O(n) shift	O(1) if you are already at the position
Delete	O(n) shift	O(1) if you are already at the position
Memory	More efficient	Pointer overhead

Types of Linked List

Singly Linked List: Each node has one pointer (next).
Doubly Linked List: Each node has two pointers (next and prev).
Circular Linked List: The last node points back to the first node.

Memory

A Linked List does not store data contiguously in memory. Each node is allocated at a different address and the nodes are connected by pointers.

[10|*] -> [20|*] -> [30|None]
 address: 0x100     0x200     0x300

Use Cases

Implementing Stack and Queue
Music playlists (next/previous song)
Browser history (back/forward)
LRU Cache

Linked Lists come in many variations. Let's start with the most basic one: the Singly Linked List.