AuK/Konkrete Datenstrukturen/Linked List
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Python</language>
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.
==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:
[[Datei:Singly-linked-list_5-10-20-1.png|center]]
<code id="5f3896b68ccff">
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)
</code>
<run id="5f3896b68ce04">
lst = SinglyLinkedList()
lst.add(5)
lst.add(10)
lst.add(20)
lst.add(1)
lst.add(-1, 2)
lst.print_lst()
</run>
===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.
[[Datei:Linkedlist_insert_middle.png|center]]
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.
[[Datei:Linkedlist_insert_at_start.png|center]]
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.
[[Datei:Linkedlist_deletion.png|center]]
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.
[[Datei:DLL1.png|center]]
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".
<code id="5f3896b68cd82">
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)
</code>
<run id="5f3896b68ce6d">
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()
</run>
==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.