Was ist eine einfach verkettete Liste und wann würden Sie eine verwenden?

Question

Accepted Answer

Eine **einfach verkettete Liste** ist eine Kette von **Knoten**, wobei jeder Knoten einen Wert und einen Zeiger auf den **nächsten** Knoten enthält. Im Gegensatz zu einem Array sind die Knoten nicht zusammenhängend — sie können überall im Speicher sein und sind durch Verweise verbunden.

## Struktur

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

## Beispiel

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

## Komplexität

| Operation | Zeit |
|---|---|
| Einfügen/Löschen am Anfang | O(1) |
| Zugriff nach Index | O(n) |
| Suche | O(n) |

## Kompromisse

- **Stärken:** O(1) Einfügen/Löschen am Anfang; Wachstum ohne Neuallokation; keine verschwendete Kapazität.
- **Schwächen:** kein wahlfreier Zugriff; jeder Knoten trägt Zeiger-Overhead; schlechte Cache-Lokalität (zersplitterter Speicher).

## Warum es wichtig ist

Verlinkte Listen glänzen, wenn Sie häufig an den Enden hinzufügen oder entfernen und nur selten in die Mitte indizieren — zum Beispiel als Grundlage von Stacks, Queues und Adjazenzlisten.

Das Verständnis der Zeigermanipulation hier ist grundlegend für Bäume, Graphen und viele Interview-Probleme.

Operation	Zeit
Einfügen/Löschen am Anfang	O(1)
Zugriff nach Index	O(n)
Suche	O(n)