# Linked List — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/linked-list

> Nodes connected by pointers — O(1) insert/delete once you hold the node.

## Node + next

Each node holds a value and a reference to the next node:

```
[10|·]-> [20|·]-> [30|null]
```

Elements are scattered in memory. There's no index math, so reaching position `k` costs `O(k)`, but splicing a node in or out is `O(1)`.

## Treasure hunt

Each clue tells you only where the next clue is. You can't jump to clue 5 — you follow the chain. But adding a clue means rewriting just two notes.

## Insert at head, reverse

Reversing is the classic: walk once, flipping each `next` pointer backwards.

```python
class Node:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def reverse(head):
    prev = None
    while head:
        nxt = head.next   # save
        head.next = prev   # flip
        prev = head        # advance
        head = nxt
    return prev            # new head
```

## Variants & patterns

Singly, doubly (has `prev`), and circular (tail points to head). Fast/slow pointers detect cycles and find the middle; a dummy head node removes edge cases when deleting.