Doppelt verkettete Listen

Wir tauschen Speicher gegen Geschwindigkeit

Die doppelt verkettete Liste und die einfach verkettete Liste sind fast identisch. Der einzige Unterschied ist, dass unseren Listenelementen hier nicht nur ein Zeiger auf das nachfolgende Element, sondern auch auf das ihnen vorhergehende Element mitgegeben wird:

Auch der Listenkopf braucht natürlich Speicherplatz für einen Zeiger auf einen Vorgänger, da es ja passieren könnte, dass wir vor dem aktuellen Listenkopf noch ein neues Element einfügen wollen.

So ist es auf einer doppelt verketteten Liste möglich, schneller zu "navigieren". Das bezahlen wir allerdings natürlich auch mit zusätzlichem Speicherbedarf.

Allgemein ist dir vielleicht aufgefallen, dass es eine Art Austausch zwischen Speicherbedarf und Zugriffsgeschwindigkeit gibt. Denn auch ein Array kann in fast jedem Fall benutzt werden, man muss schließlich das Array nur groß genug machen, damit man sicher ist, dass es nicht überläuft.

Das geht vielleicht nicht in allen Fällen, aber gewiss in vielen. Gleichzeitig ist es natürlich auch mit erheblichem zusätzlichem Speicherbedarf verbunden.

Aufgabe 1

Entscheide in den folgenden Fällen, welche der drei vorgestellten Datenstrukturen optimal ist und begründe, warum.

(a) Ein mittelständischer Buchhändler erweitert sein Angebot durch einen Versandhandel. Der Buchhändler möchte nun alle seine Aufträge speichern. Er muss nicht oft auf diese zugreifen, will sie aber archiviert halten.

(b) Ein Lehrer will seine Klasse von dreißig Schülern am Computer "managen", also deren mündliche und schriftliche Leistung festhalten. Er hat keine extrem hohen Ansprüche an Geschwindigkeit, freut sich aber, wenn es flott geht.

(c) Der erwähnte jetzt nicht mehr mittelständische Buchhändler will jetzt anfangen, auch seinen Bücherbestand am Computer zu archivieren. Er kauft und verkauft jeden Tag mehrere hundert Bücher und das soll permanent in seinen Daten dokumentiert werden und aufgrund seiner begrenzten Zeit möglichst schnell gehen.

(d) Ein anderer Buchhändler will sich ein Beispiel an dem ersten Buchhändler nehmen und führt auch einen Versandhandel ein. Auch er möchte seine Aufträge speichern, da er aber oft einzelne Aufträge vergisst, muss er häufig irgendwelche Aufträge (manchmal auch sehr alte) anschauen. Er hofft natürlich, dass er bald ähnlich erfolgreich wie sein Vorbild ist, hat aber aktuell nur einen sehr kleinen Kundenstamm.