Diskussion:Liste (Datenstruktur)

Laufzeitkomplexität, Vorteile von Listen gegenüber anderen Datentypen

Die Laufzeitkomplexität fehlt völlig, z.B. O(n) (linear) für den Zugriff auf ein Element. Allerdings O(1) für das Einfügen eines Elements am Anfang etc. Vorteile der Speicherverwaltung gegenüber Arrays etc. fehlt auch alles.

Array

Ich einen ausführlicheren vergleich mit Arrays für wichtig vielleicht eine tabelle wo die laufzeitkomplexitäten für standardoperationen verglichen werden

Implementieren...

"und nicht extra eine Datenstrukturliste implementieren muss" heißt doch sicherlich "und nicht extra eine Datenstruktur Liste implementieren muss", oder?

Ja, hab ich das etwa geschrieben, oder wer hat an meinem Text rumgepfuscht? --Coma 09:14, 30. Apr 2003 (CEST)

Aha, Martin Aggel war der Übeltäter... --Coma 09:15, 30. Apr 2003 (CEST)

Möchte nur erwähnen, dass die Überschriften recht winzig erscheinen. --nerd 15:25, 22. Mai 2003 (CEST)

Ich möchte nicht in den Verdacht kommen, meine Programmlistings wie sauer Bier anzubieten, aber wie wäre es mit diesen beiden Listings als Beispiele für Programme mit Zeigern (pointern): Benutzer:Arbol01/Programm_mit_Zeigern --Arbol01 11:59, 25. Mär 2004 (CET)

ADT Liste vs. DT verkettete Liste

wenn mich nicht alles täuscht, dann handelt der Artikel von der Datenstruktur verkettete Liste, obwohl der Titel eigentlich mehr auf den abstrakten Datentypen Liste (unabhängig von möglichen Implementationen wie beispielsweise Arrayliste oder eben auch verkettete Liste) schliessen liesse. Eigentlich bräuchte es also die Artikel

• Liste (Abstrakter Datentyp)
• verkettete Liste (Datenstruktur)
• Arrayliste (Datenstruktur)
• was Euch noch so an Listen-Implementierungen einfällt

und der Artikel mit dem Titel Liste Datenstruktur müsste wegfallen, weil es eben nur nen Datentypen Liste gibt, nicht aber eine allgemeine Struktur von Listenimplementierungen. Meinungen dazu?

Den Hinweis, dass im allgemeinen verkettete Listen auch ungenau als Listen bezeichnet werden und dass verkettete Listen vielleicht die häufigste Listenimplementierung darstellen, wäre ja in Ordnung.

Stimmt: für einfache Zwecke können Listen (die dann eben nur bis zu einem vorher festgelegten Punkt wachsen können) durchaus mit einem Array als interner Datenstruktur implementiert sein. Allerdings glaube ich nicht, daß separate Artikel nötig sind. Was gibt es über Arraylisten so viel zu sagen, außer daß sie eben bestimmten Einschränkungen unterliegen, weil sie eben auf Arrays basieren? --Tobias 13:53, 3. Aug. 2007 (CEST)

vergleiche

Vergleiche der verschiedenen Implementierunge wären hilfreich. Zum Beispiel sollte man erfahren können, dass Baum-Listen eine Komplexität von O(log(n)) für das hinzufügen von Elementen besitzen.

Vor- und Nachteile von Listen

Warum kann man in doppelt verketteten Listen "problemlos Elemente aus der Liste löschen und einfügen", während es in einfach verketteten aufwändig ist? imho geht das in O(1) (an der aktuellen Position) bei Listen und ist im Gegensatz zu z.B. AVL-Bäumen eher ein Vorteil!

In beiden Fällen braucht es O(n) um an eine bestimmte Stelle in der Liste zu kommen. Bei der einfach verketteten Liste muss man aber den Vorgänger kennen, um ein Element zu entfernen. Wenn man die Liste aber nur ab einer gewissen Stelle kennt (man bedenke vor allem Pointer-Listen in C), dann kann man aus einer einfachverketten Liste keine Elemente löschen oder einfügen. Hat man Anfang und aktuelle Position (z.B. einen Iterator), dann braucht man wiederum O(n) um den Vorgänger zu finden. --82.141.60.133 18:52, 17. Jul 2006 (CEST)

Es ist auch unklar, warum keine zwei Sonderfälle mehr betrachtet werden müssen, wenn es einen Zeiger auf das Ende einer einfach verketteten Liste gibt. Auch kann nicht von hinten nach vorne iteriert werden.

Der Vorteil liegt doch imho darin, dass Elemente immer in O(1) an das Ende eingefügt werden können, da sofort zum Ende gesprungen werden kann, was sonst nochmal O(n) kosten würde.

Ja, dies wird in der Regel genutzt um einen FIFO zu implementieren. Ohne diesen Zusatzeiger wird eine einfach verkettete Liste meist als Stack (LIFO) gehandhabt. --82.141.60.133 18:56, 17. Jul 2006 (CEST)

Aufwand

> Es ist aufwändig [...] Knoten einzufügen, zu löschen und die Liste zu sortieren

Aufwändig im Vergleich wozu? Als erste Assoziation fallen mir Arrays ein und für die stimmt das ja nun eher nicht :D

Änderung, Überarbeitung, Erweiterung

In den nächsten Tagen würde ich gerne diese Seite über "verkettete Listen" überarbeiten. Wenn jemand noch Vorschläge hat, kann er sie hier nennen.

Gruß Lars

Skip-Liste

Ich würde mir wünschen, der Abschnitt über Skip-Listen würde diese noch näher erläutern. Zielgruppe der Wikipedia ist m.E. die Allgemeinheit. Bevor auf verschiedene Typen von Skip-Listen eingegangen wird, sollte erst einmal deutlich gemacht werden, was eine Skip-Liste eigentlich ist. Leonach 16:46, 11. Jun. 2007 (CEST)

Ich habe eine kleine allgemeine Beschreibung der Skipliste eingefügt. Egentlich würde ich einen eigenen Artikel für die Skipliste für angebracht halten, allerdings habe ich die Befürchtung, dass dieser wegen Relevanz Gründen gelöscht wird. --4pf3154f7 12:29, 25. Sep. 2008 (CEST)

Adaptive Liste

Unter "Adaptive Liste" steht: "Dieses Prinzip geht von der Voraussetzung aus und sortiert die Listenelemente nach ihrer Zugriffshäufigkeit" Welche Voraussetzung?? --Rubik-wuerfel 17:30, 16. Jul. 2007 (CEST)

Da war in dieser Bearbeitung etwas Sinngehalt über die Wupper gegangen. Ich bau das mal wieder ein. --jpp ?! 20:01, 16. Jul. 2007 (CEST)

Bildbeschreibung fehlt bei [[Bild: Knoten _(Informatik).png]], [[Bild: Einfach_verkettete_Liste.png]] und [[Bild:Liste_SkipList.png]]

Der Artikel enthält ein Bild, dem eine Bildbeschreibung fehlt, überprüfe bitte, ob es sinnvoll ist, diese zu ergänzen. Gerade für blinde Benutzer ist diese Information sehr wichtig. Wenn du dich auskennst, dann statte bitte das Bild mit einer aussagekräftigen Bildbeschreibung aus. Suche dazu nach der Textstelle [[Bild: Knoten _(Informatik).png]], [[Bild: Einfach_verkettete_Liste.png]] und [[Bild:Liste_SkipList.png]] und ergänze sie.

Wenn du eine fehlende Bildbeschreibung ergänzen willst, kannst du im Zuge der Bearbeitung folgende Punkte prüfen:

• Namensraum Datei: Bilder sollte im Namensraum Datei liegen. Bitte ändere die alten Bezeichnungen Bild: und Image: in Datei:.
• Skalierung: Außerhalb von Infoboxen sollten keine festen Bildbreiten (zum Beispiel 100px) verwendet werden. Für den Fließtext im Artikelnamensraum gibt es Thumbnails in Verbindung mit der automatischen Skalierung. Um ein Bild/eine Grafik in besonderen Fällen dennoch größer oder kleiner darzustellen, kann der „upright“-Parameter verwendet werden. Damit erfolgt eine prozentuale Skalierung, die sich an den Benutzereinstellungen orientiert. --SpBot 23:21, 1. Mär. 2009 (CET)

Lemma

... wieso nicht Verkettete Liste und Liste (Datenstruktur) als Weiterleitung? -- Gohnarch^░░░░ 09:41, 27. Mai 2009 (CEST)