Datenstrukturen in Python - Linked Lists

Nach den Queues und den Stacks geht es im dritten Artikel zu Datenstrukturen um die Linked Lists.

Bei dieser Datenstrukturen hat man es mit Knoten (nodes) zu tun, die miteinander verbunden sind. Zu jedem Knoten gehört ein Wert (value) und ein Zeiger (pointer). Folgende Abbildung zeigt eine Singly Linked List, bei der jeder Knoten nur über einen Zeiger verfügt, der auf den nächsten Knoten zeigt. Der erste Knoten wird als Head Node bezeichnet. Der letzte Knote wird als Tail Node bezeichnet.

Darüber hinaus gibt es noch die Doubly Linked Lists, bei denen die Knoten über zwei Zeiger verfügen. Einer zeigt auf den nachfolgenden Knoten (wie bei der Singly Linked List), der andere zeigt auf den vorhergehenden Knoten.

Vor- und Nachteile

Der Vorteil einer Linked List besteht darin, dass die einzelnen Elemente an verschiedenen Stellen im Arbeitsspeicher abgelegt werden können. Im Gegensatz dazu benötigen anderen Datenstrukturen — wie beispielsweise Arrays (array.array, numpy.array oder lists) — eine zusammenhängende Speichersequenz. Linked Lists zeichnen sich also durch eine hohe Flexibilität aus.

Der Nachteil besteht darin, dass die Suche nach einem Wert am Anfang der Linked List beginnt und dann von Knoten zu Knoten gesprungen wird. Es handelt sich also um eine (relativ langsame) lineare Suche (O(n)). Beinhaltet eine Linked List n-Elemente, dann dauert die Suche n-Zeit.

collections.deque verwenden

Das Collections-Modul implementiert spezialisierte Container-Datentypen. Falls Ihr den Artikel zu den Queues gelesen habt, werdet Ihr wissen, dass für die Realisierung einer Queue auf collections.deque zurückgegriffen werden kann. Die Klasse collections.deque, die für Stacks und Queues verwendet werden kann, ist intern als Linked List implementiert. Dementsprechend kann sie auch für eine Linked List verwendet werden.

Das Hinzufügen von Werten kann sowohl am Anfang (mit appendleft()) als auch am Ende (mit append()) vorgenommen werden. Daher kann collections.deque sowohl für Singly Linked Lists als auch für Doubly Linked Lists verwendet werden. Im folgenden Beispiel wird eine neue Linked List erstellt, zu der vier Elemente hinzugefügt werden:

from collections import deque

linked_list = deque()

# Element zur Linked List hinzufügen
linked_list.append(5)
linked_list.append(27)
linked_list.append(2)
linked_list.append(20)

print(linked_list)
# -> deque([5, 27, 2, 20])

Für das Entfernen des letzten Elements steht die Methode pop() zur Verfügung. Nach dem Entfernen des letzten Knotens wird hier der Knoten mit dem Wert 2 zum neuen Tail Node:

linked_list.pop()
print(linked_list)
# -> deque([5, 27, 2])

Wie bereits erwähnt, kann ein Element auch zum Anfang hinzugefügt werden. Hier wird der Knoten mit dem Wert 100 zum neuen Head Node:

linked_list.appendleft(100)
print(linked_list)
# -> deque([100, 5, 27, 2])

Und das Entfernen des ersten Elements erfolgt mit popleft():

linked_list.popleft()
print(linked_list)
# -> deque([5, 27, 2])

Eine eigene Singly Linked List erstellen

Sofern nicht auf das Collections-Modul zurückgegriffen werden soll, muss man selbst eine Linked List erstellen. Dabei stellt sich die Frage, welche Funktionalität vorhanden sein soll. Auf jeden Fall wird man einen Knoten hinzufügen wollen. Außerdem soll die Linked List auch durchlaufen werden können. Und schließlich mag es auch von Interesse sein, ob eine Linked List überhaupt Knoten enthält oder leer ist. Also sollten folgende Methoden implementiert werden:

push: Ein Element am Ende hinzufügen
traversal: Eine Linked List durchlaufen
is_empty: Überprüfen, ob die Linked List Elemente enthält

Dies könnte folgendermaßen realisiert werden, wobei zunächst eine Klasse Node erstellt wird, die jeweils einen Knoten repräsentiert. Diese Klasse beinhaltet den Wert und den Zeiger zum nächsten Knoten:

# A Node of a Singly Linked List
class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next_node = next

Es folgt die Klasse LinkedList, die die Linked List selbst repräsentiert:

# A Linked List Class with a single (head) node
class LinkedList:
    def __init__(self):
        self.head = None

Wir haben damit eine Basisstruktur geschaffen, die als Ausgangspunkt für die Implementierung der erforderlichen Methoden dient. Beginnen wir mit der Methode is_empty, mit der überprüft wird, ob die Linked List Knoten enthält:

def is_empty(self):
    return not self.head

Anspruchsvoller wird es mit der Methode, die einen Wert am Ende der Linked List hinzufügt:

def push_node(self, value):
    new_node = Node(value)
    if self.head:
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
    else:
        self.head = new_node

Zunächst wird mit der Zeile

new_node = Node(value)

ein neuer Knoten erstellt.

Betrachten wir als nächstes den else-Block der folgenden if-Verzweigung:

if self.head:
    …
else:
    self.head = new_node

Denn am Anfang, wenn noch gar kein Knoten existiert, wird dieser Teil aufgerufen und mit

self.head = new_node

ein Head-Knoten erstellt.

Das Hinzufügen der dann folgenden Knoten erledigt danach der if-Block:

if self.head:
    current_node = self.head
    while current_node.next:
        current_node = current_node.next
    current_node.next = new_node

Die Linked List wird dabei durchlaufen, um das Ende zu ermitteln. Wenn das Ende erreicht wurde, fügt

current_node.next = new_node

einen neuen Knoten hinzu.

Mit der Methode def traversal() wird die Linked List durchlaufen und alle vorhandenen Elemente ausgegeben. Inhaltlich weist sie Ähnlichkeiten zu push_node() auf, da dort — zur Feststellung des letzten Knotens — die Linked List ebenfalls durchlaufen werden muss.

def traversal(self):
    current_node = self.head
    while current_node:
        print(current_node.value)
        current_node = current_node.next

Eine neue Linked List könnte nun mit

my_linked_list = LinkedList()

erzeugt werden. Anschließend können Knoten hinzugefügt werden:

my_linked_list.push_node(24)
my_linked_list.push_node(7)
my_linked_list.push_node(30)
my_linked_list.push_node(33)

Wird diese Linked List nun durchlaufen, führt dies zu folgender Ausgabe:

my_linked_list.traversal()
24
7
30
33

Außerdem lässt sich überprüfen, ob sie Knoten enthält:

print(my_linked_list.is_empty())
False

Die hier gezeigt Implementierung ist lediglich als Vorschlag zu verstehen. Es ließe sich auch anders umsetzen, und so werdet Ihr bei einer Internet-Recherche einige andere Beispiele finden. Außerdem könnte noch mehr Funktionalität implementiert werden, z.B. das Entfernen eines Knotens.