Verkettete Liste

[nachac]

Servus,

mir fehlt das Verständnis, wie ich eine verkettete Listen in Python darstellen soll. Komischerweise wird darauf in den Tutorials auch nicht eingegangen.

Ein Beispiel:
Ich will immer die benachbarten Elemente ausgeben.

Code: Alles auswählen

liste = [0, 1, 2, 3, 4]

Bei

Code: Alles auswählen

current = liste[2]

soll also 1, 2, 3 ausgegeben werden.
Bei

Code: Alles auswählen

current = liste[4]

3, 4, 0.

Danke für eure Hilfe!

[EyDu]

Hallo.

Warum sollte man auf so ein triviales und allgemeines Thema in einem Python-Tutorial eingehen? Du suchst den Modulo-Operator.

[BlackJack]

@nachac: Du erstellst Dir entweder einen eigenen Datentyp dafür, der eben eine klassische doppelt verkettete Liste implementiert, oder eine Funktion die mit einer gegebenen `list` und einem Index die entsprechenden Elemente liefert. Dabei könnte sich die Modulo-Rechnung als nützlich erweisen.

Warum sollten Tutorials darauf speziell eingehen?

[nachac]

Versteh nicht ganz, was MOD damit zu tun hat

Warum sollte man auf so ein triviales und allgemeines Thema in einem Python-Tutorial eingehen? / Warum sollten Tutorials darauf speziell eingehen?

Weil ich dachte, diesen Datentyp gibt es in Python.

[numerix]

Dein Eingangsbeispiel ist insofern unglücklich gewählt, weil die Werte in der Liste ihren Indizes entsprechen und so nicht ganz klar ist, was genau du erreichen willst.

Ansonsten bringt der Datentyp list schon alles mit, was du brauchst. Du kannst von jedem Element aus den Vorgänger und den Nachfolger bestimmen, kannst Elemente einfügen und entfernen. Was willst du mehr?

Edit: mod brauchst du (nicht zwingend, aber sinnvollerweise), wenn du an eine zyklische Liste denkst und das 1. Element der Nachfolger des letzten sein soll.

[problembär]

Code: Alles auswählen

liste = [0, 1, 2, 3, 4]

ist schon eine Liste. Obwohl ich das nicht genau nachgesehen habe, glaube ich, daß sie auch als verkettete Liste im Interpreter (in der Regel) in C implementiert ist. Jedenfalls verhält sie sich so (wie numerix schon sagte).
Insofern macht es keinen Sinn, eine verkettete Liste in Python implementieren zu wollen, weil es sie als Datentyp schon gibt.

[EyDu]

Obwohl ich das nicht genau nachgesehen habe, glaube ich, daß sie auch als verkettete Liste im Interpreter (in der Regel) in C implementiert ist. Jedenfalls verhält sie sich so (wie numerix schon sagte).

Da glaubst du falsch. In C Python ist es ein Array.

[nachac]

Dein Eingangsbeispiel ist insofern unglücklich gewählt, weil die Werte in der Liste ihren Indizes entsprechen und so nicht ganz klar ist, was genau du erreichen willst.

Ja hast du recht.

Code: Alles auswählen

Tiere = ['hase', 'hund', 'katze', 'maus', 'meerschweinchen']

aktuelles_tier = Tiere[1]

Ausgabe:
hase
hund <-- aktuell
katze

Code: Alles auswählen

aktuelles_tier = Tiere[5]

Ausgabe:
maus
meerschweinchen <-- aktuell
hase

[numerix]

Code: Alles auswählen

>>> tiere = ['Hase', 'Hund', 'Katze', 'Maus', 'Meerschweinchen']
>>> for i,tier in enumerate(tiere):
...     print tiere[i-1],tier,tiere[(i+1)%len(tiere)]
... 
Meerschweinchen Hase Hund
Hase Hund Katze
Hund Katze Maus
Katze Maus Meerschweinchen
Maus Meerschweinchen Hase

[problembär]

Obwohl ich das nicht genau nachgesehen habe, glaube ich, daß sie auch als verkettete Liste im Interpreter (in der Regel) in C implementiert ist. Jedenfalls verhält sie sich so (wie numerix schon sagte).

Da glaubst du falsch. In C Python ist es ein Array.

Das sollte mich wundern:
http://de.wikipedia.org/wiki/Liste_(Dat ... strukturen

Der Vorteil einer Liste gegenüber einem Array ist, dass das Einfügen und Löschen von Elementen an jedem Punkt in der Liste in konstanter Zeit möglich ist.

Auch hier dieser nähere Vergleich.
Aber bitte, man kann Listen in C auch in (ggf. mehrdimensionalen) Arrays organisieren. Obwohl ich mir das immer noch schwierig umzusetzen vorstelle, denn Python-Listen können im Gegensatz zu C-Arrays ja alle möglichen Datentypen enthalten. Da ist dann jede Menge "Zeiger-Arbeit" in den Arrays nötig, noch mehr als normalerweise ohnehin schon.

Jedenfalls denke ich immer noch, daß in Python der eingebaute Datentyp "Liste" reicht, so daß man keine verketteten Listen neu zu implementieren braucht.

Gruß

[BlackJack]

@problembär: Dann wundere Dich ruhig, denn Listen sind in CPython als dynamische Arrays implementiert. Und wahrscheinlich auch in anderen Python-Implementierungen denn der Indexzugriff muss schnell passieren, und das ist bei Implementierungen als verkettete Liste nicht der Fall. Bei Jython wird wahrscheinlich der Typ `ArrayList` aus der Java-Standardbibliothek zum Einsatz kommen.

Bei Wikipedia ist halt auch nicht alles Gold und in der Diskussionsseite findet man dann auch den Hinweis, dass der Artikel eine konkrete Implementierung von Listen beschreibt und nicht den abstrakten Datentyp (ADT) Liste. Man kann Listen nämlich auf verschiedene Arten implementieren.

Laufzeitverhalten in Listen bei CPython ist jedenfalls O(1) beim Indexzugriff, O(n) beim Einfügen/Entfernen beliebiger Elemente, und amortisiert O(1) beim Anfügen von Elementen am Ende.

Es wäre schwierig Listen in Python *nicht* mit Zeigern zu implementieren. Wie würdest Du Dir *das* denn bitte vorstellen? Es wird in Python nie ein Objekt kopiert ohne dass man das explizit haben will und man kann das selbe Objekt in mehrere Listen stecken. Wie soll dass gehen wenn da keine Zeiger verwendet würden -- wie überall anders in der Implementierung auch!?

[sma]

mir fehlt das Verständnis, wie ich eine verkettete Listen in Python darstellen soll.

Man kann es z.B. so machen wie Lisp es vor 60 Jahren gemacht hat.

Code: Alles auswählen

# implementation
def cons(first, rest): return (first, rest)
def first(lst): return lst[0]
def rest(lst): return lst[1]
def isempty(lst): return lst is None

# example usage
example = cons(1, cons(2, cons(3, None)))
print(example)

def length(lst):
    if isempty(lst):
        return 0
    return 1 + length(rest(lst))
print(length(example))

def append(lst1, lst2):
    if isempty(lst1):
        return lst2
    return cons(first(lst1), append(rest(lst1), lst2))
print(append(example, example))

def reverse(lst):
    if isempty(lst):
        return None
    return append(reverse(rest(lst)), cons(first(lst), None))
print(reverse(example))

Stefan

[Darii]

Aber bitte, man kann Listen in C auch in (ggf. mehrdimensionalen) Arrays organisieren. Obwohl ich mir das immer noch schwierig umzusetzen vorstelle, denn Python-Listen können im Gegensatz zu C-Arrays ja alle möglichen Datentypen enthalten. Da ist dann jede Menge "Zeiger-Arbeit" in den Arrays nötig, noch mehr als normalerweise ohnehin schon.

Das ist in der Implementierung von CPython kein Problem, da dort alle Python-Objekte vom Typ PyObject sind. Davon abgesehen arbeitet man da eh nur mit Zeigern. Die wären sowieso alle gleichartig, selbst wenn die Python-Objekte verschiedene C-Typen hätten. Außerdem hätte man das Problem das du da siehst auch mit verketteten Listen.

[nachac]

Code: Alles auswählen

>>> tiere = ['Hase', 'Hund', 'Katze', 'Maus', 'Meerschweinchen']
>>> for i,tier in enumerate(tiere):
...     print tiere[i-1],tier,tiere[(i+1)%len(tiere)]

Ah, danke, jetzt versteh ich auch das mit dem Modulo.

Ansonsten bringt der Datentyp list schon alles mit, was du brauchst. Du kannst von jedem Element aus den Vorgänger und den Nachfolger bestimmen, kannst Elemente einfügen und entfernen. Was willst du mehr?

Ja, hast du recht.

[HerrHagen]

Man sollte allerdings noch erwähnen das bei der Allokation des Arrays immer ein wenig mehr als benötigt belegt wird. Dadurch ist gewährleistet das bei Anfügen von Elementen an das Listenende in den meisten fällen gar kein zusätzlicher Speicherplatz reserviert werden muss.
Wenn ich keinen Denkfehler hab sollte man sich das folgendermaßen auch visualisieren können:

Code: Alles auswählen

import sys
import pylab

l = []
p = []
for i in range(1000):
    p.append(sys.getsizeof(l))
    l.append(None)

pylab.plot(p)
pylab.show()

MFG HerrHagen