Algorithmen Anfänger 30 min

Arrays, Listen & Hash-Tables

Die drei wichtigsten Datenstrukturen: Arrays, Linked Lists und Hash-Tables. Ihre Staerken, Schwaechen und wann du was nutzt.

Aktualisiert:
Inhaltsverzeichnis

Arrays, Listen & Hash-Tables

Ohne gute Datenstrukturen ist kein Algorithmus effizient. Diese drei sind die mit Abstand wichtigsten.

Array (dynamisch, wie Python-Listen)

Ein Array ist eine geordnete, indizierte Sammlung. In Python heisst sie list, in JavaScript Array, in Rust Vec.

Operationen und Komplexitaet

arr = [10, 20, 30, 40, 50]

arr[2]              # O(1) - Index-Zugriff
arr[2] = 99         # O(1) - Setzen
len(arr)            # O(1)

arr.append(60)      # O(1) amortisiert - anhaengen
arr.pop()           # O(1) - letztes entfernen

arr.insert(0, 5)    # O(n) - am Anfang einfuegen
arr.pop(0)          # O(n) - am Anfang entfernen
del arr[2]          # O(n) - in der Mitte

value in arr        # O(n) - Suche

Warum die Unterschiede?

Arrays sind zusammenhaengende Speicherbereiche. Index-Zugriff ist eine Adressberechnung - sofort. Am Ende einfuegen ist meist trivial. Aber am Anfang oder in der Mitte: alle Elemente muessen verschoben werden.

Wann nutzen?

  • Immer, wenn du Index-Zugriff brauchst
  • Wenn du meistens am Ende einfuegst/entfernst
  • Fuer sequenzielle Iteration

Wann NICHT?

  • Wenn du viele Insertions in der Mitte hast
  • Fuer Suchen ohne Index (besser Hash-Table)

Linked List - verkettete Liste

Jedes Element haelt einen Verweis auf das naechste:

[10] → [20] → [30] → [40] → null

Keine zusammenhaengenden Speicher. Insertions und Deletions sind billig - wenn man die Stelle kennt.

Komplexitaet

# Pseudo-Code
head = ...

# Zugriff per Index
get(i)              # O(n) - durchlaufen

# Am Anfang einfuegen
prepend(x)          # O(1)

# Nach bekanntem Knoten einfuegen
insert_after(node, x)  # O(1)

# Am Ende (ohne Tail-Pointer)
append(x)           # O(n)

Eigene Implementation

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, value):
        new = Node(value)
        new.next = self.head
        self.head = new

    def __iter__(self):
        current = self.head
        while current:
            yield current.value
            current = current.next

ll = LinkedList()
ll.prepend(3)
ll.prepend(2)
ll.prepend(1)

print(list(ll))  # [1, 2, 3]

Wann nutzen?

  • Implementation-Details von Queues, Stacks
  • Wenn du haeufig am Anfang einfuegst/entfernst
  • In Low-Memory-Umgebungen (keine Array-Resize-Spitzen)

In der Praxis

Im Alltag nutzt du selten selbst geschriebene Linked Lists - Python’s list oder JavaScript’s Array decken das meiste ab. Aber: Verstehen, wie sie funktionieren, ist wichtig.

Hash-Table - Dictionary, Map, Object

Eine Hash-Table speichert Key-Value-Paare und erlaubt schnelle Lookups.

dict_map = {}
dict_map["anna"] = 28
dict_map["max"] = 34

dict_map["anna"]            # 28 - O(1) average
"anna" in dict_map          # True - O(1)
del dict_map["max"]         # O(1)

for key, value in dict_map.items():
    print(key, value)         # O(n)

In JavaScript: Map oder einfaches Object. In Java: HashMap. In Rust: HashMap.

Wie funktioniert eine Hash-Table?

  1. Key wird durch Hash-Funktion in einen Index umgewandelt: hash("anna") % size → 42
  2. Der Wert wird bei diesem Index gespeichert
  3. Suche: gleicher Hash → gleicher Index → direkt zum Wert

Collisions (zwei Keys haben den gleichen Index) werden mit Linked Lists oder offener Adressierung aufgeloest.

Komplexitaet

OperationAverageWorst (extreme)
InsertO(1)O(n)
LookupO(1)O(n)
DeleteO(1)O(n)

Worst-Case tritt nur bei sehr vielen Kollisionen auf (z.B. boese Hash-Funktion bei Angreifern).

Wann nutzen?

  • Immer, wenn du schnelles Lookup brauchst
  • Als Cache, Index, Lookup-Table
  • Fuer eindeutige Elemente (Sets sind Hash-Tables ohne Value)

Typisches Optimierungs-Pattern

Viele “Ist X in der Liste?”-Algorithmen werden von O(n²) zu O(n), indem du eine Hash-Table nutzt:

Naiv - O(n²):

def finde_paar(liste, ziel):
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            if liste[i] + liste[j] == ziel:
                return (i, j)
    return None

Mit Hash-Table - O(n):

def finde_paar(liste, ziel):
    gesehen = {}
    for i, x in enumerate(liste):
        komplement = ziel - x
        if komplement in gesehen:
            return (gesehen[komplement], i)
        gesehen[x] = i
    return None

Bei 10.000 Elementen: erste Version ist ~10.000x langsamer.

Set - einzigartige Elemente

Ein Set ist eine Hash-Table ohne Values - nur Keys, alle unique.

s = set()
s.add("anna")
s.add("max")
s.add("anna")         # schon drin, keine Aenderung

print(s)               # {"anna", "max"}

"anna" in s            # O(1)
s.remove("max")

Nuetzlich fuer:

  • Duplikate entfernen: list(set(arr))
  • Enthalten-Test in O(1)
  • Mengen-Operationen: a | b (Vereinigung), a & b (Schnitt), a - b (Differenz)

Stack (LIFO)

Last-In-First-Out - wie ein Tellerstapel.

stack = []
stack.append(1)       # push
stack.append(2)
stack.append(3)

stack.pop()           # 3 (LIFO)
stack[-1]             # Top: 2

In Python ist list mit append/pop ein Stack. Perfekt fuer:

  • Rueckgaengig machen (Undo)
  • Rekursion-Simulation
  • Klammern-Matching
  • DFS (naechstes Kapitel)

Queue (FIFO)

First-In-First-Out - wie eine Warteschlange.

from collections import deque

queue = deque()
queue.append(1)       # enqueue
queue.append(2)
queue.append(3)

queue.popleft()       # 1 (FIFO) - O(1)!

Wichtig: Python-list mit pop(0) ist O(n) - deque ist O(1). Nutze collections.deque fuer Queues.

Verwendung:

  • BFS (Breadth-First Search)
  • Job-Queue, Task-Scheduling
  • Buffer

Wann welche Struktur?

BedarfWahl
Index-ZugriffArray / List
Schnelles Enthalten-TestSet / Dict
Key-Value-LookupDict / HashMap
LIFOStack (list)
FIFOQueue (deque)
Sortierte Elementesort + Array, oder Heap
Eindeutige ElementeSet
Keine Duplikate + sortiertTreeSet / SortedSet

Ein praktisches Beispiel

Count-Anwendung: Wie oft kommt jedes Wort in einem Text vor?

Naiv - O(n²):

def zaehle(text):
    woerter = text.split()
    counts = {}
    for wort in woerter:
        if wort not in counts:
            counts[wort] = 0
        counts[wort] += 1
    return counts

Das ist schon O(n) (Dict-Lookups sind O(1)), aber eleganter:

from collections import Counter

def zaehle(text):
    return Counter(text.split())

Counter ist eine spezialisierte Dict-Subklasse, perfekt fuer solche Probleme.

Die Kosten im Blick

Eine Routine, um Duplikate zu finden:

def duplikate(liste):
    gesehen = set()
    duplikate = set()
    for x in liste:
        if x in gesehen:
            duplikate.add(x)
        else:
            gesehen.add(x)
    return duplikate

Analyse:

  • Zeit: O(n) - eine Iteration, in set ist O(1)
  • Platz: O(n) - beide Sets koennen bis zu n Elemente haben

Das ist optimal.

Zusammenfassung

  • Array/List: Index-Zugriff in O(1), Einfuegen/Loeschen in der Mitte O(n)
  • Linked List: O(1) am Anfang/nach bekanntem Knoten
  • Hash-Table (Dict): O(1) Lookup - der grosse Optimierungs-Joker
  • Set: unique Elemente in O(1), perfekt fuer Enthalten-Tests
  • Stack/Queue: fuer LIFO/FIFO - list fuer Stack, deque fuer Queue
  • in auf Dict/Set statt auf Liste macht O(n²) → O(n)

Im naechsten Kapitel: Baeume und Graphen - die komplexeren Strukturen.

Zurück zum Algorithmen Kurs