Co je jednosměrný propojený seznam a kdy byste jej použili?

Question

Accepted Answer

**Jednosměrný propojený seznam** je řetězec **uzlů**, kde každý uzel obsahuje hodnotu a ukazatel na **další** uzel. Na rozdíl od pole nejsou uzly souvislé — mohou být kdekoli v paměti, spojené prostřednictvím odkazů.

## Struktura

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## Příklad

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

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## Složitost

| Operace | Čas |
|---|---|
| Vložení/odstranění na začátku | O(1) |
| Přístup podle indexu | O(n) |
| Hledání | O(n) |

## Kompromisy

- **Silné stránky:** O(1) vložení/odstranění na začátku; růst bez přealoace; bez plýtvání kapacitou.
- **Slabé stránky:** bez náhodného přístupu; každý uzel nese režii ukazatele; špatná lokalita mezipaměti (rozptýlená paměť).

## Proč na tom záleží

PropojenÝ seznamy se vyznačují, když často přidáváte nebo odebíráte na koncích a zřídka indexujete do středu — například jako páteř zásobníků, front a seznamů sousednosti.

Pochopení manipulace s ukazateli zde je základní pro stromy, grafy a mnoho interview problémů.

Operace	Čas
Vložení/odstranění na začátku	O(1)
Přístup podle indexu	O(n)
Hledání	O(n)