verkette Listen, sinnvolle Anwendungen?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
Dr.Miles
User
Beiträge: 38
Registriert: Montag 15. Dezember 2008, 08:33
Wohnort: Mannheim
Kontaktdaten:

Mittwoch 28. Januar 2009, 22:49

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
www.i2p2.de <--- sehr interressantes Anonymisierungsprojekt.
www.schaeuble-wegtreten.de <--- Petition gegen Schäuble
abgdf

Mittwoch 28. Januar 2009, 22:52

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
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 28. Januar 2009, 23:19

Dr.Miles hat geschrieben: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
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Freitag 30. Januar 2009, 09:27

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
Antworten