Wozu sind Verkettete Listen gut
-
Wozu der ganze Aufwand (Ich meine die Verkettete Liste), wenn man doch genauso gut ein Array aus Strukturen bilden kann.
Es wird, vermute ich, einen Grund haben, aber welchen?
Danke
-
Versuch mal, in der Mitte des Arrays was einzufügen...
-
Hauptsächlich Selbstzweck im Informatikunterricht. Die Vorteile klingen zwar zunächst gut, sind praktisch aber eher selten relevant, die Nachteile sind hingegen fast immer spürbar.
-
SG1 schrieb:
Versuch mal, in der Mitte des Arrays was einzufügen...
Das ist bei Datenbanken sehr praktisch, oder?
Danke
-
Du verstehst nicht.
Wenn man etwas in der Mitte einfügen möchte, muss man n/2 Elemente um einen Platz verschieben und kann erst dann das Element einfügen.
Wenn du etwas in der verkettete Liste einfügen möchtest, so musst du nur ein Zeiger vom Vorgänger und Nachfolger in der Liste aktualisieren.
Der Nachteil der Liste ist aber dass die Elemente wild im Speicher herumliegen. Das ist nicht besonders Cache freundlich und hat ebenso den Nachteil dass man nicht direkt das ite Element bestimmen kann. Man muss potenziell vom ersten Element sich durchiterieren. Im schlimmsten Fall braucht man n/2 Schritte.
-
Ps:
Für Datenbanken nimmt man etwas komplexeres, nämlich B× Bäume.
-
Verkette Listen sind zwar etwas merkwürdig, aber doch "praxistauglicher" als binäre Bäume, die habe ich in meiner fast 25jährigen Praxis noch nicht gebraucht, da ich keine Datenbanken programmiere, aber verkettete Listen habe ich schon 3-10x gebraucht.
Und zwar dann, wenn ich etwas einfügen mußte, aber ich arbeite gerne mit "Doppelzeiger", dann wird es erst richtig lustig, aber nur für einen C-Programmierer
-
Es gibt x Varianten von Listen und alle sind abhängig vom Szenario von Vor- oder Nachteil
die Varianten gibt es nicht einfach nur weil es den Leuten langweilig war und man einfach mal was programmieren wollte
Wenn deine Szenarien zu klein sind ist es meistens egal welche Form man nutzt - dafür muss auch erst mal was zusammen kommen das es relevant wird
-
Ich habe es verstanden Leute, eure Antworten haben mir etwas zu denken geben.
Danke
-
-
Bitte ein Bit schrieb:
Du verstehst nicht.
Wenn man etwas in der Mitte einfügen möchte, muss man n/2 Elemente um einen Platz verschieben und kann erst dann das Element einfügen.
Wenn du etwas in der verkettete Liste einfügen möchtest, so musst du nur ein Zeiger vom Vorgänger und Nachfolger in der Liste aktualisieren.
und um dort hinzukommen, mußt du dich n/2 mal mit pointer chase entlanghangeln.
