Aktuelle Version vom 27. August 2011, 18:54 Uhr

Listen

Liste / Tabelle

Man muss verkettete Listen von Tabellen unterscheiden. Bei einer Tabelle (Array) sind gleich große Elemente hintereinander im Speicher angeordnet und können durch einen „Index“ (= Element-Nummer) gezielt adressiert werden. Bei Bascom hat übrigens das erste Tabellenelement den Index „1“, bei C (z.B. GCC) beginnt der Index bei „0“ Beides hat was, aber darauf wollen wir hier nicht eingehen.
In einer verketteten Liste kann das Auffinden eines bestimmten Elements nur erfolgen, indem man der Verkettung vom ersten Element weg folgt, bis man das gesuchte Element gefunden hat.
Wenn die Elemente umsortiert werden sollen, dann reicht es, die Verkettungs-Zeiger zu verändern, bei einer Tabelle muss man die gesamten Daten verschieben. Ebenso, wenn man einzelne Element entfernen oder einfügen will.

Bei verketteten Listen kann sich jedes Element irgendwo im Speicher befinden. Daher gibt es:

• einen "ListHeader", der einen festen Platz in der Gesamtdatenstruktur hat und auf das das Anfangselement verweist.
• Jeder Datenelement bekommt zusätzlich zu seinen eigentlichen Nutzdaten einen "Element-Header".

Dieser Element-Header befindet sich zweckmäßigerweise ganz vorne in seiner Struktur. Dadurch ist die Adresse des Elements gleichzeitig auch die Adresse dieses Headers. Die Listen-Manipulations-Routinen brauchen ja für ihre Funktionen nur den jeweiligen Header und kümmern sich nicht um die übrigen Daten. Aus diesem Grunde können die Listen-Elemente auch völlig unterschiedlich lang sein und völlig unterschiedliche Strukturen haben.

In diesem Artikel sind nur die Header und deren Inhalte das Thema, die "Nutzdaten" sind aus dieser Sicht nur Anhängsel und werden in den Bildern wohl etwas vernachlässigt (oder gar tw. weggelassen).

Verweise/Adressen

Ich werde in der Folge immer wieder unterscheiden zwischen „Verweis“ und „Adresse“ . Das wird zwar in vielen Fällen ein und dasselbe sein, aber eben nicht unbedingt. Bei einem Computer /PC mit 32-Bit Adressen (4 Byte) und keinen (kaum) Speicherproblemen ist die Verwendung der Adresse als Verweis sicher eine praktikable Methode. Auf einem µC reicht meistens eine 16-Bit (2Byte) Adresse, um eine 64k memory abzudecken. Aber wenn einem die 2 Byte für den Verweis je Element zu viel sind oder die 64k Adressraum zu wenig, muss man sich was überlegen. Das ist aber auch ein eigenes Thema. Bei meinen diversen Pseudo-Codes werde ich daher der Ordnung halber zwei Hilfs-Funktionen verwenden, die aus einem Verweis eine Adresse und umgekehrt machen. Ich gehe aber nicht drauf ein, wie diese Funktionen genau beschaffen sind.

• Verweis = makeVerweis(Adresse)
• Adresse = makeAdresse(Verweis)

Einfach verkettete Listen

jedes Element enthält im Header nur einen Verweis auf das folgende Element. Das letzte Element hat einfach (und meistens) den Wert NULL als Verweis. Man muss aber berücksichtigen, „0“ ist eine zumindest theoretisch mögliche Adresse. Der List-Header bei einer solchen Liste muss einen Verweis auf das erste Element haben. Ein zusätzlicher Verweis auf das aktuelle letzte Element hat nur Sinn, wenn ich auch am Ende der Liste einfügen will. Wird ohnehin immer an einer beliebigen Stelle eingefügt (sortierte Liste) oder immer nur ganz vorne (FILO = First-In Last-out) kann ich mir einen solchen Verweis auch sparen. Im schlimmsten Falle muss ich mir hat das letzte Element suchen (das ist das mit dem „NULL“-Verweis).

Liste mit zwei Elementen

Der List-Header verweist auf das erste Element und dieses auf das nächste, das durch den NULL-Verweis zeigt, dass es auch das letzte Element der Liste ist.

Grundsätzliche Methoden

• Erzeugen einer leeren Liste. List-Header werden die Verweise für erstes und letztes Element auf NULL gesetzt

• Einfügen in die ob. Liste mit zwei Elementen

• • Einfügen an erster Stelle, gegeben sind Head und das neue Element. Ist das neue Element gleichzeitig das erste in der Liste, muss es im Header aber auch als letztes eingetragen werden.
  • Einfügen an letzter Stelle, gegeben sind Head und das neue Element. Ist das neue Element gleichzeitig das erste der Liste, muss es im Header dann auch als erstes eingetragen werden.
  • Einfügen eines neuen Elements als Nachfolger eine anderen. Wird das neue Element aber dadurch das neue letzte Element, muss man das im List-Header korrigieren
• Abfragen nach Element-Adressen
  • Abfrage im List-Header nach dem ersten Element
  • Abfrage im List-Header nach dem letzten Element
  • Abfrage im Element-Header nach dem nächsten Element
• Entfernen (ausketten) aus der Liste (die Nutzdaten bleiben dabei aber erhalten)
  • Entfernen des ersten Elements. Man fragt den List-Header nach dem ersten Element. Dessen Nachfolger wird dann im List-Header das neue erste Element. Gibt's diesen Nachfolger aber garnicht, dann ist die Liste nun leer, also muss man den List-Header initialisieren (s.o)
  • Entfernen des letzten Elements. Das geht nur, wenn ich auch das bisher vorletze kenne, um es im List-Header nun als neue letztes zu verzeichnen.
  • Entfernen eines beliebigen Elements. Auch da muss ich den Vorgänger kennen.

Doppelt verkettete Listen

Bei eine „doppelt“ verketteten Liste enthält jeder Element-Header zusätzlich auch einen Verweis auf seinen Vorgänger, dadurch kann dann in der Liste direkt in beiden Richtungen navigiert werden. Dafür ist natürlich der Aufwand grösser.
Um sich nicht beim Einfügen und Entfernen immer wieder darum kümmern zu müssen, ob man sich am Anfang, mittendrin oder am Ende der Liste befindet und ob die Liste leer ist oder nicht, hat es sich bewährt, keine NULL-Verweise zu verwenden. Die entsprechenden Methoden sind einfacher (und sicherer), weil sie kein Wenn und Aber brauchen.
Durch die Vorwärts- und Rückwärts-Kett-Felder haben nun auch die Elemente einen wirklichen Header, der dafür aber völlig identisch mit dem List-Header ist.

• Header
  • Einen Verweis auf das nächste Element (beim List-Header ist das das erste)
  • einen Verweis auf das vorherige Element (beim List-Header ist das das letzte)

Liste mit vier Elementen

Das letzte Element verweist „vorwärts“ wieder auf den List-Header, das erste „rückwärts“ ebenfalls.

Grundsätzliche Methoden

• Erzeugen einer leeren Liste. Ein Header eine leeren Liste zeigt vorwärts und rückwärts auf sich selbst.

• Einfügen

Durch die Gleichsetzung von List- und Element-Header und den "Eigenverweis" im Header einer leeren Liste, gibt es nur zwei Einfügefunktionen. Zur Erläuterung:
"POSITION" ist die Adresse eines bereits in der Liste verketteten Headers
"NEW" ist die Adresse eines neuen Elements bzw. dessen Headers
"-.FWD" ist der "vorwärts"-Verweis eines dieser Header
"-.BCK" ist der "rückwärts"-Verweis

• • Einfügen "NEW" vor einem anderen Element ("POSITION")
    

NEW.BCK = POSITION.BCK
POSITION.BCK = makeVerweis(NEW)
NEW.FWD = makeVerweis(POSITION)
PREV = makeAdresse(NEW.BCK)
PREV.FWD = makeVerweis(NEW)

• • Einfügen "NEW" nach einem anderen Element ("POSITION")
    

NEW.FWD = POSITION.FWD
POSITION.FWD = makeVerweis(NEW)
NEW.BCK = makeVerweis(POSITION)
NEXT = makeAdresse(NEW.FWD)
NEXT.BCK = makeVerweis(NEW)

Verwende ich als "POSITION" die Adresse des LIst-Headers, entspricht:
Vor dem Header ==> eintragen als letztes Element Nach dem Header ==> eintragen als erstes Element

Liste mit einem Element

Liste mit vier Elementen

Hier das Beispiel "Einfügen irgendwo", wobei das Gleiche rauskommt, wenn ich nach dem zweiten oder vor dem dritten einfüge

• • Vorher

• • Nachher

• Entfernen gibt es nur in einer Version. Gegeben immer das Element, das gemeint ist (=POSITION).
  

"PREV" ist der Vorgänger des Elements, "NEXT" dessen Nachfolger
PREV = makeAdresse(POSITION.BCK)
NEXT = makeAdresse(POSITION.FWD)
NEXT.BCK = makeVerweis(PREV)
PREV.FWD = makeVerweis(NEXT)

Optional, nur der Ordnung halber. dadurch ist das entfernte Element auch als "keiner Liste zugehörig" gekennzeichnet
POSITION.FWD = makeVerweis(POSITION)
POSITION.BCK = makeVerweis(POSITION)

Was man vermeiden sollte: Ein „Remove“ des Headers würde zwar technisch funktionieren, aber alle List-Elemente wären dann verwaist und nicht mehr zu finden, weil sie keinen Header mehr haben.

• Lesen Nächstes. Gegeben der Listheader und
  • das zuletzt gelesene Element oder
  • nochmal der Listheader, wenn es das erste Element werden soll

NEXT = makeAdresse(POSITION.FWD)
ist NEXT gleich HEAD, dann gibt es kein weiteres Element (end-of-list)

• Lesen Vorgänger. Gegeben der Listheader und
  • das zuletzt gelesene Element oder
  • nochmal der Listheader, wenn es das letzte Element werden soll

PREV = makeAdresse(POSITION.BCK)
ist PREV gleich HEAD, dann gibt es kein weiteres Element (end-of-list)

Anwendungen

Man kann nicht generell sagen, ob man für irgendeine Anwendung mit einer einfach verketteten Liste auskommt oder unbedingt doppelt verketten muss. Die fehlende Rückwärtsverkettung lässt sich mit etwas Befehlscode eigentlich auch immer ersetzen. Man muss einen Kompromiss zwischen Performance und Speicherverbrauch finden und ggf. entscheiden, was im konkreten Fall wichtiger ist.
Ich bin auch darauf hingewiesen worden, dass die Verwendung von verketteten Listen durchaus nicht in allen Fällen die beste Methode ist, irgendein Problem zu lösen. Gerade bei "Queues" u.ä sind Ringpuffer wohl eher µC-Style.

Warteschlangen (queues)

Beim Aufbau von „Warteschlangen“ wird z.B. beim „enqueuen“ immer „hinten“ ein Element eingefügt, beim „dequeuen“ immer vorn das erste entfernt (wie beim Aldi an der Kassa).

"sliding window"

Wenn fortlaufend Messages kommen und ich aber nur ein "Beobachtungs-fenster" von ein paar Messages habe, dann bewegt sich dieses Fenster bildlich über die Messages (oder andere Ereignisse) hinweg. Das ist dann eben ein "gleitendes Fenster" oder eben "Sliding window". Ist wohl am ehesten bekannt bei Kommunikations-Protokollen. Damit nicht jede Message einzeln bestätigt werden muss, werden Messages zwar fortlaufend gesendet, aber von der letzten bestätigten Paket-Nummer an gespeichert. Eine ev. angeforderte Sendewiederholung kann sich nur auf eine Stelle in diesem "Message-Fenster" beziehen und dann ist diese Message eben noch greifbar. Kommt aber eine Bestätigung für eine Message-Nummer innerhalb des Fensters, werden diese Message und alle davor endgültig verworfen, das Fenster wird wieder kleiner.

„Gleitendes Mittel“

Ganz gleich funktioniert es, wenn man z.B. immer nur die, sagen wir, 10 letzten Ergebnisse eines Sensors speichern und einen aktuellen Durchschnittswert errechnen will. Dann wird das neueste Ergebnis hinten eingefügt und der Messwert auf eine Gesamtsumme addiert. Wenn es nun mehr als zehn Ereignisse sind, entfernt man das bisher erste Element und zieht diesen Wert von der Summe ab. Der aktuelle Durchschnittswert ist dann immer Summe / Elementanzahl.

Daten-Bäume

Da ich ja in jedem List-Element auch wieder einen List-Header hineinschreiben und dort wiederum andere Elemente einfügen kann, habe ich so die Möglichkeit, einen „Datenbaum“ zu erstellen bzw. zu bearbeiten. Die Directory-struktur bei einer Hard-Disk ist zum Beispiel so ein Baum. Auch ein „Menü“-Baum kann so dargestellt werden.

Weniger detailliert, aber besser für den Überblick kann das dann so aussehen

Kombination Tabelle/Liste

Man kann natürlich auch die Elemente einer Tabelle verketten. Damit entsteht neben der eigentlichen Tabellen-Index-Reihenfolge eine weitere „logische“ Reihenfolge. Wenn ich also eine Tabelle umsortieren will, lasse ich die Elemente, wo sie sind, und ändere nur die Verkettung. Als ListHeader brauch ich dann den Index der ersten und ev. letzen Elements. Da ist auch gleich so ein Fall, wo ein „Verweis“ keine wirkliche Adresse ist, sondern nur ein Index für ein anderes Element.

Autoren

• PicNick

Siehe auch

• Sensoren