Verzettelte Liste

Aus Stupidedia, der sinnfreien Enzyklopädie!
Version vom 23:45, 15. Feb. 2013 von Sebus (Diskussion | Beiträge)

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Wechseln zu: Navigation, Suche

In der Informatik bezeichnet die verzettelte Liste eine dynamische Datenstruktur, die mehrere Objekte im Speicher mit einander verknüpft, indem sie mit Hilfe von Zetteln überall dezente Hinweise auf die einzelnen Objekte verteilt.

Motivation und Konzept

Ein Bot durchstöbert verzettelte Listen

Bei der herkömmlichen Liste (oder auf Deutsch: Array) stehen einfach alle Daten sauber hinter einander. Das hat den Vorteil, dass man problemlos alles wiederfindet. Der Nachteil ist, dass man sich vorher überlegen muss, welche Daten wohin sollen und wie viel Platz dafür benötigt wird, sonst muss hinterher dauernd alles umsortiert werden und das ist anstrengend. Hier liegt das Problem. Der Informatiker ist, auch wenn das außer ihm selbst niemand einsieht, vor allem ein Künstler, ein kreativer Kopf mit langen Haaren (sogar die Männer!) und Zauselbart (sogar die Frauen!). Er weiß natürlich nicht vorher, wie viel Platz er braucht oder in welcher Reihenfolge irgendetwas gespeichert werden soll. Auch nicht ungefähr.

Die verzettelte Liste löst dieses Problem auf äußerst elegante Weise. Sie erlaubt dem Informatiker die künstlerische Freiheit, seine Daten ganz nach Belieben auf den Stapel werfen zu können und sorgt mit Hilfe kleiner Notizzettel dafür, dass sie trotz größtmöglicher Unordnung wieder gefunden werden. Das Konzept ist vergleichbar mit einer Schnitzeljagd: Jedem Objekt wird ein Zettel angeheftet, auf dem die Speicheradresse des nächsten Objekts vermerkt ist, so dass man sich von Objekt zu Objekt hangeln kann, egal wie verstreut diese gespeichert sein mögen. Führt die Schnitzeljagd irgendwohin, wo es Gras gibt, wird sie auch als Hashmap bezeichnet und erfreut sich besonders großer Beliebtheit.

Bei mehrfach verzettelten Listen verweisen optionale zusätzliche Zettel auch noch auf das vorige Objekt, so dass rückwärts navigiert werden kann, sowie auf ähnliche oder aus anderen Gründen gerade nennenswerte Objekte; weitere Zettel können andere hilfreiche Informationen über die Liste und ihre Elemente enthalten oder auch einfach die persönlichen Ansichten des Compilers über die Gesamtsituation dokumentieren.

Nicht mehr benötigte Zettel (etwa weil die zugehörigen Daten gelöscht wurden) wandern in den Papierkorb und werden recycelt. Es handelt sich um ein enorm durchdachtes System.

Kritik

Neben den schwer zu leugnenden Vorzügen verzettelter Listen gibt es auch den einen oder anderen Kritikpunkt. So gilt es unter Puristen als erstrebenswert, mit Hilfe der EDV langfristig das Ideal des papierlosen Büros zu erreichen. Derlei Anstrengungen werden natürlich ad absurdum geführt, wenn der Computer seinerseits mit Abermillionen von Zetteln arbeitet.

Neben diesem eher ideologischen Dilemma können aber auch praktische, also echte Schwierigkeiten im Umgang mit verzettelten Listen auftreten. Das häufigste Problem ist der so genannte Papierstau. Beim Drucker schon ärgerlich genug, stellt er im wesentlich feiner gearbeiteten Prozessor eine absolute Katastrophe dar und endet nicht selten mit der irreparablen Zerstörung der Hardware. Ursache ist meist die enorme Taktfrequenz moderner Prozessoren, die Millionen und Milliarden von Zetteln pro Sekunde beschriften, so dass die winzigste Unregelmäßigkeit – ein kleines Eselsohr reicht völlig aus – sofort außer Kontrolle geraten kann. Spätestens wenn Multithreading zum Einsatz kommt (eine spezielle Form elektronischer Schizophrenie, bei der der Prozessor sich für zwei oder mehr Geräte hält und angeblich mehr Arbeit leisten kann), können solche Vorfälle kaum noch mit letzter Sicherheit ausgeschlossen werden.

Darüber hinaus besteht auch die banale Gefahr des Datenverlusts, wann immer Zettel beschädigt werden oder verloren gehen. Eine kleine CoffeeOverflowException reicht schon aus, um schätzungsweise zehn bis hundert Millionen Zettel auf einmal unbrauchbar zu machen, was bei stark fragmentierten Daten einem Verlust von vielen Gigabytes entsprechen kann.


Linktipps: Faditiva und 3DPresso