Doppelt verkettete Liste
lima-city → Forum → Programmiersprachen → C/C++ und D
anfassen
array
element
hauptspeicher
index
konstrukt
korrigieren
letzte element
list
liste
listen
pointer
punkt
queue
rest
speichern
sprache
stelle
struktur
zeitaufwand
-
Hallo,
noch mal eine Frage an die erfahrenen Leute hier: ich bin gerade dabei eine doppelt verlinkte Liste zu basteln... die meisten Implementierungen die ich mir angeschaut habe arbeiten mit Pointern, also dh ein Listenelement enthält Pointer auf den Vorgänger und den Nachfolger.
Warum wird das so gemacht? Warum sammelt man die Elemente nicht in einem Array und speichert im Element zwei Zahlen i,j die angeben, an welcher Stelle im Array sich Nachfolger und Vorgänger befinden?
Das gute wäre, dass man dann überprüfen könnte, ob der Verweis stimmt, wenn man iwo speichert, wie viel Elemente die Liste hat... mit Pointern hat man ja gar keine Kontrolle. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Weil du bei einer verketten Liste einfach ein neues Element erstellen und in die Liste einfügen kannst. Wenn die verkette Liste ein Array ist, dann musst du, wenn du ein neues Element bekommst, oder eines löschen willst, immer ein komplett neues Array machen und den Inhalt rüberkopieren, da ein Array ja eine konstante Größe hat.
Möglich wäre es also, aber langsamer und speicherhungriger bei der Ausführung und wahrscheinlich auch komplizierter zu programmieren. -
Ich hab noch mal in meinen schlauen Büchern nachgeschaut, da steht dass der Stack bei C (NICHT C++) auf 64 KB begrenzt ist.
Vll will man ja eine größere Liste haben...? Außerdem ist der Stack sicher auch nur ein Array.Wenn die verkette Liste ein Array ist, dann musst du, wenn du ein neues Element bekommst, oder eines löschen willst, immer ein komplett neues Array machen und den Inhalt rüberkopieren, da ein Array ja eine konstante Größe hat.
ich hab mir das so vorgestellt:
1. Der Array ist ein Puffer (wird "zu groß" angelegt). Ich merke mir wie groß der Puffer (int m) ist und wie viele Elemente die Liste enthält (int n). Wenn n == m wird (evtl mit realloc) neuer Speicher alloziert und m entsprechend raufgesetzt.
2. Wenn ich ein Element aus der Liste lösche, nehme ich einfach das letzte Element aus dem Array und kopiere es auf den freigewordenen Speicherplatz. Natürlich muss ich dann noch die Verweise korrigieren aber das ist ja kein Problem. Und mit n-- ist das letzte Element hinten "verschwunden". So bleibt alles kompakt zusammen.
-
listen sind spezielle datentypen. nun kommt es darauf an, wozu bzw. was du machen willst.
eine liste (queue, stack, dequeue, ...) ist generell im zeitaufwand besser als ein array.
Bsp:
suchen
array: nimm das erste/letzte element, ist dies nicht das gesuchte nimm das nächste, solange element != null oder element != gesuchtes element.
--> im schlimmsten fall alle n elemente durchsuchen.
liste: gilt das selbe.
queue/dequeue/stack: gibts nicht
einfügen:
array: suche freien platz im array und füge das neue element ein
--> im schlimmsten fall ist das n-te element == null.
liste: vorne / hinten anfügen.
queue/dequeue/stack: vorne / hinten anfügen.
löschen:
array: suche element (siehe oben) und lösche
--> im schlimmsten fall ist das n-te element zu löschen.
liste: lösche erste/letzte element oder wie array.
queue/dequeue/stack: lösche erste/letzte element
du siehst, dass es generell egal ist, was du verwendest. es sei denn dir genügt eine queue, dequeue oder stack. diese sind natürlich vom zeitaufwand extrem effizienter als ein array. und du darfst nicht immer von kleinen arrays / listen ausgehen!
zu deinen 2. punkt des letzten beitrags:
dadurch geht die ordnung der liste (arrays) verloren. überleg ma wozu listen verwendet werden.
mfg koslo
p.s. wenn du hilfe mit der implementierung einer liste (mit pointern) brauchst meld dich, dann schick ich sie dir!
Beitrag geändert: 4.11.2008 22:16:53 von koslo -
eine liste (queue, stack, dequeue, ...) ist generell im zeitaufwand besser als ein array.
Es sei denn, Du weißt, wie viele Elemente Du hast und hättest gern wahlfreien Zugriff. Letzterer beeinflusst dann evtl. wieder die möglicherweise anwendbaren und Sortier- und Suchverfahren (es gibt nicht nur die von Dir beschriebene lineare Suche...) etc.
Der Rest Deines Beitrags war mir dann leider zu konfus. ;)
-
Der Rest Deines Beitrags war mir dann leider zu konfus. ;)
lol
was genau meinst du? -
nun:
wir haben in der Schule Arrays benutzt, wenn wir z.B. etwas sortieren wollten. Das heißt dort lohnt es sich.
Ich kann dir auch nicht die korrekte antwort geben. Ich denke jedoch, dass die doppelt verkettete Liste genauso funktioniert, wie ein Array, nur das du halt bei der doppelt verketteten Liste mehr selber Hand anlegen kannst und verstehst, wie ein Array arbeitet... -
Man benutzt Pointer um nicht alle Elemente anfassen zu müssen, wenn man 1 Element in der Mitte des Arrays hinzufügen will.
In deinem Fall müsste man dann jedes Element des Arrays durchgehen und die Index-Angaben anpassen.
Benutzt man hingegen Pointer muß man dies nicht, da die Pointer-Adressen sich nicht ändern
Man muß nur maximal 3 Elemente anfassen, der Rest bleibt unberührt.
Grüßle
Beitrag geändert: 5.11.2008 16:02:52 von scout -
zu deinen 2. punkt des letzten beitrags:
man muss die Referenzen natürlich korrigieren.
dadurch geht die ordnung der liste (arrays) verloren. überleg ma wozu listen verwendet werden.
IWo müssen auch die Elemente der Liste gespeichert werden...?
Wo soll das schon sein... im Nirgendwo??
Das kann nur in einem Array sein! Stacks, Queues oä sind HÖHERE Datenstrukturen als ein Array dh ein Array mit Zusatzfunktionen.
Der Speicher im PC ist ja auch ein Array und ein Pointer ist nur ein "Index" dazu.
MMn läuft das aufs gleiche hinaus, ob ich schreibe:
* element = ... oder
list[ i ] = ...
und
struct element{
element * next;
element * prev;
int data;
};
oder
struct element{
int next;
int prev;
int data;
};
Man benutzt Pointer um nicht alle Elemente anfassen zu müssen, wenn man 1 Element in der Mitte des Arrays hinzufügen will.
wenn man sich merkt an welcher Stelle das Element im Array sich das Element befindet, reicht das ja. Der Pointer merkt sich stattdessen halt die Stelle im Speicher.
Ich sehe jetzt ein, warum man Pointer nimmt: um es sauberer zu machen aber im Prinzip kann man eine doppelt verlinkte Liste auch problemlos ohne Pointer programmieren. Es gibt ja auch Sprachen ohne Pointer oder äquivalente Konstrukte (altes BASIC) und da wird man ja auch doppelt verlinkte Listen implementieren können.
das wäre schön. Vielen Dank.
p.s. wenn du hilfe mit der implementierung einer liste (mit pointern) brauchst meld dich, dann schick ich sie dir!
Beitrag geändert: 5.11.2008 18:16:24 von danger-mouse -
Wo müssen auch die Elemente der Liste gespeichert werden...?
Wo soll das schon sein... im Nirgendwo??
In einer dynamisch (bspw. mit malloc()) angelegten Datenstruktur irgendwo im frei belegbaren Hauptspeicher.
Ganz im Gegensatz zum C-Array, das auf dem Stack angelegt wird.
Das kann nur in einem Array sein! Stacks, Queues oä sind HÖHERE Datenstrukturen als ein Array dh ein Array mit Zusatzfunktionen.
Es gibt keine "höheren" und keine "niederen" Datenstrukturen. C-Arrays sind keine Datenstrukturen. Eigentlich gibt es in C gar keine Arrays. Es gibt lediglich eine zusätzliche Schreibweise für Pointer ("syntactic sugar"), die der Schreibweise für echte Arrays in anderen Sprachen ähnelt.
Der Speicher im PC ist ja auch ein Array ...
Nein ist er nicht. Auch wenn du den Hauptspeicher so betrachten möchtest.
... und ein Pointer ist nur ein "Index" dazu.
MMn läuft das aufs gleiche hinaus, ...
Richtig, wie ich bereits sagte: Die Array-Schreibweise ist unnötig.
... ob ich schreibe:
* element = ... oder
list[ i ] = ...
Wenn list auf die gleiche Adresse wie element zeigt und wenn i == 0 ist.
struct element{
element * next;
element * prev;
int data;
};
oder
struct element{
int next;
int prev;
int data;
};
Nein, ein INT ist etwas anderes als ein Pointer auf eine Struktur vom Typ element. Der Compiler wird wahrscheinlich meckern, wenn du versuchst einem INT einen Zeiger auf eine Struktur zuzuweisen (was du ja tun müsstest, wenn du next oder prev aktualisieren möchtest) -- und das zu Recht: Daten (INT) und Adressen (Pointer) sollten normalerweise schön getrennt behandelt werden. Auch wenn du es dir nicht vorstellen kannst: Adressregister und Datenregister in Prozessoren können unterschiedliche Breite haben. Heutzutage sind zwar beide meistens noch 32 Bit breit. Aber das war schon mal anders (z.B.: Z80, Intel 8080) und kann sich auch jederzeit wieder ändern.
Es gibt ja auch Sprachen ohne Pointer oder äquivalente Konstrukte (altes BASIC) und da wird man ja auch doppelt verlinkte Listen implementieren können.
Nöö, wenn wirklich keinerlei "äquivalente Konstrukte" in der Sprache existeren, kann man das nicht. Antike Basic-Dialekte hatten für diesen Zweck die Funktionen PEEK und POKE. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
