Što je jednostruko povezana lista i kada biste je koristili?

Question

Accepted Answer

**Jednostruko povezana lista** je lanac **čvorova**, gdje svaki čvor sadrži vrijednost i pokazivač na **sljedeći** čvor. Za razliku od array, čvorovi nisu susjedni — mogu biti bilo gdje u memoriji, povezani referencama.

## Struktura

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

## Primjer

```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ženost

| Operacija | Vrijeme |
|---|---|
| Umetanje/brisanje na početku | O(1) |
| Pristup po indeksu | O(n) |
| Pretraživanje | O(n) |

## Kompromisi

- **Prednosti:** O(1) umetanje/brisanje na početku; rast bez realokacije; nema rasipane kapacitete.
- **Nedostaci:** nema slučajnog pristupa; svaki čvor nosi dodatne troškove pokazivača; loša lokalnost cache (razbacana memorija).

## Zašto je to važno

Povezane liste sjajno funkcioniraju kada često dodajete ili brišete na krajevima i rijetko pristupate sredini — na primjer, kao osnova storiva, redova čekanja i popisa susjedstva.

Razumijevanje manipulacije pokazivačima ovdje je temelj za stabla, grafove i mnoge probleme na razgovorima.

Operacija	Vrijeme
Umetanje/brisanje na početku	O(1)
Pristup po indeksu	O(n)
Pretraživanje	O(n)