Mikä on yksinkertaisesti linkitetty lista ja milloin käyttäisit sitä?

Question

Accepted Answer

**Yksinkertaisesti linkitetty lista** on **solmujen** ketju, jossa jokainen solmu sisältää arvon ja osoittimen **seuraavaan** solmuun. Toisin kuin taulukon tapauksessa, solmut eivät ole peräkkäisiä — ne voivat sijaita missä tahansa muistissa, yhteydessä toisiinsa viittausten avulla.

## Rakenne

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

## Esimerkki

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

## Monimutkaisuus

| Operaatio | Aika |
|---|---|
| Lisäys/poisto alussa | O(1) |
| Pääsy indeksillä | O(n) |
| Haku | O(n) |

## Kompromissit

- **Vahvuudet:** O(1) lisäys/poisto alussa; kasvu ilman uudelleenallokointia; ei tuhlattua kapasiteettia.
- **Heikkoudet:** ei satunnaista pääsyä; jokainen solmu kuljettaa osoitinyläkuormaa; huono välimuistin paikallisuus (hajallaan oleva muisti).

## Miksi se on tärkeää

Linkitetyt listat loistavat silloin, kun lisäät tai poistat usein päissä ja harvoin indeksoit keskelle — esimerkiksi pinon, jonon ja vierekkäisyysluetteloiden perustana.

Osoittimen manipuloinnin ymmärtäminen on perustavanlaatuista puiden, graafien ja monien haastattelu-ongelmien kannalta.