Dynamische Datenstrukturen – Lineare Listen

IN-SA TB #030+

---

Überblick: Statische vs. Dynamische Datenstrukturen

	Statisch	Dynamisch
Beispiele	Felder (Arrays)	Verkettete Liste, Queue, Stack
Größe	Im Vorhinein festgelegt	Zur Laufzeit veränderbar
Speicher	Zusammenhängend, indiziert	Verteilt, über Referenzen verbunden
Vorteil	Schneller Zugriff per Index	Effiziente Nutzung des Speichers

Dynamische DS – Vorteil

Eine DS heißt dynamisch, wenn ihre Größe nicht im Vorfeld festgelegt werden muss, sondern zur Laufzeit verändert werden kann.

Vorteil: Effiziente Nutzung des Speicherbedarfs, effiziente Anordnung der Daten im Speicher.

---

① (Einfach) Verkettete Liste

Idee

Eine Liste ist eine verkettete Folge von Elementen. Jedes Element (Knoten) kennt seinen Nachfolger.

[Inhalt|→] → [Inhalt|→] → [Inhalt|→] → NIL

Wichtige Operationen

Operation	Beschreibung
insert(b)	Einfügen eines neuen Elements in die Liste
delete(b)	Löschen eines Elements aus der Liste
search(b)	Suchen eines Elements in der Liste (von vorne beginnen)
replace(b)	Ersetzen eines Elements in der Liste

Formale Definition einer verketteten Liste

1. Es gibt genau ein Element, das keinen Vorgänger hat → Listenanfang
2. Es gibt genau ein Element, das keinen Nachfolger hat → Listenende
3. Alle übrigen Elemente haben genau einen Vorgänger und genau einen Nachfolger
4. Eine Liste, die kein Element besitzt, heißt leere Liste (NULL / NIL)

Klassendiagramm (UML)

┌──────────────────────────────┐
│            Liste             │
├──────────────────────────────┤
│                              │
├──────────────────────────────┤
│ + insert(b)                  │
│ + delete(b)                  │
│ + search(b)                  │
│ + replace(b)                 │
└──────────────────────────────┘
         ◇ (reflexive Aggregation)
         │
┌────────▼─────────────────────┐
│           Knoten             │
├──────────────────────────────┤
│ - inhalt : Datentyp          │
│ - referenz : Knoten          │  ← zeigt auf nächsten Knoten
└──────────────────────────────┘

Die verkettete Liste ist eine rekursive Struktur: Jeder Knoten enthält den nächsten Knoten (oder NIL).

Modell

head
 │
 ▼
[Inhalt | ref] → [Inhalt | ref] → [Inhalt | ref] → NIL

Varianten

• Doppelt verkettete Liste: Jeder Knoten kennt zusätzlich noch seinen Vorgänger

  NIL ← [◄ Inhalt ►] ↔ [◄ Inhalt ►] ↔ [◄ Inhalt ►] → NIL

• Ring: Listenanfang und Listenende werden verbunden (zyklisch)

---

② Queue / Schlange (FIFO)

FIFO = First In, First Out

Prinzip

Das Element, das zuerst eingefügt wurde, wird auch zuerst herausgeholt – wie eine Warteschlange.

Eingang → [o][o][o][o] → Ausgang
           einfügen      rausholen

Beispiel: Druckerwarteschlange

Operationen einer Queue

Operation	Beschreibung
enqueue(x)	Einfügen eines Elements – nur als letztes
dequeue()	Löschen eines Elements – nur als erstes
front()	Lesen des ersten Elements (dort, wo auch dequeue stattfindet)
isEmpty()	Gibt True zurück, falls kein Element vorhanden

Implementierung in Python

class Queue:
    def __init__(self):
        self.__head = None   # Inhalt zunächst leer
        self.__tail = None   # Referenz auf nächste Queue

    # Getter und Setter
    def setHead(self, head):
        self.__head = head

    def setTail(self, tail):
        self.__tail = tail

    def getHead(self):
        return self.__head

    def getTail(self):
        return self.__tail

    def enqueue(self, x):
        # Hinten einfügen
        if self.__tail == None:
            neu = Queue()
            neu.setHead(x)       # tail von neu ist eh None
            self.__tail = neu
        else:
            self.__tail.enqueue(x)   # weiterreichen

    def dequeue(self):
        # Das erste Element entfernen
        if self.__tail != None:
            self.__tail = self.__tail.getTail()

    def front(self):
        if self.__tail != None:
            return self.__tail.getHead()

    def isEmpty(self):
        if self.__tail == None:
            return True
        else:
            return False

---

③ Stack / Stapel (FILO / LIFO)

FILO = First In, Last Out | LIFO = Last In, First Out

Prinzip

Das Element, das zuletzt eingefügt wurde, wird zuerst herausgeholt – wie ein Stapel Teller.

     ┌──────┐   ← push (oben drauf legen)
     │  5   │
     │  4   │
     │  3   │
     │  2   │
     │  1   │   ← erstes Element (ganz unten)
     └──────┘   ← pop (von oben wegnehmen)

Operationen eines Stacks

Operation	Beschreibung
push(x)	Einfügen eines Inhalts (nur als oberstes Element)
pop()	Löschen des obersten Elements (gibt es auch zurück)
top()	Lesen / Rückgabe des obersten Elements (ohne löschen)
isEmpty()	Gibt True/False zurück – prüft ob der Stapel leer ist

Bei Aufruf von pop() wird auch noch das gepopte Element zurückgegeben.

Beispiel-Aufrufsequenz

push(1) → [1]
push(2) → [1, 2]
pop()   → [1]        (gibt 2 zurück)
push(3) → [1, 3]
push(4) → [1, 3, 4]
pop()   → [1, 3]     (gibt 4 zurück)
pop()   → [1]        (gibt 3 zurück)
push(5) → [1, 5]

Implementierung in Python

class Stack:
    def __init__(self):
        self.__head = None
        self.__tail = None

    # Getter und Setter (analog zu Queue)
    def setHead(self, head):
        self.__head = head

    def setTail(self, tail):
        self.__tail = tail

    def getHead(self):
        return self.__head

    def getTail(self):
        return self.__tail

    def push(self, x):
        # Oben einfügen (vorne)
        neu = Stack()
        neu.setHead(x)
        neu.setTail(self.__tail)
        self.__tail = neu

    def pop(self):
        # Oberstes Element entfernen
        if self.__tail != None:
            self.__tail = self.__tail.getTail()

    def top(self):
        if self.__tail != None:
            return self.__tail.getHead()

    def isEmpty(self):
        return self.__tail == None

---

Vergleich: Queue vs. Stack

Eigenschaft	Queue (FIFO)	Stack (LIFO)
Prinzip	Erster rein = Erster raus	Letzter rein = Erster raus
Einfügen	Hinten (enqueue)	Oben (push)
Entnehmen	Vorne (dequeue)	Oben (pop)
Lesen ohne Entnahme	front()	top()
Beispiel	Druckerwarteschlange	Browsing-Verlauf / Undo