Listen: einfach verkettete und doppelt verkettete Listen

5.1 Definition einer Liste und ihre Arten

Liste – ist eine dynamische Datenstruktur, die aus Elementen (Knoten) besteht, wobei jeder Knoten Daten und Verweise auf andere Knoten enthält. Im Gegensatz zu Arrays können Listen ihre Größe zur Laufzeit des Programms ändern.

Wichtig! Hier geht es nicht um die Klasse list in Python, sondern um eine Datenstruktur aus der Algorithmentheorie.

Arten von Listen:

• Einfach verkettene Liste (Singly Linked List): Jeder Knoten enthält Daten und einen Verweis auf den nächsten Knoten.
• Doppelt verkettene Liste (Doubly Linked List): Jeder Knoten enthält Daten, einen Verweis auf den nächsten Knoten und einen Verweis auf den vorherigen Knoten.

5.2 Funktionsprinzip einer einfach verkettenen Liste

Struktur einer einfach verkettenen Liste:

• Knoten (Node): Besteht aus zwei Teilen: Daten und einem Verweis auf den nächsten Knoten.
• Kopf (Head): Zeiger auf den ersten Knoten der Liste.

Funktionsprinzip:

• Hinzufügen eines Knotens: Erfolgt durch Erstellen eines neuen Knotens und Aktualisieren des Verweises des letzten Knotens auf den neuen Knoten.
• Entfernen eines Knotens: Erfordert die Aktualisierung des Verweises des vorherigen Knotens auf den nächsten Knoten des zu entfernenden Knotens.

Beispielimplementierung:

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Beispielnutzung:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Ausgabe: 1 -> 2 -> 3 -> None

5.3 Funktionsprinzip einer doppelt verkettenen Liste

Struktur einer doppelt verkettenen Liste:

• Knoten (Node): Besteht aus drei Teilen: Daten, einem Verweis auf den nächsten Knoten und einem Verweis auf den vorherigen Knoten.
• Kopf (Head): Zeiger auf den ersten Knoten der Liste.
• Schwanz (Tail): Zeiger auf den letzten Knoten der Liste (nicht unbedingt erforderlich, aber oft verwendet).

Funktionsprinzip:

• Hinzufügen eines Knotens: Erfolgt durch Erstellen eines neuen Knotens und Aktualisieren der Verweise des letzten und des neuen Knotens.
• Entfernen eines Knotens: Erfordert die Aktualisierung der Verweise der benachbarten Knoten des zu entfernenden Knotens.

Beispielimplementierung:

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Beispielnutzung:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Ausgabe: 1 <-> 2 <-> 3 <-> None

5.4 Grundlegende Operationen

Grundlegende Operationen: Einfügen, Entfernen, Suchen

Einfügen:

• Einfach verkettene Liste: Das Einfügen eines neuen Knotens am Ende der Liste erfordert das Durchlaufen aller Knoten bis zum letzten und das Aktualisieren des Verweises des letzten Knotens.
• Doppelt verkettene Liste: Das Einfügen eines neuen Knotens am Ende der Liste ist ähnlich wie bei der einfach verkettenen Liste, es ist jedoch auch eine Aktualisierung des Verweises prev des neuen Knotens auf den vorherigen Knoten erforderlich.

Entfernen:

• Einfach verkettene Liste: Das Entfernen eines Knotens erfordert das Durchlaufen der Liste bis zum Knoten, den man entfernen möchte, und das Aktualisieren des Verweises des vorherigen Knotens auf den nächsten Knoten des zu entfernenden Knotens.
• Doppelt verkettene Liste: Das Entfernen eines Knotens erfordert die Aktualisierung der Verweise next und prev der benachbarten Knoten des zu entfernenden Knotens.

Suchen: Durchlaufen der Liste vom Kopf bis zum Schwanz und Vergleichen der Daten jedes Knotens mit dem gesuchten Wert. Zeitkomplexität — O(n).

5.5 Beispiel für die Nutzung von Listen

Lass uns als Beispiel einen Stack auf Basis einer einfach verkettenen Liste implementieren.

Ein Stack kann einfach mit einer einfach verkettenen Liste implementiert werden, indem die Methoden push zum Hinzufügen und pop zum Entfernen von Elementen verwendet werden. Er sollte 2 Methoden haben:

• push — Hinzufügen eines neuen Elements am Ende der Liste
• pop — Entfernen des letzten Elements vom Ende der Liste

Beispielimplementierung:

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Beispielnutzung:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Ausgabe: 3 -> 2 -> 1 -> None
print(stack.pop())  # Ausgabe: 3
stack.display()  # Ausgabe: 2 -> 1 -> None