Direkt zur Hauptnavigation springen Direkt zum Inhalt springen Jump to sub navigation

Lineare Liste

Lineare Liste

Wenn wir auf die Instanz eines Objekttyps zugreifen, z. B. auf einen Patienten mit dem Variablennamen "aktuellerPatient", so wird dieser Namen mit dem Beginn eines Speicherbereichs verknüpft, der die Patientendaten in irgendeiner Reihenfolge enthält. "Suchpatient" verweist auf dem Start eines anderen Speichersegments.

Zur besseren Veranschaulichung beschränken wir uns auf den Nachnamen und gehen davon aus, dass dieser Name in eine Speicherzelle passt. 

Adresse1001 1002 1003 1004 
SpeicherplatzHauptmann Brecht Heine Fontane

Reihen wir nun Patienten oder andere Daten durch eine Anordnung aneinander, so enthält jeder Datensatz selbst einen Verweis auf den nächsten Datensatz. In unserem Beispiel enthält es neben dem Namen noch einen Zeiger auf das nächste Element. Dieser Zeiger ist wiederun nur die Speicheradresse des Folgedatensatzes.

Adresse1001 1002 1003 1004 
SpeicherplatzHauptmann Brecht Heine Fontane 
Zeiger1002 1003 1004   

Jeder Datensatz besteht aus einem Knoten, der die Daten aufnimmt und dem Zeiger, der auf das nachfolgende Element verweist. Diese Struktur heißt einfach verkettete Liste, ihre sequentielle Ordnung wird durch eine Zeigerverkettung gebildet. Auf den Kopf der Liste muss ebenfalls ein Zeiger gerichtet sein, um den Zugriff zu ermöglichen. Um den Schwanz der Liste erkennbar zu machen, wurde ein Zeiger vereinbart, der auf eine feste, sonst nicht benutzte Speicherstelle weist - in einigen Programmiersprachen nil
 So kann man sich jetzt die Anordnung der Datensätze im Speicher nach dem Löschen von zwei Einträgen und dem Anfügen eines neuen so vorstellen:

Speicher-
adresse
KnotenZeiger
1000 (Kopf) 1002 
1001    
1002 Brecht 1003 
1003 Heine 1005 
1004     
1005 Döblinnil

Die Inhalte der Speicherbereiche 1001 und 1004 könnten auch stehen bleiben, da kein Zeiger meht auf sie verweist, sind sie in der Liste nicht mehr zugreifbar. 
 

Redaktionell verantwortlich: Frank Oppermann