Liste
Aus TriagonyWiki
Eine Liste ist eine Speicherstruktur in der Informatik.
Inhaltsverzeichnis |
Definition
Eine Liste ist eine dynamische Speicherstruktur, welche aus verketteten Elementen besteht. Wobei ein Element aus einem Kopf und einer bestimmten Anzahl an Zeigern oder Referenzen besteht. Der Kopf bildet dabei den Speicher. Ein Element einer Liste, kann dabei mehrere Zeiger oder Referenzen auf andere Elemente haben. Auch müssen diese Zeiger nicht auf das nächste oder das vorherige Element verweisen, sondern können auch auf ein bestimmtes zeigen. Durch all diese unterschiedlichen Konstellationen bekommen die Listen ihren Namen.
Dies ist eine einfach verkettete Liste. Sie hat genau einen Zeiger auf ein nachfolgendes Element. Jedoch gibt es viele verschiedene Formen von Listen. Die einfach verkettete Liste ist die einfachste Speicherform einer Liste. Komplexer jedoch wird es mit mehrfach verkettete Listen, Beispielsweise mit einer doppelt verkettete Liste oder einer Ringliste. Die Namen sagen meistens schon, wie diese Liste konzipiert ist.
Vor- und Nachteile von Listen
Vorteile
Eine Liste ist eine dynamische Speicherstruktur, das heißt die Anzahl der Element muss zum Zeitpunkt der Initialisierung nicht feststehen. Es ist einzig und allein wichtig, dass die Information auf das nachfolgende Element nicht verloren geht. Daraus resultiert, dass die Element einer Liste in beliebigen Speicherzellen liegen können. Diese Speicherform muss also nicht linear sein. Daraus ergibt sich auch mit der größte Vorteil einer Liste. Sie ist in ihrer Größe dynamisch. Sind wenige Elemente in der Liste gespeichert, verbraucht sie auch weniger Speicher. Sind hingegen mehr Elemente in einer Liste, wird mehr speicher verbraucht.
Nachteile
Ein Nachteil von einer Liste ist, dass sie mehr Speicher verbraucht, als eine lineare Speicherstruktur mit gleicher Anzahl an Elementen. Das hat den Grund, das die Information auf das nachfolgende Element mit gespeichert werden muss. Zudem ist das auslesen von Elementen problematisch. Da man ohne den Vorgänger nicht weiß, wo ein Element im Speicher platziert ist, muss man erst immer eine bestimmte Anzahl von Knoten durchlaufen, um zu dem Element zu kommen, welches man auslesen möchte. Dadurch ist eine Liste langsamer als eine lineare Speicherstruktur.
Einsatzgebiete
Wo werden Listen also eingesetzt? Natürlich dort, wo man nicht weiß wie viele Elemente gespeichert werden müssen.
Als kleines Beispiel möchte ich hier mal einfach eine Benutzerverwaltung anführen. Wir wissen nicht, wie viele Benutzer sich auf unserem System anmelden wollen. Würden wir dies mit einem Array realisieren wollen, Hätten wir das Problem, dass wir nur eine bestimmte Anzahl in unser System aufnehmen könnten. Oder wir müssten Das Array sobald es voll ist neu erstellen, mit einem größeren Bereich. Das hat zum einen den Nachteil, dass erstmal mit dem initialisieren des Arrays ein bestimmter Bereich des Speichers weg ist. Denn dieser wird ja für das Array vorbehalten. Zum zweiten ist das neu erstellen des Arrays mit einem größeren Bereich sehr langsam und speicherhungrig. Denn erstens muss ein neues Array initialisiert werden, welches größer ist. Aus dem alten Array müssen alle vorhandenen Werte kopiert werden und dann erst kann das alte Array freigegeben werden.
Mit einer Liste hat man diese Probleme nicht. Sie wird angelegt und verbraucht den Speicher, welchen die Daten für den Nutzer brauchen und die Referenzen. Außerdem können wir fast(!) endlos Benutzer speichern. Die einzige Einschränkung ist dort durch den RAM gegeben, welcher endlich ist.
