Hvad er en enkeltlinket liste, og hvornår ville du bruge en?

Question

Accepted Answer

En **enkeltlinket liste** er en kæde af **noder**, hvor hver node indeholder en værdi og en pointer til den **næste** node. I modsætning til et array er noderne ikke sammenhængende — de kan være overalt i hukommelsen, forbundet via referencer.

## Struktur

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

## Eksempel

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

## Kompleksitet

| Operation | Tid |
|---|---|
| Indsæt/slet i hovedet | O(1) |
| Adgang efter indeks | O(n) |
| Søg | O(n) |

## Afvejninger

- **Styrker:** O(1) indsæt/slet i hovedet; vokser uden omfordeling; ingen spildt kapacitet.
- **Svagheder:** ingen tilfældig adgang; hver node bærer pointer-overhead; dårlig cache-lokalitet (spredt hukommelse).

## Hvorfor det betyder noget

Linkede lister skinner når du ofte tilføjer eller fjerner i enderne og sjældent indekserer ind i midten — for eksempel som ryggraden af stakke, køer og naboskabslister.

Forståelse af pointer-manipulation her er grundlæggende for træer, grafer og mange interview-problemer.