## What is it? A Singly Linked List is a linear data structure where each element (node) contains a value and a pointer to the next node. Unlike arrays, nodes are not stored contiguously in memory — each node links to the next via a reference. ## How it works Each node: `{ value, next → Node | null }` **Core operations:** - **Insert at head** — create node, point it to current head, update head → O(1) - **Insert at tail** — traverse to end, link last node to new node → O(n) - **Delete** — find the node before target, update its `next` pointer → O(n) - **Search** — traverse from head comparing values → O(n) - **Traverse** — follow `next` pointers until `null` ## When to use - When frequent insertions/deletions at the head are needed (O(1) vs O(n) for arrays) - Implementing stacks, queues, hash chaining - When memory allocation must be dynamic (no pre-allocated block needed) ## Key Points - No random access — accessing index `i` takes O(n), not O(1) - No cache-friendly — nodes scattered in memory; arrays are faster in practice for most reads - The tail node always points to `null` - Common gotchas: losing the head reference, forgetting to update `next` on delete