Cos'è una singly linked list e quando la useresti?

Question

Accepted Answer

Una **singly linked list** è una catena di **nodi**, dove ogni nodo contiene un valore e un puntatore al nodo **next**. A differenza di un array, i nodi non sono contigui — possono trovarsi ovunque in memoria, collegati da riferimenti.

## Struttura

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

## Esempio

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

## Complessità

| Operazione | Tempo |
|---|---|
| Inserimento/eliminazione in testa | O(1) |
| Accesso per indice | O(n) |
| Ricerca | O(n) |

## Compromessi

- **Vantaggi:** O(1) inserimento/eliminazione in testa; cresce senza riallocazione; nessuna capacità sprecata.
- **Svantaggi:** nessun accesso casuale; ogni nodo porta overhead del puntatore; scarsa località di cache (memoria sparsa).

## Perché è importante

Le linked list brillano quando frequentemente aggiungi o rimuovi alle estremità e raramente indicizzi nel mezzo — ad esempio, come base di stack, code e liste di adiacenza.

Capire la manipolazione dei puntatori qui è fondamentale per alberi, grafi e molti problemi di intervista.

Operazione	Tempo
Inserimento/eliminazione in testa	O(1)
Accesso per indice	O(n)
Ricerca	O(n)