In der Realität werden Strukturen geschaffen, die der Verwaltung von Einzeldaten
oder gar Klassen dienen. Zum Beispiel dient Einwohnerkartei eines kleinen Ortes der
Erfassung von Wohndaten, Familiengröße ,-stand ...etc.
Als Verwaltung würde sich eine z.B. ein Arraystruktur anbieten. Diese hat aber eine
maximale Zahl von Einträgen. Damit würde Sie der Anforderung an eine Kartei deren
Datenmenge ständig wächst oder schrumpft nicht gerecht werden.
Definiert man, um sicher zu sein, eine große Anzahl von Listenplätzen, würde unter Umständen
unnötig
viel Speicherplatz trotz einer potenziellen Unterbelegung zur Verfügung gestellt werden müssen. Der Ausweg ist die
Schaffung von dynamischen Datenstrukturen. Solche Datenstrukturen stellen
zum Beispiel verkettete Listen dar.
01 class Knoten : 02 03 def __init__(self,value) : 04 self.value = value 05 self.next = None 05 06 def get_value (self) : 07 return self.value 08 09 def set_next (self, node) : 10 self.next = node 11 12 if __name__=="__main__" : 13 14 test = Knoten (5) 15 test.set_next (Knoten (3)) 16 print text.get_value () 17 print text.next.get_value() |
Die Klasse Liste kann nun die Instanzen der Klasse Knoten verwenden und und diese nacheinander in die Liste einfügen. Am Beispiel des Anfügens eines Knotens append an eines bestehende Liste soll diese Prinzip verdeutlicht werden.
01 class Liste : 02 03 def __init__(self) : 04 self.liste = None 05 06 def append (self, elem) : 07 M = self.liste 08 K = Knoten (elem) 09 if M is None : 10 self.liste = K 11 return 12 else : 13 while M.next is not None : M = M.next 14 M.next = K |
Um die Klasse Liste zu implementieren sind neben den gegebenen weitere Methoden zu implementieren. Die wichtigsten sind dabei :
Der Vorteil einer doppelt verketteten Liste besteht in der Möglichkeit, sich nicht
nur vorwärts durch die Liste zu bewegen, sondern auch in die entgegengesetzte Richtung.
Dadurch werden Suchfunktionen erheblich verkürzt, gleichzeitig ist die dynamische Verwaltung
der Daten gesichert.
Es besteht hier allerdings die Notwendigkeit einer Neuimplemntierung
des Knotenmoduls und einer Anpassung der Methoden. Auch für diesen Fall das entsprechende
Bespiel.
01 class DKnoten : 02 03 def __init__(self,value) : 04 self.value = value 05 self.left = None 06 self.right = None 07 08 def get_value (self) : 09 return self.value 10 11 def set_left (self, node) : 12 self.left = node 13 14 def set_right (self, node) : 15 self.right = node |
Die append Methode gestaltet sich mit dem entsprechenden Import ähnlich.
02 from DKnoten import * 02 01 class DListe : 02 03 def __init__(self) : 04 self.liste = None 05 06 def append (self, elem) : 07 M = self.liste 08 K = DKnoten (elem) 05 09 if M is None : 10 self.liste = K 11 return 12 else : 13 while M.right : M = M.right 14 K.left = M 14 M.right = K |