Inhaltsverzeichnis

1 Listen

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

Bei verketteten Listen kann sich jedes Element irgendwo im Speicher befinden, daher gibt es üblicherweise einen „Header“, der zumindest auf das das Anfangselement verweist. Listen-Elemente können auch unterschiedlich lang sein, dann muss oder sollte jedes Element auch eine Längenangabe enthalten (Bei Strings reicht natürlich ev. auch der „NUL“ Terminator). Das Auffinden eines bestimmten Elements kann hier aber nur erfolgen, indem man der Verkettung vom ersten Element weg folgt, bis man das gesuchte gefunden hat. Wenn die Element 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.

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

Eine leere Liste

Liste mit zwei Elementen

Einfügen von Elementen

Grundsätzliche MEthoden

Init Head (HEAD)

HEAD.FIRST = makeVerweis(NULL) HEAD.LAST = makeVerweis(NULL)

Insert Head (HEAD, NEW)

FIRST = makeAddresse(HEAD.FIRST) ? FIRST = NULL HEAD.LAST = makeVerweis(NEW) HEAD.FIRST = makeVerweis(NEW) NEW.FWD = makeVerweis(FIRST)

Insert Tail (HEAD, NEW)

LAST = makeAddresse(HEAD.LAST) ? LAST = NULL HEAD.FIRST = makeVerweis(NEW) else LAST.FWD = makeVerweis(NEW) HEAD.LAST = makeVerweis(NEW) optional NEW.FWD = „NULL“

Insert Behind (POSITION, NEW)

NEW.FWD = POSITION.FWD POSITION.FWD = makeVerweis(NEW) ? NEW.FWD = NULL HEAD.LAST = makeVerweis(NEW) optional

Read First(HEAD)

NEXT = makeAddresse(HEAD.FIRST) ? NEXT = NULL  end-of-list

Read Next(POSITION)

NEXT = makeAddresse(POSITION.FWD) ? NEXT = NULL  end-of-list

Remove First(HEAD)

FIRST = makeAddresse(HEAD.FIRST) ? FIRST = NULL HEAD.LAST = NULL optional  end-of-list else HEAD.FIRST = FIRST.FWD

Remove(POSITION, PREV)

Entfernen eines beliebigen Elements aus der Liste geht nur, wenn auch der Vorgänger gegeben ist. PREV.FWD = POSITION.FWD

Doppelt verkettete Listen

Bei eine „doppelt“ verketteten Liste enthält jedes Element zusaätzlich auch einen Verweis auf seinen Vorgänger, dadurch kann dann in der Liste direkt in beiden Richtungen navigiert werden.

NULL-Verweise

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, weil sie kein Wenn und Aber brauchen.