Auf Arrays kann man hervorragend sehr schnell zugreifen, da alle Einträge zwischen der 0. und der letzten Position in einem großen, zusammenhängendem Speicherblock aufgereiht liegen: Die Daten liegen im Array (engl. für 'Reihe'). Bei manchen Systemen können diese großen Speicherblöcke zu Problemen führen, weil das Betriebssystem gar nicht so große, zusammenhängende Speicherblöcke liefern kann. Dieser Grund ist bei heutigen PCs und modernen Betriebssystemen nicht mehr so ausschlaggebend. Viel wichtiger ist heutzutage, dass ein volles Array nicht einfach vergrößert werden kann. Man kann nicht einfach mal Speicher dahinter anbauen. Arrays können nicht vergrößert werden. Das Array muss zunächst in ein größeres Array kopiert werden, um anschließend neue Elemente hinzuzufügen und das ist sehr aufwendig. Entfernt man Elemente, verbrauchen die nun unbenutzten Elemente weiterhin Speicherplatz und man muss sich merken, welche Elemente benutzt werden und welche nicht. Zwischen zwei belegte Elemente kann man kein neues Element einfügen, auch hier müssen erst reihenweise Elemente aufwendig verschoben werden. Es gibt also gute Gründe nach alternativen Lösungen zu suchen. Für dieses Standardproblem gibt es auch eine Standardlösung: Die Liste.

Eine Liste besteht aus einer beliebigen Menge an Elementen. Wird von Listen-Elementen gesprochen, so werden diese häufig Node (auf Deutsch 'Eintrag') genannt. Eine Node enthält die Daten, wie sie auch im Array vorliegen, aber zusätzlich auch einige Verwaltungsdaten. Diese Verwaltungsdaten sind notwendig, um flexibel Nodes in die Liste eintragen und entfernen zu können.

Sind Listen noch nicht bekannt, empfehle ich die Kapitel nacheinander zu lesen.

• einfache Listen
• Listenköpfe
• doppelt verkettete Listen
• Rückreferenz auf den Listenkopf

Während das Array ausschließlich die Daten speichert, in den Bespielen also vom Typ struct Address, bedeutet eine Liste je nach Ausbau einen Speichermehrbedarf von ein bis drei Zeigern (je Zeiger 4 Byte auf 32Bit Systemen bzw. 8 Byte auf 64 Bit Systemen). Zusätzlich kommt der Listenkopf mit ein bis zwei Zeigern. Schwerwiegender kommt dazu der vom Betriebssystem benötigte Speicher, der für die Speicherverwaltung verwendet wird und der Rechenaufwand, um den Speicher zu verwalten. Dieser Overhead ist bei Arrays nicht vorhanden. Häufiges Anfordern und Freigeben von Listenelementen fragmentiert weiterhin den Speicher, was bei aufwendigen Programmen auch heute noch in seltenen Fällen zu Problemen führen könnte. Neben der Rechenzeit, die für das Anlegen und Freigeben von Elementen verbraucht wird, entsteht ebenso ein deutlicher Mehraufwand für das Durchlaufen und Verketten der Liste.

Hat ein Element nur wenig Daten, wie ein einzelnes Integer, so ist der Speicheroverhead deutlich größer als die Daten selbst. Werden nun nur wenige Integer verwendet, so ist ein kleines Array effizienter.

Diese zum Array zusätzlichen Kosten sind zu berücksichtigen, wenn Listen eingesetzt werden. Müssen jedoch große Datenmengen verschoben werden, um einzelne Daten einzuschieben, sind Listen deutlich effizienter. Sie spielen ihre Vorteile aus, wenn Daten häufig umorganisiert werden müssen.

Diskussionsthread