Version vom 23. August 2011, 13:55 Uhr

Listen

Verkettete Listen

Man muss verkettete Listen von Tabellen unterscheiden. Bei einer Tabelle 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, jedes Element enthält einen Verweis auf das folgende Element, meist in Form der Adresse. Die Element 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). Die Auffinden eine bestimmten Elements kann hier aber nur erfolgen, indem man der Verkettung vom ersten Element weg folgt, bis man das gesuchte gefunden hat. Bei eine „doppelt“ verketteten Liste enthält jedes Element auch einen Verweis auf seinen Vorgänger, dadurch kann dann in der Liste in beiden Richtungen navigiert werden.

Klingt irgendwie aufwendig, wofür kann man das brauchen ?

Anwendungsbeispiele

Nun, wenn zum Beispiel die Element umsortiert werden sollen, dann reicht es, die Verkettungs-Zeiger zu verändern, während man bei einer Tabelle die gesamten Daten verschieben muss. Ebenso, wenn man einzelne Element entfernen oder einfügen will. Beim Aufbau von „Warteschlangen“ (Queues) wird z.B. beim „enqueuen“ immer „hinten“ ein Element eingefügt, beim „dequeuen“ immer vorn das erste (wie beim Aldi an der Kassa).

Aufbau

List-Header

Ein solcher Header ist sozusagen die Kontroll-Struktur für eine Liste. Auf das notwendigste reduziert, hat er drei Attribute:

• Seine eigene Adresse
• Einen Verweis auf das erste Element
• einen Verweis auf das letzte.

Element-Header

Sieht im Grunde genauso aus

• Seine eigene Adresse
• Einen Verweis auf das nächste Element
• einen Verweis auf das vorherige.

Verweise/Adressen

Als Verweis kann direkt die jeweilige Speicher-Adresse dienen. Bei einem Computer /PC mit 32-Bit Adressen (4 Byte) und keinen (kaum) Speicherproblemen ist das sicher eine praktikable Methode. Aber dann bestünde so ein Header aus 2x4 , also 8 Byte. Und für einen µC knabbert das doch ganzschön an den üblicherweise knappen Speicherressourcen. Verwendet man dort 16-Bit Adressen, reicht das, um eine 64k memory abzudecken. Da gehen zwar auch noch 4 Byte für jeden Header drauf, aber von nix kommt eben nix. Es gibt noch mehr Möglichkeiten, solche Verweise kürzer zu bekommen, eine davon ist die, auf die Rückwärtsverkettung zu verzichten, in manchen /vielen Fällen ist sie ja nicht notwendig, dann halbiert sich der Speicherbedarf schlagartig. Wie man das auch macht, in der Folge bleibe ich bei meinen doppelt verketteten Listen, und bleibe beim Begriff „Verweis“ und lasse offen, was das genau ist. Für das weitere Verständnis ist es auch unerheblich.

Verweise/Sonderfälle

Für das erste bzw. letzte Element der Liste ist die Frage, wie dann die Verweise auf den Nachfolger/Vorgänger aussehen sollen. Die gleiche Frage beim List-Header, wenn die Liste leer ist. Man kann natürlich einfach „NULL“ reinschreiben bzw. darin stehen lassen. Für die Lese-Funktionen „nächstes-“/“vorheriges Element“ ist das praktisch, „NULL“ heisst, es ist kein Element mehr da.

Leere Liste

Liste mit einem Element

Liste mit mehreren Elementen

Element einfügen

Vorher

Nachher

List-Tree

Autoren

• PicNick

Siehe auch

• Sensoren