Doppelt verkettete Liste Teil 1

Listen sind eine grundlegende Datenstruktur in der Informatik - im alltäglichen Leben übrigens auch. Daher sollte der Zugang leicht fallen. Schon das Aufstellen eines Einkaufszettels ist eine Liste:

Eier
Brot
Bananen
Tomaten
Pfifferlinge
Auberginen

Eine ganz offensichtliche Funktionalität ist das Anhängen eines neuen Datensatzes am Ende, ohne Rücksicht auf irgend eine Sortierung. Das sollte eine per Software realisierte Liste also mindestens bieten - neben der ohnehin selbstverständlichen Ausgabe der Liste.

Fast von alleine stellt sich die Frage, warum und ob man das nicht einfach als Array realisiert? Wer nicht weiß, was ein Array ist, braucht sich hier nicht weiter den Kopf darüber zu zerbrechen, ansonsten gilt: Bei einem Array muss von vornherein festgelegt werden, welche Größe es hat - und damit handelt man sich zwei Probleme ein:

1. Will man Speicherplatz sparen und legt das Array relativ klein an, dann kommt früher oder später die Situation, in der es zu klein ist - Abhilfe: Änderungen im Quellcode.
2. Will man dieses Problem umgehen, legt man das Array sehr groß an; in den meisten Fällen ist das eine sehr große Speicherplatzverschwendung und dennoch kann es irgendwann einmal immer noch zu klein sein.

Mit einer Liste haben wir diese Probleme nicht, denn sie ist immer nur so lang wie gerade nötig. Wir verschwenden also niemals Speicherplatz und sie kann nie zu kurz sein.

Wir können jetzt schon die beteiligten Klassen identifizieren: Eine Klasse ist die Liste als solche, eine weitere Klasse ist ein Listeneintrag - das genügt schon und das Klassendiagramm sieht zunächst wie folgt aus:

Diese beiden Klassen hängen miteinander zusammen über eine Assoziation und zwar dergestalt, dass die Liste aus Listeneinträgen besteht. Eine solche Assoziation wird Aggregation genannt; in der Darstellung wird die Raute bei der aggregierten Klasse eingezeichnet. Die Kardinalitäten besagen, dass 1 Liste aus mindestens 2 Listeneinträgen besteht - warum das so ist, lernen wir später.

Die Grundlagen sind gelegt, nun müssen wir uns zunächst Gedanken machen, wie das denn alles funktionieren soll - weiter mit Teil 2.