FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Unterbereich Grundstudium / Praktische Informatik

P3 : Einfach oder doppelt verkette Liste im Array

P3 : Einfach oder doppelt verkette Liste im Array 2005-03-28 13:43
Anonymer User
Wer kann mir das erklären?
Vielleicht mit Beispiel?

Re: P3 : Einfach oder doppelt verkette Liste im Array 2005-03-28 14:12
georg
Das ist eine Implementation einer Liste mithilfe eines Arrays.
In der sequentiellen Darstellung entsprechen der Array-Index
jedes Elements seinem Listen-Index.

Bei der Darstellung als (doppelt) verkettete Liste werden aber die
Elemente, die in der Liste aufeinanderfolgen, nicht an
aufeinanderfolgenden Positionen im Array gespeichert. Stattdessen
enthält jeder Eintrag im Array sowohl das Datenelement als auch den
Array-Index des in der Liste darauffolgenden Elements.

Bei der doppelt verketteten Liste enthält jeder Eintrag zusätzlich
den Array-Index des in der Liste vorangehenden Elements.

Wo das erste Listenelement im Array liegt, muss noch
außerhalb des Arrays notiert werden.

Man hat es also mit einer normalen verketteten Liste zutun, nur
dass hier die Adressen der Nachfolger (und ggf. Vorgänger)
keine Speicheradressen sondern Array-Indices sind.

Ist jetzt wirklich noch ein Beispiel nötig? Falls ja, sag bescheid.