Diskussion:Liste (Datenstruktur)/Archiv/1
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.
Zustimmung! Komplexitätsangaben sind sinnvoll. Vielleicht ist es am besten, eine Infobox für Datenstrukturen zu machen, die übersichtlich und einheitlich soche Angaben enthält. -- Chwinter (Diskussion) 22:02, 30. Apr. 2013 (CEST)
Die Aussage über exponentiellen Zeitbedarf unter Geschwindigkeit von Listen in der Praxis ist falsch und deshalb werde ich sie löschen. -- Chwinter (Diskussion) 22:02, 30. Apr. 2013 (CEST)
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)
Ä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)
Lemma
... wieso nicht Verkettete Liste und Liste (Datenstruktur) als Weiterleitung? -- Gohnarch░░░░ 09:41, 27. Mai 2009 (CEST)
Klingt sinnvoll. Jetzt ist es genau andersherum, aber die vorgeschlagene Zuordnung finde ich besser. Gibt es hierzu weitere Meinungen? -- Chwinter (Diskussion) 21:00, 1. Mai 2013 (CEST)
Zyklische Liste
Zitat: "Eine Liste kann zu einem Zyklus (zyklische Liste) geschlossen werden, indem der Zeiger des letzten Listenelementes so geändert wird, dass er auf ein beliebiges Listenelement zeigt. Dieses Listenelement (und nur dieses) hat dann zwei Vorgänger, alle anderen Elemente haben genau einen Vorgänger."
Was dort steht ist falsch! Begründung: Man setze den Nachfolger des letzten Listenelements auf das erste Listenelement. Nutzer142 11:23, 12. Nov. 2011 (CET)
Bäume
Änderung kann wieder rückgängig gemacht werden, nicht der Überschrift ist falsch, sondern der Inhalt des Abschnitts. Der Inhalt geht nicht auf die Unterschiede zur Baumstruktur ein, bzw. fehlen Anwendungen, Vor- und Nachteile. (nicht signierter Beitrag von 89.246.183.37 (Diskussion) 12:04, 12. Jan. 2013 (CET))
Vorteile doppelt verkettete Liste
"Die Elemente in der zweiten Hälfte einer sortierten Liste sind schneller aufzufinden.". Warum genau?/Ich halte das fuer falsch. --JasperOCommons (Diskussion) 11:59, 25. Feb. 2014 (CET)
- Bei n Einträgen und einem gesuchten Eintrag, der m Elemente vom mittleren Element entfernt in der zweiten Hälfte ist, muss man bei der einfach verketteten Variante über 0,5n + m Elemente iterieren. Bei der doppelt verketteten Variante sind es nur 0,5n-m. Da m per Definition im Intervall [1;0,5n] liegt, ist ein Auffinden von Elementen in der doppelt verketteten Variante für den speziellen Fall schneller. Das setzt allerdings voraus, dass bekannt ist, dass das gesuchte Element in der zweiten Hälfte der Liste liegt. Gruß--Flash1984 (Diskussion) 15:23, 3. Mär. 2014 (CET)
Der Artikel ist äußerst unbefriedigend
Bereits im zweiten Abschnitt beginnt ein Versuch, Listen mit Arrays in Bezug auf die Laufzeitkomplexität von Array-Typischen Operation zu vergleichen. Dabei wird die Tatsache verkannt, dass Listen für einen völlig anderen Zweck als Arrays gedacht sind und nur in trivialen Fällen überhaupt mit diesen verglichen werden können.
Der Hinweis auf Lisp schließlich ist deswegen irreführend, weil die hier diskutierten, nicht-hierarchischen Listen eben nicht die "Basisdatenstruktur" (was immer genau das Wort exakt bedeutet) von Lisp sind.
Der Hinweis auf häufigere CacheMisses schließlich scheint wenig begründet und einem "Gutdünken" entsprungen zu sein.
Über diesen Irrweg kommen die Autoren dann zu einem Ergebnis, das gleichzeitig falsch und irrelevant ist. Letzteres dürfe der Grund sein, warum sich diese Darstellung seit Jahren hier unkritisiert halten konnte.
Aus diesen Gründen bedarf der Artikel meines Erachtens einer gründlichen Überarbeitung. --West of House (Diskussion) 11:20, 11. Dez. 2014 (CET)
- Dito! Schräubchenkundlerisches Schwadronieren aus dem scheuklappenlimitiertem Blickwinkel eines Pennälers. Jemand, der weiß, was dynamische Datenstrukturen, Zeiger, "Container" oder "Schnittstellen" sind, braucht diesen Artikel nicht, kann ihn aber beurteilen. Wer diese und einige weiteren Begriffe nicht kennt, versteht den Artikel erst gar nicht. Es ist also ein typisches Streberreferat vor einer 12. Klasse vom Schüler für den Lehrer, um zu zeigen, wie schlau der Schüler die Stichworte des Unterrichts zusammenfassen kann. Das Java-orientierte Vokabular unterstreicht den Schulcharakter, und daß dieses Vokabular als bekannt vorausgesetzt wird, deutet auf die Zielgruppe aus Mitschülern und Lehrern.
- Die enge Limitierung wird schon im ersten Satz deutlich, wo Liste mit dynamisch (explizit) verketteter Liste, einem untergeordneten Sonderfall von Listen, gleichgesetzt wird. Nichtdynamische und implizit verkettete Listen werden nicht einmal erwähnt, dabei werden dynamisch verkettete Listen üblicherweise auf implizit verketteten Listen abgebildet. Die einfachste implizit verkettete Listen ist das Array oder der Stream mit dem konstanten Abstand Eins zum Vorgänger und/oder Nachfolger. Etwas anspruchsvollere, implizit verkettete Listen sind die jeweils zu durchlaufenden Knoten eines binären Baumes von den Blättern zur Wurzel (die implizite Vorschrift für den Vorgänger ist die Indexhalbierung) oder beim Shellsort die zu sortierenden Teillisten mit vorgegebenem Objektabstand.
- Bezeichnenderweise ist die Verlinkung zum englischen Artikel "Linked List" anstatt zu "List" gut gelungen. Dort wird dann auch korrekt die "Linked List" von "List" unterschieden. Meiner Meinung nach braucht es wenigstens drei Artikel: Liste (allgemein von zB Einkaufs- bis zur Roten oder Stückliste), Liste (grundsätzliche Idee für Datenstrukturen) und Verkettete Liste.--46.114.136.17 16:25, 14. Feb. 2015 (CET)
Array
Ich einen ausführlicheren vergleich mit Arrays für wichtig vielleicht eine tabelle wo die laufzeitkomplexitäten für standardoperationen verglichen werden (nicht signierter Beitrag von 79.215.84.231 (Diskussion) 23:32, 15. Apr. 2008 (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. (nicht signierter Beitrag von 198.240.212.30 (Diskussion) 14:17, 21. Sep. 2004 (CEST))
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)
"Die Elemente in der zweiten Hälfte einer sortierten Liste sind schneller aufzufinden" - na ja: wenn man weiß, dass das Gewünschte näher am Ende als am Anfang liegt - geordnet/sortiert ist nicht wirklich der Punkt, und Wissen teuer. (nicht signierter Beitrag von 188.100.196.116 (Diskussion) 15:57, 11. Jan. 2016 (CET))