verkette Listen, sinnvolle Anwendungen?

[Dr.Miles]

Hallo, mache gerade Kapitel 17 in "Wie ein Informatiker denken lernen". Es geht um verkette Listen. Im Tutorial steht, man kann unendlich lange zahlen damit darstellen, indem man halt auf den letzten Knoten verweist.
(

Wie dem auch sei, sie sind gelegentlich nützlich. So können wir z.B. eine Zahl als Liste von Ziffern darstellen und eine unendliche Liste verwenden, um eine sich wiederholende Zahlenfolge abzubilden.

)
Aber wofür kann man die denn noch gebrauchen?
Im Forum habe ich danach gesucht, aber nichts wirklich dazu gefunden...
Werden sie so selten / garnicht verwendet?
Gruß
Dr.Miles

[abgdf]

Doch, sie werden ständig in Python verwendet: Die Datentypen "Liste", "Tuple", vielleicht auch "Dictionary", sind Implementationen verketteter Listen.

So können wir z.B. eine Zahl als Liste von Ziffern darstellen

Code: Alles auswählen

a = 12345

b = str(a)

c = []

for i in b:
    c.append(int(i))

for i in c:
    print i

Das werkelt aber im Python-Interpreter vor sich hin. Python-Programmierer arbeiten damit, müssen sich mit der internen Logik aber nicht beschäftigen.

Gruß

[Leonidas]

Aber wofür kann man die denn noch gebrauchen?

Das hätte man zum Beispiel mit einer doppelt verketteten Liste implementieren können (wäre aber komplizierter geworden - nicht jede Sprache ist so elegant wie Python).

Generell: Strukturen in denen man Listen nicht nur in eine Richtung durchgehen will, sondern in beide.

abgdf: ich denke nicht, dass das Double-Linked-Lists sind. Gerade Tupel sind allozieierte Arrays, Listen sind eigentlich Arrays die überalloziiert sind. Wie Dictionaries implementiert sind, weiß ich nicht genau, kann man aber rausfinden wenn man wollte, ``dictobject.c`` ist ja veröffentlicht.

[sma]

Zahlen, die bei Python sowieso schon beliebig lang sein können, sind IMHO ein schlechtes Beispiel. Verkettete Listen sind eine mögliche Implementierung eines Listen-ADTs. Eine Vielzahl von Algorithmen lassen sich darauf definieren.

Zunächst der ADT:

Code: Alles auswählen

head L -> E - liefert das erste Element der Liste
tail L -> L - liefert die Restliste ohne das erste Element
empty L -> bool - true, falls Liste leer, sonst false
cons E L -> L - Konstruiert eine Liste, indem E vorne angefügt wird

Jetzt die Implementierung mittels verketteter Listen, die Tupel benutzt, um das erste Element und die Restliste zu speichern. `None` steht für die leere Liste.

Code: Alles auswählen

def head(l): return l[0]
def tail(l): return l[1]
def cons(e, l): return e, l
def empty(l): return l is None

Eine derartige Liste kann man z.B. benutzen, um den Stack-ADT zu implementieren. Allgemein sind einfach verkettete Listen ein speichereffizientes Mittel, LIFO-Strukturen zu implementieren, da man sehr effizient (Aufwand O(1) vorne Anfügen und wieder entfernen kann. Mit einem Aufwand von O(n) kann man Element an anderer Stelle einfügen oder löschen. In einer doppelt verketteten Liste kann man zumindest mit O(1) ein beliebiges Element löschen. Meist merkt man sich dort auch noch das Ende der Liste, sodass man dort auch mit O(1) am Ende anfügen kann. In einer als Array implementierten Liste (so wie Python das AFAIK macht) ist zwar der Zugriff auf jedes Element O(1), doch das Einfügen oder Entfernen von Elementen prinzipiell immer O(n). Für den häufigen Fall des hinten Anfügen kann man's optimieren, ebenso könnte man den Fall des in der Mitte Einfügens (braucht man z.B. für Texteditoren) mittels einer speziellen Variante optimieren. Das geht aber beides zu Lasten des Speicherbedarfs.

Stefan