mehrfach verk. Listen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:15 Sa 14.01.2017 | | Autor: | Bindl |
| Aufgabe | | Was ist eine mehrfach verkettete Liste und geben Sie ein Beispiel für eine solche? |
Hi,
hier gehts mir rein um eine "Erklärungshilfe".
Eine einfach verkettete Liste besteht aus einem Tupel mit dem eigentlichen Element und dem Verweis auf den nächsten Tupel. Nur das letzte Tupel hat natürlich keinen Verweis mehr.
Die doppelt verkettete Liste besteht aus einem Tupel mit dem Element und 2 Verweisen. Einmal auf den vorherigen Tupel und einmal auf den folgenden Tupel. Nur der erste und der letzte Tupel haben natürlich nur einen Verweis.
Was ist denn nun eine mehrfach verkettete Liste?
Ist die Skip Liste eine mehrfach verkettete Liste?
Hat eine mehrfach verkettete Liste mehr als 2 Verweise und kann somit auf den vorherigen, folgenden und auch übernächsten verweisen?
Ich hoffe mich kann jemand aufklären.
|
|
| |
|
Hallo!
Grundsätzlich bedeutet "mehrfach" ja "mehr als einmal", demnach könnte man schon eine zweifach verkettete Liste auch als mehrfach verkettete Liste bezeichnen. Ob man das in der Realität auch so sieht, weiß ich allerdings nicht.
Aber ja, eine mehrfach verkettete Liste kann mehr als zwei Verweise enthalten.
Es ist klar, welche Vorteile zweifach verkettete Listen gegenüber einfach verketteten haben, darüber hinaus muß man überlegen, welche weitere Verkettung für den konkreten Fall überhaupt Sinn macht, und auch tatsächlich was bringt.
Ich würde behaupten, deine Idee, auch auf das übernächste Element zu verweisen, ist ineffizient. Denn um an das übernächste Element zu gelangen, muß man ja nur einen einzigen Zwischenschritt machen, nämlich das nächste Element lesen. Das kostet kaum Zeit, die Listenelemente wären aber gleich 8 Byte größer (bei 64bit-Systemen).
Was hältst du von einer Liste, die nach zwei Kriterien sortiert werden soll? Man kann eine zweifach verkettete Liste ja nur nach einem Kriterium sortieren, aber man könnte zwei weitere Verweise nutzen, um die gleichen Elemente ein zweites mal, nach einem anderen Kriterium sortiert zweifach zu verketten. Wenn die Liste andauernd nach dem einen oder anderen Kriterium sortiert gelesen wird, ist das ein riesen Geschwindigkeitsvorteil.
Eine Skiplist ist sicher auch eine mehrfach verkettete Liste, allerdings auch schon eine recht fortschrittliche und etwas kompliziertere, da jedes Element unterschiedlich viele Verweise haben kann. Das Lesen geht auch bei langen Listen extrem schnell, das Einfügen von Elementen ist jedoch etwas aufwändiger.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:07 Mo 16.01.2017 | | Autor: | Bindl |
Vielen Dank!!!
|
|
|
|
