Diskussion:Liste (Datenstruktur)

Letzter Kommentar: vor 4 Jahren von Nomen4Omen in Abschnitt Skip Liste / Container
Archiv
Archiv
Wie wird ein Archiv angelegt?

Aufwand

Bearbeiten

> 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 (nicht signierter Beitrag von 84.143.15.190 (Diskussion) 18:49, 15. Nov. 2005 (CET))Beantworten

Bearbeiten

GiftBot (Diskussion) 00:15, 27. Nov. 2015 (CET)Beantworten

Struktur und Einleitung gekürzt und entwirrt, Korrekturen angebracht.

Bearbeiten

Ich habe einiges entfernt, was sachlich falsch oder in erster Linie Meinung/Beurteilung war. Einige Definitionen habe ich formalisiert. Der Text ist jetzt etwas weniger blöd aber immernoch schwach, da die Liste als Datenstruktur rekursiv gedacht ist, die Programmbeispiele dem aber keinerlei Rechnung tragen. Rekursive Beispiele wären viel kürzer.

West of House (Diskussion) 15:40, 19. Jan. 2017 (CET)Beantworten

Sentinel

Bearbeiten

@Benutzer:West_of_House, die m.E. korrekte (oder zumindest die wichtige) Verwendung des Wächterzeiger oder Sentinel hast Du rausgeschmissen. Übrig geblieben ist die als »Kopf« (»spezieller Knoten am Anfang der Liste«), für die man m.E. keine extra Begriffsbildung braucht und die ich eher rausgeschmissen hätte. --Nomen4Omen (Diskussion) 17:45, 19. Jan. 2017 (CET)Beantworten

@Benutzer:Nomen4Omen Du hast Recht, der Abschnitt über Listen mit Kopf ist überflüssig. Wir sollten ihn auch entfernen, wenn niemand das ander sieht.

@Benutzer:Nomen4Omen Findest Du, das Sentinels in bezug auf listen von Bedeutung sind? Ist es nicht eher so, dass bei der sequentiellen Suche der Nachfolgeknoten sowieso in die Hand genommen werden muss und die Feststellung, ob er NIL ist quasi umsonst uu haben ist? Und selbst wenn man ein Sentinel einführt, um eine Bedingung "wahr" werden zu lassen, müsst man das Listenende suchen um ein Sentinel einzuführen. Ist so ein vorgehen sinnvoll? (nicht signierter Beitrag von West of House (Diskussion | Beiträge) 10:22, 15. Feb. 2017 (CET))Beantworten

@Benutzer:West_of_House, im Artikel Sentinel (Programmierung)#Version mit Sentinel kommt ein Code-Snippet, bei dem in der heißen Schleife durch den Sentinel tatsächlich eine Abfrage gespart wird, die dafür bei Verlassen der Schleife wieder bezahlt werden muss, allerdings kalt, d.h. nur einmal auszuführen. Du hast vollkommen Recht, dass der Nachfolgeknoten in die Hand genommen werden muss. Aber die Abfrage auf NIL wird von den Sentinel-Priestern NICHT als für umme angesehen!! - Auch nicht quasi!! --Nomen4Omen (Diskussion) 18:25, 15. Feb. 2017 (CET)Beantworten

@Benutzer:Nomen4Omen Habs wieder eingabaut. Bitte mal checken, danke. (nicht signierter Beitrag von West of House (Diskussion | Beiträge) 10:09, 23. Feb. 2017 (CET))Beantworten

Skip Liste / Container

Bearbeiten

Das Wort "Container" kommt nur in diesem Abschnitt vor, und bedeutet glaube ich eigentlich einfach "Knoten", weshalb es durchgehend durch "Knoten" ersetzt werden sollte. Ausserdem könnte sich der Artikel entweder für "Zeiger" oder für "Verweis" entscheiden. 194.174.73.80 14:37, 11. Feb. 2020 (CET) Marco Pagliero BerlinBeantworten

Lieber Marco!
Ja, das Wort "Container" kommt nur in dem einen Abschnitt vor.
Laut Artikel Container (Informatik) bedeutet es aber NICHT einfach Knoten, sondern wenn schon Knoten, dann eine Ansammlung (oder die Gesamtheit) von Knoten gleichen Typs.
Der Begriff würde also NICHT korrekt im besagten Abschnitt "Skip-Liste" verwendet, denn dort scheint er im Sinn von "Knoten" ["enthalten ... einen Zeiger auf den nächsten Container"] (oder Element oder Vorkommen) verwendet zu sein. Wenn ich das alles recht verstehe, wäre die Skip-Liste selbst der Container (analog zu AVL-Baum etc.).
Das Wort "Container" wurde am 18:35, 24. Sep. 2008‎ von 193.170.48.26 in den Artikel eingebracht. Man kann also den Autor vermutlich nicht mehr fragen.
Mit "Zeiger" und "Verweis" hast du Recht.
Deine Korrekturen auf Plural gehen in Ordnung.
--Nomen4Omen (Diskussion) 18:52, 13. Feb. 2020 (CET)Beantworten