Linked List

Aus ProgrammingWiki

Im Gegensatz zu Arrays sind Listen dynamische Datenstrukturen. Die Länge einer Liste steht nach Instanziierung nicht für immer fest. Durch Hinzufügen weiterer Elemente kann die Länge einer Liste bedarfsgerecht angepasst werden.

Eine Linked List (verkettete Liste) ist eine Implementation für den ADT "Lineare Liste". Linked Lists müssen die folgenden Operationen implementieren:

Einfügen eines Elements $x$ in die Liste $L$ - an der Position $p$, Entfernen eines Elements $x$ aus der Liste $L$, Suchen eines Elements $x$ in der Liste $L$ und Zugriff auf das Element $x$ in der Liste $L$

Zur Implementation linearer Listen kommen sequentielle Speicherung (Array) und die verkettete Speicherung infrage. Für letztere Speicherform betrachten wir zwei Implementationen, nämlich Singly Linked List (einfach verkettete Liste) und Doubly Linked List (doppelt verkettete Liste), und illustrieren an diesem Beispiel nochmals den Trade-off zwischen Speicher und Zeit.

Inhaltsverzeichnis 1 Singly Linked List 1.1 Access (Zugriff) und Search (Suche) 1.2 Insert (Einfügen) 1.3 Delete (Entfernen) 2 Doubly Linked List 3 Fazit

Singly Linked List

Bei einer Singly Linked List werden die Elemente (eines bestimmten Grundtyps) der Liste als Nodes (Knoten) abgebildet. Ein Node besteht dabei aus zwei Werten: dem eigentlichen Wert des Elements und einem Pointer, der auf das nächste Element der Liste zeigt. Der Pointer des letzten Elements der Liste hat den Wert null. Um auf die Liste zuzugreifen, wird die (gespeicherte!) Adresse des ersten Nodes angegeben. Da die Verweise auf das jeweils nächste Element gegeben sind, kann man durch Iteration der Pointer, die entsprechenden Elemente der Liste erreichen. Man kann sich das wie ein "Durchhangeln" vorstellen.

Die Liste [5, 10, 20, 1] wird folgendermaßen dargestellt:

import math class Node: def __init__(self): self.value = None self.next = None def add(self, value, index): if index > 1 and self.next is not None: return self.next.add(value, index - 1) elif index == 1: new_node = Node() new_node.value = value new_node.next = self.next self.next = new_node return True return False class SinglyLinkedList: def __init__(self): self.head = Node() self.length = 0 def add(self, value, index=None): if index is None: index = self.length if index == 0: new_node = Node() new_node.value = value new_node.next = self.head self.head = new_node self.length += 1 elif 0 < index <= self.length: if self.head.add(value, index): self.length += 1 def print_lst(self): node = self.head for i in range(self.length - 1): print('{0}, '.format(node.value), end='') node = node.next print(node.value)

lst = SinglyLinkedList() lst.add(5) lst.add(10) lst.add(20) lst.add(1) lst.add(-1, 2) lst.print_lst()

ausführen

Access (Zugriff) und Search (Suche)

Da man zunächst nur auf den Anfang der Liste zugreifen kann, muss man über die Pointer auf die jeweils nächsten Elemente durch die gesamte Liste iterieren, um das letzte Element der Liste zu erreichen. Der Aufwand zur Suche bzw. zum Zugriff auf ein Element beträgt also $\mathcal{O}(n)$. Dies gilt auch für den Fall, dass das gesuchte Element nicht in der Liste vorkommt.

Insert (Einfügen)

Nach dem $m$-ten Element einer Liste soll ein neues Element eingefügt werden. Die Einfügeposition ist durch einen Zeiger auf das $m$-te Element vorgegeben (wird also nicht gesucht). Als erstes wird an einer beliebigen Stelle im Speicher ein neues Node angelegt. Danach muss der Pointer des $m$-ten Elements, der auf das nächste, also $m+1$-te, Element zeigt, in das neu erstellte Node geschrieben werden. Schließlich soll das bisherige $m+1$-te Element Nachfolger des einzufügenden Elements sein. Im letzten Schritt muss der Pointer des $m$-ten Elements so umgeschrieben werden, dass er auf das neu erstellte Node zeigt.

Für den Sonderfall, dass an erster Stelle, also am Index 0, das Element eingefügt werden soll, muss der Pointer des neuen Nodes auf das bisher erste Element zeigen. Zusätzlich wird der Pointer auf den Head der Linked List entsprechend bearbeitet.

In beiden Fällen wird eine konstante Anzahl an Operationen durchgeführt, somit beträgt der Aufwand zum Einfügen $\mathcal{O}(1)$.

Delete (Entfernen)

Um das $m$-te Element der Liste zu löschen, muss lediglich der Pointer des $m-1$-ten Nodes so modifiziert werden, dass er auf das $m+1$-te Element zeigt. Auch hier wird lediglich eine konstante Anzahl an Operationen benötigt, was zu einem Aufwand von $\mathcal{O}(1)$ führt.

Für den Fall, dass das Element am Index 0 entfernt werden soll, muss der Pointer, der auf den Head der Linked List zeigt, auf das Node mit Index 1 zeigen.

Doubly Linked List

Eine Doubly Linked List ist wie eine Singly Linked List implementiert, mit dem Unterschied, dass es bei einer Doubly Linked List zusätzlich zum Pointer auf das nächste Element, einen Pointer, der auf das vorherige Element zeigt, gibt.

Der prev-Pointer des ersten Elements zeigt, wie der next-Pointer des letzten Elements, auf null.

Die asymptotischen Zeitaufwände der Access-, Insert- und Delete-Operationen verhalten sich genauso, wie bei der Singly Linked List.

Befindet sich der aktuelle Pointer auf dem Element mit dem Index $i$, so kann man durch den prev-Pointer mit konstantem Aufwand $\mathcal{O}(1)$ auf das Element mit dem Index $i-1$ zugreifen. Bei einer Singly Linked List müsste man wieder am Anfang der Liste beginnen und hätte einen Aufwand von $\mathcal{O}(n)$. Zu erwähnen ist, dass der Speicherbedarf zwar auch $\mathcal{O}(n)$ ist, jedoch das 1.5-fache an Speicher im Vergleich zur Singly Linked List benötigt wird, da durch die zwei Pointer pro Element drei anstatt zwei Speicherplätze beansprucht werden. Hier gilt also das Prinzip "trade space for time".

class DoublyNode: def __init__(self): self.value = None self.next = None self.prev = None # prev Pointer is required in Doubly Linked List def add(self, value, index): # using prev node as parameter to be able to set prev pointer if index > 1 and self.next is not None: return self.next.add(value, index - 1) elif index == 1: new_node = DoublyNode() new_node.value = value new_node.next = self.next new_node.prev = self self.next.prev = new_node self.next = new_node return True return False def add_from_tail(self, value, index): if index > 1 and self.prev is not None: return self.prev.add_from_tail(value, index - 1) elif index == 1: new_node = DoublyNode() new_node.value = value new_node.next = self new_node.prev = self.prev self.prev.next = new_node self.prev = new_node return True return False def remove(self, index): if index > 0 and self.next is not None: return self.next.remove(index - 1) elif index == 0: self.prev.next = self.next self.next.prev = self.prev return True return False def remove_from_tail(self, index): if index > 0 and self.prev is not None: return self.prev.remove_from_tail(index - 1) elif index == 0: self.next.prev = self.prev self.prev.next = self.next return True return False class DoublyLinkedList: def __init__(self): node = DoublyNode() self.head = node self.tail = node # tail pointer exist to access from end of list self.length = 0 def add(self, value, index=None): if index is None: index = self.length if index == 0 and self.length == 0: self.head.value = value self.length += 1 elif index == 0: new_node = DoublyNode() new_node.value = value new_node.next = self.head new_node.prev = None self.head.prev = new_node self.head = new_node self.length += 1 elif 0 < index < self.length: if self.head.add(value, index): self.length += 1 elif index == self.length: self.add_from_tail(value, 0) def add_from_tail(self, value, index): if index == 0 and self.length == 0: self.tail.value = value self.length += 1 elif index == 0: new_node = DoublyNode() new_node.value = value new_node.next = None new_node.prev = self.tail self.tail.next = new_node self.tail = new_node self.length += 1 elif 0 < index < self.length: if self.tail.add_from_tail(value, index): self.length += 1 elif index == self.length: self.add(value, 0) def remove(self, index): if index >= self.length: return None if index == 0 and self.length == 1: self.head.value = None self.length -= 1 elif index == 0: self.head.next.prev = None self.head = self.head.next self.length -= 1 elif 0 < index < self.length - 1: if self.head.remove(index): self.length -= 1 elif index == self.length - 1: self.remove_from_tail(0) def remove_from_tail(self, index): if index >= self.length: return None if index == 0 and self.length == 1: self.tail.value = None self.length -= 1 elif index == 0: self.tail.prev.next = None self.tail = self.tail.prev self.length -= 1 elif 0 < index < self.length - 1: if self.tail.remove_from_tail(index): self.length -= 1 elif index == self.length - 1: self.remove(0) def print_lst(self): node = self.head for i in range(self.length - 1): print('{0}, '.format(node.value), end='') node = node.next print(node.value)

lst = DoublyLinkedList() lst.add(5) lst.add(10) lst.add(20) lst.add(1) lst.add(-1, 2) lst.add_from_tail(-2, 4) lst.remove(2) lst.print_lst()

ausführen

Fazit

Eine Linked List (sowohl singly als auch doubly) eignet sich, wenn häufig Elemente eingefügt und entfernt werden, da der Zeitaufwand dafür lediglich $\mathcal{O}(1)$ beträgt. Eine Doubly Linked List ist besonders dann geeignet, wenn man häufig das Vorgängerelement benötigt. Dies ist z. B. bei Browserverläufen oder Undo/Redo-Aktionen der Fall. Hier kommt eine Doubly Linked List zum Einsatz.