Suchen in doppelt verketteten Listen [Archiv]

PatkIllA

2010-04-20, 16:19:12

das sind dann aber keine (linearen) listen im eigentlichen sinne sondern dynamische arrays oder ähnliches.Die Standardliste in .NET funktioniert z.B. so.
Wenig Overhead in vielen Fällen, dafür ist Einfügen (besonders am Anfang) halt teuer und wenn das interne Array nicht reicht wird intern ein neues Array erstellt und umkopiert.
Oft heißen die Implementierungen sogar ArrayList.
In meinem Verständnis ist eine Liste auch nicht unbedingt verkettet.

Wenn ihr eine Einkaufsliste schreibt dann schreibt ihr die Einträge also nicht einfach untereinander sondern ordnet die wild auf dem Zettel an und sorgt dann durch Pfeile für eine Reihenfolge?

Tesseract

2010-04-20, 16:31:30

Wenn ihr eine Einkaufsliste schreibt dann schreibt ihr die Einträge also nicht einfach untereinander sondern ordnet die wild auf dem Zettel an und sorgt dann durch Pfeile für eine Reihenfolge?

der vergleich hinkt gewaltig. eine liste in der informatik hat nicht viel mit einer einkaufsliste zutun. eine einkaufsliste auf einem zettel wäre ein statisches array.

und ja, eine liste muss verkettet sein, sonst findest du die elemente nicht. du kannst sie nur über pointer oder ordnung finden. über pointer ist eine liste (oder baum bzw. graph) und über ordnung ist es ein array.
hashing mal ausgenommen.

PatkIllA

2010-04-20, 16:36:14

Vielleicht bin ich da zu stark von .NET und Java geprägt, aber für mich ist der Unterschied von Listen zu Mengen oder Kollektionen einfach nur das die Elemente eine Reihenfolge haben.
Im Studium war eine Liste auch nicht automatisch verkettet.
Und natürlich finde ich auch in einer Liste die intern durch ein Array repräsentiert wird die Elemente wieder.

_Gast

2010-04-20, 16:37:45

Welche sollen das sein? Wenn es ein Array ist, dann ist es keine (doppelt) verkettete Liste und hat dementsprechend auch ein ganz anderes Laufzeitverhalten.Man kann aber bei verketteten Listen parallel ein Array mitführen, das bestimmte zu durchsuchende Elemente enthält. Eine verkette Liste aus Adressobjekten könnte beispielsweise ein Array mitführen, das den Nachnamen enthält.

Datenbanken mit Indexen zu Tabellen machen im Prinzip nichts anderes.

Tesseract

2010-04-20, 16:38:59

Und natürlich finde ich auch in einer Liste die intern durch ein Array repräsentiert wird die Elemente wieder.

natürlich kannst du einen wrapper schreiben, der aus einer liste intern ein array macht. das ändert aber nix daran wie listen und arrays funktionieren. ;)

PatkIllA

2010-04-20, 16:42:14

natürlich kannst du einen wrapper schreiben, der aus einer liste intern ein array macht. das ändert aber nix daran wie liste und arrays funktionieren, ;)
Nach welcher Definition ist denn definiert wie eine Liste zu funktionieren hat? Ich bin da in keiner Vorlesung drüber gestolpert. Wenn dann wurde das immer mit einem Zusatz (z.b. einfach doppelt verkettet) verwendet.

Tesseract

2010-04-20, 16:47:24

Nach welcher Definition ist denn definiert wie eine Liste zu funktionieren hat? Ich bin da in keiner Vorlesung drüber gestolpert. Wenn dann wurde das immer mit einem Zusatz (z.b. einfach doppelt verkettet) verwendet.
eine lineare liste ist ein linearer, kreisfreier graph ohne verzweigungen. im falle einer einfach-verketteten ein gerichteter und im fall einer zweifach-verketteten ein ungerichteter.
eine liste im allgemeinen ist einfach ein graph, wobei man dann eigentlich nichtmehr den begriff liste verwendet.

ein array hingegen ist eine arithmetische projektion des indexes auf eine position im speicher.

PatkIllA

2010-04-20, 16:52:25

eine liste ist ein linearer, kreisfreier graph ohne verzweigungen. im falle einer einfach-verketteten ein gerichteter und im fall einer zweifach-verketteten ein ungerichteter.
Und da kannst du jetzt auch ein paar anerkannte Werke aus der Standardliteratur der Informatik nennen, die das genauso definiert?

Tesseract

2010-04-20, 16:56:31

Und da kannst du jetzt auch ein paar anerkannte Werke aus der Standardliteratur der Informatik nennen, die das genauso definiert?

das muss man nicht definieren weil sich das aus dem zusammenhang ergibt. die eigenschaften einer linearen liste findest du in fast jeder standardliteratur der informatik und die darin beschriebenen eigenschaften sind nunmal die eines linearen graphen.
das selbe gilt z.B. für skiplisten, die dann allerdings nichtmehr linear sind.

listen sind abstrakte datentypen und können deswegen überhaupt nichts mit array-arithmetik zutun haben.

DocEW

2010-04-20, 17:01:18

Da scheint es tatsächlich einen Unterschied zu geben zwischen einer Liste, wie sie üblicherweise in der Informatik definiert wird (http://de.wikipedia.org/wiki/Liste_%28Datenstruktur%29), und der Schnittstelle "List", wie sie einem in C# oder Java begegnet. War mir auch nicht bewusst, ich hätte auch lediglich die Ordnung der Elemente als Merkmal gesehen und den Rest unter "Implementierung" verbucht.

Edit: Wobei ich gerade sehe, dass z.B. in "Theoretische Informatik" von Blum folgendes steht:
Listen dienen zur Darstellung von Folgen, die an beliebiger Stelle verändert werden dürfen. Zur Realisierung einer Liste nimmt man üblicherweise kein einzelnes Feld, da bei der Modifikation der Liste eventuell das gesamte Feld umgespeichert werden müßte. Günstiger ist die Verwendung von verketteten Listen.
Dort ist eine Liste also nicht per Definition eine verkettete Liste.

PatkIllA

2010-04-20, 17:02:09

Aus den Eigenschaften einer Datenstrukturen folgt nichts zu der Umsetzung. Eine Liste ist deutlich abstrakter.

Pinoccio

2010-04-20, 17:02:54

Und da kannst du jetzt auch ein paar anerkannte Werke aus der Standardliteratur der Informatik nennen, die das genauso definiert?Knuth macht das so. Reicht das? :wink:
Da scheint es tatsächlich einen Unterschied zu geben zwischen einer Liste, wie sie üblicherweise in der Informatik definiert wird (http://de.wikipedia.org/wiki/Liste_%28Datenstruktur%29), und der Schnittstelle "List", wie sie einem in C# oder Java begegnet. War mir auch nicht bewusst, ich hätte auch lediglich die Ordnung der Elemente als Merkmal gesehen und den Rest unter "Implementierung" verbucht.Die Ordnung resultiert aus den von Tesseract beschrieben Eigenschaften.

mfg

PatkIllA

2010-04-20, 17:03:54

Da scheint es tatsächlich einen Unterschied zu geben zwischen einer Liste, wie sie üblicherweise in der Informatik definiert wird (http://de.wikipedia.org/wiki/Liste_%28Datenstruktur%29), und der Schnittstelle "List", wie sie einem in C# oder Java begegnet. War mir auch nicht bewusst, ich hätte auch lediglich die Ordnung der Elemente als Merkmal gesehen und den Rest unter "Implementierung" verbucht.
Direkt darunter sofort von "verketter Liste" gesprochen und in der englischen Version ist es wieder ganz anders.

Knuth macht das so. Reicht das? :wink:
Genauer Wortlaut?

Die Ordnung resultiert aus den von Tesseract beschrieben Eigenschaften.Es ist aber nur die Ordnung gefordert. Einen Graphen zu nehmen, sagen, dass er die Eigenschaften einer linearen Liste erfüllt und dann daraus zu folgern, das Listen Graphen sind ist ein ziemlicher Lapsus in einer Beweisführung.

Pinoccio

2010-04-20, 17:04:49

Direkt darunter sofort von "verketter Liste" gesprochen und in der englischen Version ist es wieder ganz anders.Wikipedia ist - leider - gerade bei solchen Artikeln keine brauchbare Quelle.

mfg

PatkIllA

2010-04-20, 17:08:22

Wikipedia ist - leider - gerade bei solchen Artikeln keine brauchbare Quelle.Und genau deswegen habe ich es auch nicht zitiert. Ich hatte allerdings auf einen Link gehofft.

Tesseract

2010-04-20, 17:09:42

Direkt darunter sofort von "verketter Liste" gesprochen und in der englischen Version ist es wieder ganz anders.

mir ist nicht ganz klar auf was du eigentlich hinaus willst.

es gibt, wie gesagt, 2 verschiedene möglichkeiten elemente einer datenstruktur zu finden:
1) über pointer
2) über ordnung
das erste sind graphen, das zweite sind arrays.
unter den (sehr allgemeinen) graphen gibt es einige spezialfälle, die eigene namen haben weil sie besonders wichtig sind. der bekannteste ist der baum, andere sehr wichtige sind z.B. verkettete listen.
den begriff einer "unverketteten liste" gibt es ganz einfach nicht.

DocEW

2010-04-20, 17:09:57

Hab' meinen Post nochmal geändert (war unklug, bei eurem Tempo ;) ), vielleicht hilft das weiter. Aber ich schätze, das wird überall leicht unterschiedlich stehen.

Pinoccio

2010-04-20, 17:15:33

Und genau deswegen habe ich es auch nicht zitiert. Ich hatte allerdings auf einen Link gehofft.Versuch's mal da (http://www.s-inf.de/#DaStru). So formal und abstrakt wie Tesseract definiert in den 3 Skripten, die ich kurz überflogen habe, keiner, aber ihre Anforderungen sind praktisch identisch mit dem.
Hab' meinen Post nochmal geändert (war unklug, bei eurem Tempo ;) ), vielleicht hilft das weiter. Aber ich schätze, das wird überall leicht unterschiedlich stehen.Ja, aber das ist ja oft so, daß jeder Prof/Autor/$Whatever erstemal seine eigene Definition macht.

mfg

PatkIllA

2010-04-20, 17:17:04

Ich will einfach nur darauf hinaus, das Listen lediglich eine abstrakte Datenstruktur ist, die Elemente in einer bestimmten Reihenfolge enthält.
Wie die Datenstruktur die Elemente findet ist völlig egal und geht über die Definition hinaus. Ich will ja nicht den Knoten eines Graphens sondern Element mit dem Index x oder das auf Element y folgende Element.
Je nach Anwendungsfall nimmt man halt Implementierung A oder B.

@Pinoccio
ich meinte jetzt link bei wiki. Manchmal sind da ja brauchbare dabei
Bei uns gab es im Studium auch nur die abstrakte Definition und dann ging es direkt weiter mit verketteten Listen als einer Umsetzung von Listen

Pinoccio

2010-04-20, 17:20:36

Ich will einfach nur darauf hinaus, das Listen lediglich eine abstrakte Datenstruktur ist, die Elemente in einer bestimmten Reihenfolge enthält.Nein, das wäre eine Lineare Liste. ><
Wie die Datenstruktur die Elemente findet ist völlig egal und geht über die Definition hinaus. Ich will ja nicht den Knoten eines Graphens sondern Element mit dem Index x oder das auf Element y folgende Element.
Je nach Anwendungsfall nimmt man halt Implementierung A oder B.Ja.

(Kurze Frage: Du kommst eher aus der Praxis, oder?)

mfg

PatkIllA

2010-04-20, 17:25:53

Nein, das wäre eine Lineare Liste. ><in unserem Skript war da nur von Liste die Rede.
(Kurze Frage: Du kommst eher aus der Praxis, oder?)jup habe mich aber tapfer durch den theoretischen Teil der Informatik gekämpft. Ich kann eine Liste auch problemlos als Graphen sehen, nur folgt da für keine zwangsweise Umsetzung als verkette Liste.

Tesseract

2010-04-20, 17:27:56

Je nach Anwendungsfall nimmt man halt Implementierung A oder B.

du musst zwischen interface und implementierung unterscheiden. c# implementiert offenbar das interface der linearen liste als array. deswegen ist die implementierung trotzdem keine lineare liste sondern das ganze einfach ein wrapper.

Monger

2010-04-20, 17:36:24

Irgendwie grad n bissl chaotisch hier... was war nochmal das Thema?

Die Standardliste in .NET funktioniert z.B. so.
Wenig Overhead in vielen Fällen, dafür ist Einfügen (besonders am Anfang) halt teuer und wenn das interne Array nicht reicht wird intern ein neues Array erstellt und umkopiert.
Die List in .NET ist viel mehr als nur eine klassische Liste. Afaik führt die .NET List nebenher auch noch eine HashTable, um die Abfrage auf "Contains" schön fix zu machen.

Rein von der Informatik her hat die "List" also nix mit einer echten Liste zu tun. Ist ja aber im Endeffekt auch irrelevant - denn wie sich ein Objekt einer Klasse zu verhalten hat, ist einzig und allein in dessen Dokumentation festgelegt, und nirgendwo sonst. Wenn da steht: "Diese Liste hat für binäre Suchen ein Laufzeitverhalten von O(1)", dann muss man das glauben. Ob das jetzt mit einem Array oder einer doppelt verlinkten Liste oder ganz anders implementiert wurde, ist im Endeffekt schnurz, und geht den Anwender auch nix an.
Den Unterschied zwischen verschiedenen Datenstrukturen, und deren Vor- und Nachteile interessiert im Endeffekt nur der kleine Kreis von armen Informatiker-Schweinen, die das auch implementieren müssen. Das sind zum Glück nicht allzu viele.

PatkIllA

2010-04-20, 17:36:27

du musst zwischen interface und implementierung unterscheiden. c# implementiert offenbar das interface der linearen liste als array. deswegen ist die implementierung trotzdem keine lineare liste sondern das ganze einfach ein wrapper.

Mir ist der Unterschied bewusst.
also erstmal implemtiert c# da gar nichts. Evtl. wurde es mit c# implementiert, aber da wäre ich mir auch nicht so sicher. Außerdem gibt es im .NET Framework auch noch andere Implementierungen z.B. die LinkedList.

Wieso ist eine Datenstruktur die alle Eigenschaften einer linearen Liste erfüllt keine lineare Liste?

Die List in .NET ist viel mehr als nur eine klassische Liste.Die klassische Liste ist wohl noch ein ganz neuer Datentyp :)
Afaik führt die .NET List nebenher auch noch eine HashTable, um die Abfrage auf "Contains" schön fix zu machen.
Nein macht sie nicht. Da musst du dich eher PHP umsehen.
Rein von der Informatik her hat die "List" also nix mit einer echten Liste zu tun.Sie erfüllt alle Eigenschaften hat damit aber nichts zu tun und ist nicht echt? Bitte was?

Tesseract

2010-04-20, 17:44:18

Wieso ist eine Datenstruktur die alle Eigenschaften einer linearen Liste erfüllt keine lineare Liste?

jetzt gehts ins philosophische. ;)

für die eigenschaften der laufzeit usw. ist natürlich die implementierung entscheidend und die wird sich als array nicht so verhalten wie sie sich als verkettete liste verhalten würde.

rein für die modellierung kannst du sie natürlich als lineare liste verwenden, auch wenn sie intern in arrays organisiert wird. dazu ist die abstraktionsebene ja da.

Monger

2010-04-20, 17:46:55

Nein macht sie nicht.

Ja okay, macht sie tatsächlich nicht (http://msdn.microsoft.com/de-de/library/bhkz42b3(v=VS.100).aspx).
"Diese Methode (Contains) führt eine lineare Suche durch. Daher ist diese Methode ein O(n)-Vorgang, wobei n Count ist."

Sie erfüllt alle Eigenschaften hat damit aber nichts zu tun und ist nicht echt? Bitte was?
Wenn ich mich hier im Forum als Angela Merkel anmelde, das schreibe was auch Angela Merkel schreiben würde, und mich auch sonst verhalte wie Angela Merkel, macht mich das noch lange nicht zu Angela Merkel.
Das heißt lediglich dass meine "API" identisch ist mit der von Angela Merkel.

Fakt ist: du weißt einfach nicht, wie konkret die List implementiert ist (jaja, ich weiß... Quellcode von List ist öffentlich... Ausnahmen, Regeln undso...), und es hat dich auch nicht zu interessieren.
Die einzigen Annahmen die du über das Verhalten der List machen darfst, stehen in deren Dokumentation.

PatkIllA

2010-04-20, 17:47:54

für die eigenschaften der laufzeit usw. ist natürlich die implementierung entscheidend und die wird sich als array nicht so verhalten wie sie sich als verkettete liste verhalten würde.Das Laufzeitverhalten gehört aber überhaupt nichts mit der Definition zu tun. Da habe ich noch keine Definition gefunden die sagt wie das auszusehen hat.
Um ausgehend von Element x das nachfolgende Element zu finden brauchst du übrigens genauso lange, da du ohne den ganzen Knoten auch erstmal Element x finden musst.

Wenn ich mich hier im Forum als Angela Merkel anmelde, das schreibe was auch Angela Merkel schreiben würde, und mich auch sonst verhalte wie Angela Merkel, macht mich das noch lange nicht zu Angela Merkel.
Das heißt lediglich dass meine "API" identisch ist mit der von Angela Merkel.Du erfüllst dann nicht die API Angela Merkel, da die RealName Eigenschaft nicht abfragbar ist und selbst wenn würdest du dann noch lange nicht die API Bundeskanzler zur Verfügung stellen.

Fakt ist: du weißt einfach nicht, wie konkret die List implementiert ist (jaja, ich weiß... Quellcode von List ist öffentlich... Ausnahmen, Regeln undso...), und es hat dich auch nicht zu interessieren.
Die einzigen Annahmen die du über das Verhalten der List machen darfst, stehen in deren Dokumentation.Das will ich doch die ganze Zeit sagen. Egal wie das implemtiert ist kann es trotzdem eine Liste sein.

Tesseract

2010-04-20, 17:53:42

Das Laufzeitverhalten gehört aber überhaupt nichts mit der Definition zu tun.

natürlich hat das was mit der definition zutun. zumindest indirekt.

wenn du z.B. eine zweifach verkettete liste hast ergibt sich aus der definition, dass der zugriff auf das vorhergehende element einen lookup brauchen sollte. denn genau deswegen gibt es implementierungen dafür. wenn du diese doppelt verkettete liste aber über einen wrapper als einfach verkettete implementierst wird sie sich nicht so verhalten.

PatkIllA

2010-04-20, 17:57:34

natürlich hat das was mit der definition zutun. zumindest indirekt.Die (zumindest hab ich noch keine andere gefunden) Definition von Liste fordert nur ein paar bestimmte Operationen.
Du hast es immer noch geschafft zu abstrahieren und bringst Liste immer mit verkettet zusammen.

Tesseract

2010-04-20, 17:59:04

Die (zumindest meine) Definition von Liste fordert nur ein paar bestimmte Operationen.
Du hast es immer noch geschafft zu abstrahieren und bringst Liste immer mit verkettet zusammen.

nochmal: den begriff "liste" als datenstruktur gibt es nicht. wenn irgendwo "liste" steht ist immer ein/zweifache lineare, skipliste oder sonstwas gemeint.
was soll eine "liste" denn sein deiner meinung nach?

PatkIllA

2010-04-20, 18:16:58

nochmal: den begriff "liste" als datenstruktur gibt es nicht. wenn irgendwo "liste" steht ist immer ein/zweifache lineare, skipliste oder sonstwas gemeint.
Und die Entwickler bei MS und Sun haben sich das ausgedacht und die ArrayList geschrieben, um sämtliche theoretischen Informatiker zur Weißglut zu bringen? In unserem alten Skrip gab es auch noch ein Kapitel Liste. Im neuen Skript wird es allerdings Sequence als formaler Begriff genannt. Der Begriff Liste wird da allerdings als Synonym benutzt und da wird auch die Speicherung in einem Feld genannt.

was soll eine "liste" denn sein deiner meinung nach?Eine abstrakte Datenstruktur, die eine Elemente in einer Reihenfolge enthält. Elemente können an beliebiger Position hinzugefügt, entfernt und nur nachgeschaut werden. Der Positionsbegriff gibt in dem Zusammenhang nicht mal her ob das über Vorgänger bzw. Nachfolger geschehen soll oder über einen Index.

Monger

2010-04-20, 19:09:07

Und die Entwickler bei MS und Sun haben sich das ausgedacht und die ArrayList geschrieben, um sämtliche theoretischen Informatiker zur Weißglut zu bringen?
Vielleicht ist das der Grund weshalb die generische Liste (die ja quasi der Nachfolger der ArrayList ist) einfach nur noch "List<T>" heißt.

was soll eine "liste" denn sein deiner meinung nach?
Das hier:

Class Liste{}

Eine Liste ist ein Objekt von einem Typus des Namens "Liste". Also ist eine "List<T>" per Definition eine Liste! :tongue:

pest

2010-04-20, 19:21:54

Welche sollen das sein? Wenn es ein Array ist, dann ist es keine (doppelt) verkettete Liste und hat dementsprechend auch ein ganz anderes Laufzeitverhalten.

vielleicht verstehe ich deinen Beitrag auch falsch,
aber doppelt verkettete Listen kann man (schneller) mit Arrays implemetieren
wenn man die max. Anzahl der Elemete kennt. Mach ich selbst oft, ist sehr praktisch.

Coda

2010-04-20, 20:32:35

Du meinst das Array als Pool für die Kettenglieder zu verwenden? Ja ist mir bekannt, aber das ändert nichts daran, dass man trotzdem keinen schnellen Direktzugriff auf Element n hat.

pest

2010-04-20, 21:24:45

Du meinst das Array als Pool für die Kettenglieder zu
verwenden?

ja ungefähr so
du hast ein array nodes[0..n-1] mit deinen elementen
und zwei int-arrays next[0..n] und prev[0..n]
das n-element ist ein nil-element
und mit next und prev hangelst du dich durch die liste

löschen kannst du dann z.b. mit next[prev[i]] = next[i]

Ja ist mir bekannt, aber das ändert nichts daran, dass man trotzdem keinen schnellen Direktzugriff auf Element n hat.

element n der Liste?, das stimmt

DocEW

2010-04-21, 10:15:25

Es ist glaube ich jedem hier klar, dass sich hinter "Liste" zwei Konzepte verbergen:

1.) Die Datenstruktur "Verkettete Liste", die Elemente in einer Reihenfolge speichert und ein charakteristisches Laufzeitverhalten hat, und
2.) Eine Menge von Operationen eines Datencontainers, der eine Sequenz von Objekten speichert.

Dummerweise redet man über beides kurz als "Liste", und dummerweise kann man das 1.) auch noch benutzen, um das 2.) zu implementieren. :ugly:
Soweit ich das erkennen kann, redet Tesseract über 1.) und PatkIllA über 2.), aber beiden ist grundsätzlich klar, dass es beide Konzepte parallel gibt. =)

_Gast

2010-04-21, 10:35:07

Eine verkette Liste ist eine Datenstruktur, in der die Objekte in linearer Reihenfolge angeordnet sind. Im Gegensatz zu einem Feld, bei dem die lineare Reihenfolge durch den Feldindex bestimmt ist, wird die Reihenfolge bei verketteten Listen durch einen in jedem Objekt zur Verfügung stehenden Zeiger bestimmt.Nach dem "Standardwerk für Algorithmen und Datenstrukturen" (http://www.amazon.de/Algorithmen-Einf%C3%BChrung-Thomas-H-Cormen/dp/3486275151) unterscheidet man zwischen (doppelt) verketteten Listen und Feldern. Was hier also umgangssprachlich als Liste bezeichnet wird, heißt in der Informatik Feld.

eXistence

2010-04-21, 10:36:24

Dass ein Container mit index-basiertem Zugriff "Liste" heißt (bzw. engl. "list"), ist aber auch bei C++ garnicht mal so unüblich. Auch wenns die theoretischen Informatiker dabei wahrscheinlich gruselt ;)

Als Beispiel fällt fällt mir da Spontan Qt (QList*) und der Code von id software (idList**) ein.

* es gibt auch noch QVector, der intern etwas anders aufgebaut ist als die QList (QVector entspricht ungefähr std::vector). Das Interface ist bei beiden Klassen aber das gleiche. Vielleicht ganz interessant: Datenstrukturen von Qt (http://doc.trolltech.com/qq/qq19-containers.html)

** std::vector-ähnliche Implementierung

_Gast

2010-04-21, 10:42:47

Dass ein Container mit index-basiertem Zugriff "Liste" heißt (bzw. engl. "list"), ist aber auch bei C++ garnicht mal so unüblich. Auch wenns die theoretischen Informatiker dabei wahrscheinlich gruselt ;)Du kannst ein Feld natürlich "Liste" nennen, aber auch Banane oder x. Zumindest für die theoretischen Informatiker (die es dabei tatsächlich gruselt) bleibt es, unabhängig vom Namen, ein Feld. ;)

Pinoccio

2010-04-21, 11:42:32

Irgendwie grad n bissl chaotisch hier... was war nochmal das Thema?Frage: kann man eine Binäre Suche in einer Liste durch führen?
Antwort: nein.
jetzt gehts ins philosophische. ;)Soviel zum Thema exakte Wissenschaft. :freak:
Und die Entwickler bei MS und Sun haben sich das ausgedacht und die ArrayList geschrieben, um sämtliche theoretischen Informatiker zur Weißglut zu bringen? In unserem alten Skrip gab es auch noch ein Kapitel Liste. Im neuen Skript wird es allerdings Sequence als formaler Begriff genannt. Der Begriff Liste wird da allerdings als Synonym benutzt und da wird auch die Speicherung in einem Feld genannt.

Eine abstrakte Datenstruktur, die eine Elemente in einer Reihenfolge enthält. Elemente können an beliebiger Position hinzugefügt, entfernt und nur nachgeschaut werden. Der Positionsbegriff gibt in dem Zusammenhang nicht mal her ob das über Vorgänger bzw. Nachfolger geschehen soll oder über einen Index.Die Reihenfolge macht das ganze schon wieder linear! (Im Gegensatz bspw. zu einem Baum) Und eine Sequenz ist auch was mit Reihenfolge.

Das Laufzeitverhalten gehört aber überhaupt nichts mit der Definition zu tun. Da habe ich noch keine Definition gefunden die sagt wie das auszusehen hat.Jein.
Aus den Eigenschaften einer einfach verketten (linearen) Liste folgen gewisse Laufzeitverhalten für die angegeben Operationen.
Wenn ein insertAtEnd in O(1) geht, dann ist es schlicht keine einfach verkettete (lineare) Liste (sondern z. B. eine doppelt verkettete (lienare) Liste).

Und die Entwickler bei MS und Sun haben sich das ausgedacht und die ArrayList geschrieben, um sämtliche theoretischen Informatiker zur Weißglut zu bringen?Zumindest für JAVA ist es so, daß ArrayList dir wahlfreien Zugriff auf Element n bietet, etwas, daß eine pure einfach verkettete (lineare) Liste per Definition nicht bietet.
Weshalb - in der Praxis - keiner pure Listen implementiert, sondern Zusatzfunktionalität hinzufügt.

Zumindest für die theoretischen Informatiker (die es dabei tatsächlich gruselt) bleibt es, unabhängig vom Namen, ein Feld. ;)Wo der Mathematiker wiederum meckert, daß der Begriff Field (http://en.wikipedia.org/wiki/Field_%28mathematics%29) doch für was völlig anderes schon vergeben ist ...

mfg

Dr.Doom

2010-04-21, 11:51:23

Hmm, typischer 3DC-Thread. :tongue:
Ich finde, dass die Frage im Startbeitrag bereits erschöpfend durch meinen Beitrag beantwortet wurde. :cool: :D

_Gast

2010-04-21, 11:53:16

Wo der Mathematiker wiederum meckert, daß der Begriff Field (http://en.wikipedia.org/wiki/Field_%28mathematics%29) doch für was völlig anderes schon vergeben ist ...Die meckern doch dauernd. ;)

Kaum nennt man 2^10 Kilo, schon ist das Geschrei groß, weil Kilo anscheinend nicht 1024 sondern 1000 sei. Und schon müssen wir Informatiker auf Begriffe wie Kibi ausweichen.Ich finde, dass die Frage im Startbeitrag bereits erschöpfend durch meinen Beitrag beantwortet wurde. :cool: :DDas könnte vielleicht daran liegen, dass das 3DCenter kein Frage- und Antwortspiel, sondern ein Diskussionsforum ist. Wir müssen also erst darüber diskutieren, bevor wir die Antwort kennen. ;)

DocEW

2010-04-21, 13:10:35

Wo der Mathematiker wiederum meckert, daß der Begriff Field (http://en.wikipedia.org/wiki/Field_%28mathematics%29) doch für was völlig anderes schon vergeben ist ...
Kein Grund zum meckern: Weder kollidiert field mit array, noch Feld mit Körper. ;)

Gast

2010-04-21, 16:01:58

jetzt gehts ins philosophische. ;)

für die eigenschaften der laufzeit usw. ist natürlich die implementierung entscheidend und die wird sich als array nicht so verhalten wie sie sich als verkettete liste verhalten würde.

rein für die modellierung kannst du sie natürlich als lineare liste verwenden, auch wenn sie intern in arrays organisiert wird. dazu ist die abstraktionsebene ja da.So gesehen ist es völlig unmöglich eine Liste auf einem Computer zu implementieren. Der Hauptspeicher oder heutzutage besser gesagt der virtuelle Adressraum ist ein Array. Somit ist jegliche Listenimplementierung auf einem Computer im Endeffekt eine Implementierung auf einem Array. Dass dort dann noch das Betriebssystem dazwischen steckt und den Programmen etwas anderes vorgaukelt ändert nichts daran dass ein Pointer nichts anderes als ein Index eines Arrays ist.

Aquaschaf

2010-04-21, 23:33:14

Weshalb - in der Praxis - keiner pure Listen implementiert, sondern Zusatzfunktionalität hinzufügt.

In der STL gibt es doch pure Listen, beispielsweise? Und je nach Problemstellung ist eine pure Liste ja auch genau das was man haben will.

Pinoccio

2010-04-21, 23:39:13

In der STL gibt es doch pure Listen, beispielsweise? Und je nach Problemstellung ist eine pure Liste ja auch genau das was man haben will.Ich bin keine Experte für belastbare Quellen zu STL, aber hier (http://www.cplusplus.com/reference/stl/list/) steht: List containers are implemented as doubly-linked lists.
Ich kann mir auch kein realistisches Szenario vorstellen, wo eine pure Liste sinnvolle Vorteile bietet.

mfg

PatkIllA

2010-04-21, 23:43:19

Weshalb - in der Praxis - keiner pure Listen implementiert, sondern Zusatzfunktionalität hinzufügt.
Der wahlfreie Zugriff auf das Element mit dem Index x ist keine Zusatzfunktionalität sondern lediglich eine Hilfsmethode die x mal den nachfolger ermittelt.

Pinoccio

2010-04-21, 23:51:45

Der wahlfreie Zugriff auf das Element mit dem Index x ist keine Zusatzfunktionalität sondern lediglich eine Hilfsmethode die x mal den nachfolger ermittelt.Für mich ist eine Hilfsfunktionalität eine Zusatzfunktionalität. Und vermutlich ist sie eben nicht über x-mal Nachfolger implementiert sondern durch einen zusätzlichen Mechanismus. /edit: Gestrichen, wir reden ja nicht über eine konkrete Implementierung.

(Und streng abstrahiert geht sowas ja auch nicht, weil es kein Element mit Index x gibt, sondern nur den Anfang und Nachfolger - Was aber (mindestens seit Peano (http://de.wikipedia.org/wiki/Nat%C3%BCrliche_Zahl#Peano-Axiome)) das selbe ist. ;)) (Vorstehende Klammer ist kein ernstgemeinter Diskussionbeitrag)

mfg

Aquaschaf

2010-04-22, 08:11:14

Ich bin keine Experte für belastbare Quellen zu STL, aber hier (http://www.cplusplus.com/reference/stl/list/) steht: List containers are implemented as doubly-linked lists.
Ich kann mir auch kein realistisches Szenario vorstellen, wo eine pure Liste sinnvolle Vorteile bietet.

Was ist denn eine "pure" Liste, wenn keine einfach- oder doppelt-verkettete?

Pinoccio

2010-04-22, 10:18:54

Was ist denn eine "pure" Liste, wenn keine einfach- oder doppelt-verkettete?Ich halte eine einfach verkettete lineare Liste für pur, da sich die anderen aus ihr durch Erweiterung ableiten.

mfg

Dr.Doom

2010-04-22, 11:31:44

Ich halte eine einfach verkettete lineare Liste für pur, da sich die anderen aus ihr durch Erweiterung ableiten.

mfgNenn' es nicht pur, sondern naiv - dann freuen sich die Mathematiker. *g*

Gast

2010-04-22, 14:23:11

Zumindest für JAVA ist es so, daß ArrayList dir wahlfreien Zugriff auf Element n bietet, etwas, daß eine pure einfach verkettete (lineare) Liste per Definition nicht bietet.
Weshalb - in der Praxis - keiner pure Listen implementiert, sondern Zusatzfunktionalität hinzufügt.In Java bietet bereits das Interface List wahlfreien Zugriff per Index. Somit gibt es diese Funktion bei allen Klassen die das List-Interface implementieren, wozu auch die ArrayList gehört. Mehr noch, sogar die LinkedList implementiert List und erlaubt somit den Zugriff per Index.

Dr.Doom

2010-04-22, 14:58:08

In Java bietet bereits das Interface List wahlfreien Zugriff per Index. Somit gibt es diese Funktion bei allen Klassen die das List-Interface implementieren, wozu auch die ArrayList gehört. Mehr noch, sogar die LinkedList implementiert List und erlaubt somit den Zugriff per Index.Ob man sich nun eine konkrete Implemetation oder Schnittstelle in einer Programmiersprache aussieht oder die Datenstruktur in der Theorie, sind ja nun zwei paar Schuhe. :freak:

Ich mein, ich kann mir eine Programmiersprache ausdenken, nennen wir sie Turbo #Doom++ Geili Gold 2000, und sehe in meinem List-Interface vor, dass eine Methode spazierengehen() angeboten wird.
Das hat aber halt nichts mehr mit der List-Datenstruktur zu tun, die man in der ersten Vorlesungsstunde Praktische Informatik zu Gesicht bekommt.

Aquaschaf

2010-04-22, 16:23:19

Ich halte eine einfach verkettete lineare Liste für pur, da sich die anderen aus ihr durch Erweiterung ableiten.

Und beispielsweise in der STL gibts die doch, dort unter dem Namen "slist".

Tiamat

2010-04-23, 23:58:09

Lol hier werden aber zig Dinge durcheinandergebracht.

Eine Liste ist eine dynamische Datenstruktur, d.h die Liste kann zur Laufzeit beliebig erweitert werden, ohne dass dies irgendne Veränderung der vorherigen Listenstruktur zur Folge hat. Die Wortwahl Lineare Liste oder Liste sind äquivalent.

Hierbei hat ein Listenelement sowohl eine zu speichernde Information, als auch eine Information auf den Speicherbereich des nächsten Listenelements.

Die Begriffe einfach verkettete oder Doppelt verkettete Liste benutzt man nur, wenn man an Implementierungsdetails der Liste interessiert ist, ansonsten ist die Information irrelevant.

Natürlich kann man nach außen eine Liste anbieten, die jedoch intern als Array oder sonstwas implementiert ist. Aber das sind schon wieder Implementierungen, die von der ursprünglichen Definition abweichen und die meint man auch nicht, wenn man sich grad in der Vorlesung Algorithmen und Datenstruktur befindet.

In Java geben die Bezeichnungen Rückschlüsse auf die interne Implementierung wie z.b ArrayList oder LinkedList.

Das Java das Interface List zur Verfügung stellt, hat mit nichts anderem zu tun, als das alle Listen, die das Interface List implementieren, Teil der Collections ist, für die das Iterator Konzept und andere nützliche Dinge zur Verfügung gestellt werden.
Das hat dann aber eher was mit der Berürcksichtigung von Design Patterns zu tun, die man in der gesamten Java API an den vielfältigsten Stellen wiederfindet.

Damit ist denk ich alles gesagt.

Gruß
Tiamat

Aquaschaf

2010-04-24, 09:28:23

Die Begriffe einfach verkettete oder Doppelt verkettete Liste benutzt man nur, wenn man an Implementierungsdetails der Liste interessiert ist, ansonsten ist die Information irrelevant.

Nein, ist sie nicht. In der einfach verketteten Liste kommt man nur in O(n) an den Vorgänger eines Elements. Und die Komplexität der Operationen gehört schon zu einem abstrakten Datentyp dazu. Wenn man die wegläßt, dann kann man sich die Unterscheidung zwischen verschiedenen abstrakten Datentypen weitgehend sparen: in den meisten Fällen lassen sich die Operationen eines Datentyps mit denen eines anderen nachbilden, bloß eben mit anderer resultierender Komplexität.

Tiamat

2010-04-24, 10:57:49

Das bedeutet für meine Erläuterung keinen Abbruch.

Um die Laufzeiteigenschaften zu betrachten, muss man sich selbstverständlich mit Implementierungsdetails auseinandersetzen.

Oder sagst du deinem Arbeitskollegen, wenn er dich fragt, was du gestern gemacht hast und nehmen wir an du hast ne 200km Spritztour mit deinem Auto gemacht : Variante a) Ich hab gestern mit meinem Audi ne Spritztour gemacht oder Variante b) Ich hab gestern mit meinem Audi A3 TDI 125PS TDI 2 Liter Hubraum 16V ne Spritztour gemacht.

Der Vergleich hinkt ? Gut anderes Beispiel.
Wenn du gerade jemanden erläuterst, wie du ein Problem in deinem Programm gelöst hast und nehmen wir an, du hast irgendwelche Kundendaten aufgrund kaum vorhersehbarer Größe in einer Liste gespeichert.
Ist es dann für den anderen von Interesse, ob die Liste einfach oder doppelt verkettet ist. Doch nur wenn Implementierungsdetails gerade benötigt werden, für die Erläuterung der Sache an sicht, irrelevant.

Gruß
Tiamat

Aquaschaf

2010-04-24, 16:14:52

Es ist am Ende einfach eine Definitionssache und diese Diskussion damit relativ unsinnig. Im Fall der Liste sehe ich singly-linked/doubly-linked nicht als Implementierungsdetail, schließlich hat die letztere Variante zusätzliche Operationen bzw. welche die sich durch erstere nur ineffizient nachbilden lassen.

Wenn du sagst dass du eine Liste verwendest wegen der unvorhersehbaren Menge der Daten, dann ist auch das ein Implementierungsdetail.

Neomi

2010-04-24, 17:35:38

Um die Laufzeiteigenschaften zu betrachten, muss man sich selbstverständlich mit Implementierungsdetails auseinandersetzen.

Auf die Art kann man es aber auch so interpretieren, daß es ein Implementierungsdetail ist, ob ein Kontainer überhaupt entsprechent seiner Interfacedefinition funktioniert. Was soll schon ein Bug in der Implementierung sein, wenn kein Implementierungsdetail? ;)

Das Laufzeitverhalten ergibt sich zwar aus der Implementierung, ist aber kein Implementierungsdetail. Ob eine Operation nun konstante, logarithmische, lineare, quadratische oder was auch immer für eine Laufzeit hat, ist eine Eigenschaft des Interfaces. Der konstante Faktor ist dann ein reines Implementierungsdetail, aber der ist auch nicht relevant für die Skalierung mit der Problemgröße.

Yavion

2010-04-24, 20:21:02

Als ich das erste mal über Array-Listen gestolpert bin, kam mir der Begriff sehr eigenartig vor.
Ich habe seitdem immer gehofft, dass ich in der Praxis mal über irgendein Beispiel stolpere, in der eine LinkedList einer ArrayList überlegen ist aber das kam mir (zumindest in Java bzw .NET) einfach nie unter.

In sofern stehe in mitlerweise auch auf dem Standpunkt:
List is as List does.
Egal ob nun als dynamisches Array oder zeigerverkettete Struktur.
Konkret bedeutet das dann meistens ArrayList, weil schneller bei wahlfreien Zugriff und speicherschonender.