Version vom 27. August 2011, 17:19 Uhr

Listen

Liste / Tabelle

Man muss verkettete Listen von Tabellen unterscheiden. Bei einer Tabelle (Array) sind gleichgrosse Elemente hintereinander in der Memory angeordnet und können durch einen „Index“ (= Element-Nummer) gezielt adressiert werden. Bei Bascom hat übrigens das erste Tabellenelement den Index „1“, bei GCC und anderen gilt hier der Index „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ässigerweise 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 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

• Init Head (HEAD)Erzeugen einer leeren Liste. Gegeben ist List-Head.

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

• • Insert Head (HEAD, NEW) 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 auch als letztes eingetragen werden (verwirrt?).
  • Insert Tail (HEAD, NEW) 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 auch als erstes eingetragen werden (noch mehr verwirrt?).
  • Insert Behind (POSITION, NEW) Einfügen als Nachfolger, gegeben sind Vorgänger und das neue Element. Da es offenbar einen Vorgänger gibt, ist die Liste nicht leer. Das neue Element kann aber auch das neue letzte Element sein, das man in den Header dann als solches eintragen muss.
• FIRST = Read First(HEAD) Lesen des ersten Elements, angegeben wird List-Head.
• NEXT = Read Next(POSITION) Lesen des nächsten Elements, angegeben wird das aktuelle Element.
• Entfernen
  • Remove First(HEAD) Entfernen des ersten Elements, Angabe List-Head. Auch hier ist zu prüfen, ob dieses Element das letzte ist in der Liste ist. Man muss dan den List-Header entsprechend korrigieren.
  • Remove(POSITION, PREV) Entfernen eines beliebigen Elements. Das geht nur, wenn der Vorgänger gegeben ist. Gibt es diesen, kann das entfernte Element nicht das erste sein. Es kann aber das letzte sein, dann muss man den Vorgänger entsprechend im Header eintragen.

Doppelt verkettete Listen

Bei eine „doppelt“ verketteten Liste enthält jedes Element 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

• Init Head (HEAD)Erzeugen einer leeren Liste. Gegeben ist List-Head.
  

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

Liste mit einem Element

• Einfügen

Durch die Gleichsetzung von List- und Element-Header und den "Eigenverweis" im Header einer leeren Liste, gibt es nur zwei Einfügefunktionen:

• • vor einem anderen Element. Gegeben das neue Element und ein anderes Element (oder der List-Header)
    

NEW.BCK = POSITION.BCK
POSITION.BCK = makeVerweis(NEW)
NEW.FWD = makeVerweis(POSITION)
PREV = makeAdresse(NEW.BCK)
PREV.FWD = makeVerweis(NEW)
Bei Angabe der List-Headers als Einfügeposition entspricht das dem "Einfügen als letztes Element"

• • nach einem anderen Element. Gegeben das neue Element und ein anderes Element (oder der List-Header)
    

NEW.FWD = POSITION.FWD
POSITION.FWD = makeVerweis(NEW)
NEW.BCK = makeVerweis(POSITION)
NEXT = makeAdresse(NEW.FWD)
NEXT.BCK = makeVerweis(NEW)
Bei Angabe der List-Headers als Einfügeposition entspricht das dem "Einfügen als erstes Element"

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

• • Vorher

• • Nachher

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

PREV = POSITION.BCK
NEXT = 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.

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).

„Gleitende Statistik“

(gibt's da nicht einen fach-chinesischen Ausdruck dafür ?) 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.

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