Vad är en enkellänkad lista och när skulle du använda en?

Question

Accepted Answer

En **enkellänkad lista** är en kedja av **noder**, där varje nod innehåller ett värde och en pekare till nästa **nod**. Till skillnad från en array är noderna inte sammanhängande — de kan finnas överallt i minnet, kopplade genom referenser.

## Struktur

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

## Exempel

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

## Komplexitet

| Operation | Tid |
|---|---|
| Infoga/ta bort i huvud | O(1) |
| Åtkomst efter index | O(n) |
| Sökning | O(n) |

## Avvägningar

- **Styrkor:** O(1) infoga/ta bort i början; växer utan omallokering; ingen slödsad kapacitet.
- **Svagheter:** ingen slumpmässig åtkomst; varje nod bär pekar-overhead; dålig cache-lokalitet (spridd minne).

## Varför det spelar roll

Länkade listor glänser när du ofta lägger till eller tar bort vid ändarna och sällan indexerar in i mitten — till exempel som ryggraden i stackar, köer och närliggande listor.

Att förstå pekar-manipulation här är grundläggande för träd, grafer och många intervjufrågor.

Operation	Tid
Infoga/ta bort i huvud	O(1)
Åtkomst efter index	O(n)
Sökning	O(n)