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. 

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.

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:

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.