Lineare Datentypen: die Liste
Um Elemente in einem Programm zu speichern, wurden bisher
Variablen und Arrays benutzt. In einer Variablen lässt sich nur ein Wert
speichern; ein Array speichert zwar mehrere Elemente, aber die Anzahl der
Elemente muss in der Regel im Voraus festgelegt werden. Möchte man beliebig
viele Elemente speichern können, muss man Listen benutzen. Listen tauchen in
vielen Anwendungen auf, z.B. bei der Nutzung von WhatsApp oder anderen
Messenger Programmen. Was geschieht, wenn eine Nachricht kommt? Die letzte
Nachricht steht am Ende einer Liste. Oder E-Mails: in der Regel steht die
neueste Mail an erster Stelle. Man kann diese Liste aber auch anders
anordnen. Was aber passiert, wenn z.B. die Speicherkarte voll ist und man
Nachrichten löschen muss? Mit diesen und anderen fragen beschäftigt sich der
folgende Text.
Elemente können zufällig oder linear angeordnet werden. Eine
einzelne Variable kann irgendwo im Speicher abgelegt werden, ein Array kann
nur linear in einem Speicherblock eingerichtet werden. Jedes Element im
Array hat einen Vorgänger und einen Nachfolger. Ausgenommen sind das erste
und das letzte Element: das erste Element hat keinen Vorgänger und das
letzte keinen Nachfolger. Bleiben wir noch beim Array: Die Datenstruktur
Array speichert eine fixe Anzahl von gleichartigen Elementen, die im
Speicher aneinander gefügt werden. Die Größe dieses Arrays wird beim
Erzeugen des Array-Objektes zu Beginn festgelegt. Da die die Größe nicht
mehr geändert werden kann, spricht man auch von einer statischen Struktur
(Hinweis: in einigen Programmiersprachen kann man dynamische Arrays anlegen.
Deren Größe kann im Verlauf des Programmes angepasst werden.) Jedem Element
ist eine Zahl zugewiesen. Mit diesem Index kann gezielt auf ein spezielles
Element zugegriffen werden. Wieso funktioniert das? Jedes Objekt befindet
sich an einer bestimmten Adresse im Speicher. Da alle Objekte linear
abgelegt werden und sie jeweils denselben Speichergröße belegen, kann man
die notwendige Adresse eines Objektes berechnen, wenn man seinen Index und
seine Größe kennt. Die Adresse des Arrays ist gleichzeitig die Adresse des
ersten Elements. Die Adresse von array[4] berechnet sich vereinfacht wie
folgt: Adresse(array[4])=Startadresse (array) + (4 * Elementgröße). Damit
ist auch geklärt, warum das erste Arrayelement den Index 0 hat
Die Liste speichert eine variable Anzahl von Elementen, sie
ist also dynamisch. Die Elemente können an einer beliebigen Stelle des
Speichers stehen. Die einzelnen Elemente sind miteinander über Zeiger
verkettet. Damit ergibt sich wie beim Array eine lineare Struktur mit Anfang
und Ende. Allerdings kann man auf einzelne Element nicht direkt
zugreifen; die ganze Liste muss sequentiell vom Anfang an durchsucht werden.
Wie sieht ein Vergleich der beiden Strukturen aus, wenn man
den Aufwand für das Einfügen und das Löschen eines Elementes und den Zugriff
auf ein Element betrachtet? Um ein Element in ein Array einfügen zu können,
benötigt man einen freien Platz im Array. An den Index des ersten freien
Platzes kann man direkt das neue Element einfügen. Beim gezielten oder
sortiertem Einfügen entscheidet die Position des neuen Elementes über den
Aufwand. Möchte man das neue Element am Anfang des Arrays einfügen, müssen
alle Elemente des Arrays um einen Platz verschoben werden. Statistisch muss
beim gezielten Einfügen die Hälfte aller Einträge verschoben werden. Beim
Einfügen eines Elementes in eine Liste muss wie beim Array zuerst die
richtige Position gefunden werden. Anschließend müssen nur Zeiger geändert
werden. Kein einziges Element wird verschoben. Der Vorteil liegt hier also
klar bei der Liste. Beim Löschen eines Elements entsteht im Array eine
Lücke. Werden dann neue Elemente eingefügt, muss man das Array sequentiell
durchgehen, um den freien Platz zu finden oder nach jedem Löschvorgang
Elemente wie beim Einfügen verschieben. Wie beim Einfügen müssen dann im
Durchschnitt die Hälfte aller Elemente verschoben werden. Das Löschen eines
Elements in der Liste verläuft ähnlich einfach wie das Einfügen: man muss
das zu löschende Element sequentiell suchen und entsprechend Zeiger
verändern. Auch hier geht der Punkt an die Liste. Der Zugriff auf ein
bestimmtes Element des Arrays erfolgt direkt über den Index; bei der Liste
muss statistisch die Hälfte aller Elemente angesehen werden. Der Vorteil
liegt hier beim Array.
Auf den verlinkten Seiten befinden sich
Beispiele für die Anwendung der Liste einschließlich der
Klasse Liste:
Materialien zu diesem Themenbereich findet man unter der
folgenden Adresse:
Materialien zum KLP GOSt Informatik Grundkurs
(Qualifikationsphase Q1-GK)
Materialien zum KLP GOSt Informatik Leistungskurs
(Qualifikationsphase Q1-LK)
Hilfreich ist auch der folgende Download:
Lineare Datentypen: Die Liste (Leitprogramm)
