Datenspeicherung und DatenstrukturenChainsBei verketteten Trees: ListenListen (Datenspeicherung und Datenstrukturen: ChainsChains) werden die einzelnen Datenspeicherung und Datenstrukturen: RecordsRecords im Speicher nicht aufeinanderfolgend abgelegt. Ihre Lage ist überhaupt völlig beliebig! Um den Zusammenhalt einer Datei zu wahren, wird jeder Datenspeicherung und Datenstrukturen: RecordsRecord gemeinsam mit einem oder mehreren Zeigern abgespeichert, die auf das folgende, vorhergehende oder ein sonstwie benachbartes Listenelement zeigen. Einfache verkettete Liste:Startpointer ---+
|
+------------|---------- Pointer <------------+
| | Record2 |
| | |
| | |
| +--> Pointer --------> Pointer --+
| Record0 Record1 +---> Pointer -+
| | Record5 |
| | |
| | |
+---------> Pointer ---------------------------> Pointer ----+ NIL <--+
Record3 Record4
Diese Grafik zeigt eine Chains: Einfache verkettete Liste:einfache, verkettete Liste mit sechs Elementen. Wie man sieht, können die einzelnen Elemente überall im Speicher liegen, und werden nur über die Pointer miteinander verbunden. Die zeigen in diesem Beispiel immer nur auf das nächstfolgende Element. Zwei weitere, wichtige Eigenschaften einer solchen Verkettung sind erkennbar: Zum Einen muss der Startpunkt, also die Adresse des ersten Kettenelements bekannt sein und zum Anderen muss das Kettenende durch einen speziellen Pointer gekennzeichnet werden. Bei Z80-Systemen verwendet man dazu sehr oft einfach die Adresse &0000. In diesem Bereich liegen ja die ROM-Konfiguration: RestartsRestarts und es ist normalerweise unmöglich, hier Daten abzuspeichern. Die Bezeichnung 'NIL' für diesen Endpointer steht dabei für 'not in Trees: Listenlist', eine typische Antwort von LISP. Um also ein spezielles Datenelement aufzufinden, muss man auch hier, egal ob man FLRs oder VLRs verkettet hat, beim ersten Element anfangen und sich mittels der Kettungspointer von einem zum anderen Datenspeicherung und Datenstrukturen: RecordsRecord durchhangeln, bis man das gewünschte Datum erreicht hat. Verkettete Trees: ListenListen werden deshalb fast nie eingesetzt, wenn ein wahlfreier Zugriff auf die einzelnen Elemente eines Feldes gewünscht ist. Verkettete Trees: ListenListen haben, bis auf den erhöhten Speicherplatz-Verbrauch für die Kettungspointer, ansonsten aber fast nur noch Vorteile: Die Anzahl der Datenspeicherung und Datenstrukturen: RecordsRecords in einer Datei kann beliebig schwanken. In einer Dateiverwaltung ist folgender Fall denkbar: Eine Datei wird eingerichtet und umfasst noch kein einziges Element. Es wird praktisch nur ein Startpointer eingerichtet, der gleichzeitig Endpointer ist. Er zeigt auf NIL. Eine solche Trees: ListenListe verbraucht noch keinen Speicherplatz! Erst wenn nach und nach Datensätze (Datenspeicherung und Datenstrukturen: RecordsRecords) eingegeben werden, beanspruchen diese auch Platz. Das Einfügen und Wieder-Aushängen von einzelnen Datemnsätzen ist äußerst komfortabel: Man braucht nicht alle nachfolgenden Datenspeicherung und Datenstrukturen: RecordsRecords um einen Platz zu verschieben, sondern verändert nur einen Pointer: Aushängen eines Records aus einer Chain:Startpointer ---+
|
+------------|---------- Pointer <------------+
| | Record2 |
| | |
| | |
| +--> Pointer --------> Pointer --+
| Record0 Record1 +---> Pointer -+
| | Record5 |
+----------------------------------------+ | |
. | | |
........... Pointer .....................+-----> Pointer ----+ NIL <--+
Record3 Record4
Datenspeicherung und Datenstrukturen: RecordsRecord 3 aus dem vorherigen Bild wurde einfach dadurch ausgehängt, dass der Pointer in Datenspeicherung und Datenstrukturen: RecordsRecord 2 verstellt wurde. Dieser zeigt jetzt auf Datenspeicherung und Datenstrukturen: RecordsRecord 4, wodurch Datenspeicherung und Datenstrukturen: RecordsRecord 3 nicht mehr erreichbar ist. Der Pointer von Datenspeicherung und Datenstrukturen: RecordsRecord 3 zeigt möglicherweise auch weiterhin auf Datenspeicherung und Datenstrukturen: RecordsRecord 4, was aber ohne Bedeutung für diese Kette ist. Einhängen eines Records in eine Chain:Startpointer ---+
|
+------------|---------- Pointer <------------+
| | Record2 |
| | |
| | |
| +--> Pointer --+..+--> Pointer --+
| Record0 | | Record1 +---> Pointer -+
| | | | Record5 |
+---------------------------|--|---------+ | |
+--------------------+ | | | |
+--> Pointer -----------+ +-----> Pointer ----+ NIL <--+
Record3 Record4
In diesem Beispiel wurde der ehemalige Datenspeicherung und Datenstrukturen: RecordsRecord 3 zwischen Datenspeicherung und Datenstrukturen: RecordsRecord 0 und Datenspeicherung und Datenstrukturen: RecordsRecord 1 eingehängt. Dazu musste einfach der Pointer, der von 0 nach 1 zeigte, 'aufgetrennt' werden. Pointer 0 zeigt nuch auf Pointer 3 und dieser wiederum auf Pointer 1. Beim Einfügen oder Aushängen verändern sich natürlich die Platznummern aller nachfolgenden Datenspeicherung und Datenstrukturen: RecordsRecords. Das kann aber vermieden werden, indem ein neuer Datenspeicherung und Datenstrukturen: RecordsRecord eben nicht nur eingehängt, sondern ein Listenelement, dessen Platz er einnehmen soll, aus der Kette entfernt wird: Ersetzen eines Records in einer Chain:Startpointer ---+
|
+------------|---------- Pointer <------------------- Pointer <--+
| | Record2 . Record6 |
| | . |
| | +---------------------------------+
| +--> Pointer --+ |... Pointer ...
| Record0 | | Record1 +---> Pointer -+
| | | | Record5 |
+---------------------------|--|---------+ | |
+--------------------+ | | | |
+--> Pointer -----------+ +-----> Pointer ----+ NIL <--+
Record3 Record4
In diesem Beispiel wurde Datenspeicherung und Datenstrukturen: RecordsRecord 1 ausgehängt und ersatzweise Datenspeicherung und Datenstrukturen: RecordsRecord 6 eingefügt. Datenspeicherung und Datenstrukturen: RecordsRecord 1 wurde also durch Datenspeicherung und Datenstrukturen: RecordsRecord 6 ersetzt. Dadurch rücken die nachfolgenden Elemente keinen Platz vor oder zurück. |