In diesem Notebook illustrieren wir die Implementation einer verketteten Liste, sowie des Listen ADTs, der mithile der verketteten Liste implementiert ist.
Die Grundlage für die Implementation ist ein Node. Ein Node enthält ein Datum (hier item genannt) und eine Referenz auf das nächste Element (oder None, falls es kein nächstes Element gibt)
class Node:
def __init__(self, item, next=None):
self.item = item
self.next = next
Bevor wir mit dieser Datenstruktur experimentieren, brauchen wir eine Methode, die uns die Liste anzeigt.
def printList(n):
currentNode = n
while (currentNode != None):
print(currentNode.item)
currentNode = currentNode.next
Ale erstes erzeugen wir 3 Knoten
n1 = Node("first")
n2 = Node("second")
n3 = Node("third")
Wie wir mit printList sehen, ist jedes Element noch einzeln.
printList(n1)
first
Um eine Liste von 3 Elementen zu erhalten müssen wir diese noch verketten.
n1.next = n2; n2.next = n3
printList(n1)
first second third
Wir können jetzt weitere Funktionen schreiben um mit der Liste zu arbeiten, wie zum Beispiel ein Element am Anfang hinzuzufügen
def addItemToBegin(item, node):
newNode = Node(item, node)
return newNode
printList(addItemToBegin("before first", n1))
before first first second third
Direkt mit der Klasse Node zu arbeiten funktiont für interne Implementationen, wäre aber für einen Endbenutzer zu Mühsam. Eine bessere Strategie ist es, einen Listen ADT zu designen, und diesen dann, zum Beispiel mit einer verketteten Liste zu implementieren. Wir zeigen hier schematisch, wie so eine Implementation aussehen kann.
class LinkedList:
class Iterator:
def __init__(self, linkedList):
self._currentItem = linkedList.head
self.linkedList = linkedList
def hasNext(self):
return (self._currentItem != None)
def next(self):
item = self._currentItem.item
self._currentItem = self._currentItem.next
return item
def iterator(self):
return LinkedList.Iterator(self)
def __init__(self):
self.head = None
def addFirst(self, item):
newNode = Node(item, self.head)
self.head = newNode
def append(self, item):
raise NotImplementedError()
def removeFirst(self):
raise NotImplementedError()
def print(self):
currentNode = self.head
while (currentNode != None):
print(currentNode.item, end=" ")
currentNode = currentNode.next
Übung: Implementieren Sie die fehlenden Methoden!
Dank dieses ADTs ist es nun sehr einfach die Liste zu benutzen.
l = LinkedList()
l.addFirst("last")
l.addFirst("second")
l.addFirst("first")
l.print()
first second last
it =l.iterator()
while (it.hasNext()):
print(it.next())
first second last
Wir können eine Liste auch als rekursive Datenstruktur interpretieren. Die Definition ist grundsätzlich dieselbe wie bei der Klasse Node. Um die rekursive Struktur klarer zu machen, führen wir hier jedoch eine neue Klasse ein, die die Intention klarer macht.
class LList:
def __init__(self, head, tail):
self.head = head
self.tail = tail
Die einfachste Instanz der rekursiven Liste ist die Leere Liste, die wir wir folgte definieren
emptyList = LList(None, None)
Eine etwas kompliziertere Liste lässt sich einfach durch Schachtelung konstruieren.
l = LList("first", LList("second", LList("third", emptyList)))
Die rekursive Definitionführt zu einer sehr natürlichen, rekursiven, Implementation der Operationen. Der Code folgt einfach der Struktur die durch die Datenstruktur vorgegeben ist.
def printList(lst):
if lst == emptyList:
return ""
else:
return str(lst.head) +"," +printList(lst.tail)
def append(element, lst):
(head, tail) = (lst.head, lst.tail)
if tail == emptyList:
lst.tail = LList(element, emptyList)
else:
append(element, lst.tail)