Doppelt verkettete lineare Liste

freakC++

Hallo zusammen,

das Prinzip der linearen Liste kenne ich und ich finde es ziemlich gut. Bei der doppelt verketten Liste kennt jedes Element auch seinen Vorgänger. Ich verstehe aber die Vorteile nicht? Könnt ihr mir die Vorteile erläutern?

Folgende Vorteile kenne ich:

Die Elemente in der zweiten Hälfte einer sortierten Liste sind schneller aufzufinden.

Schnelles Löschen und Einfügen von Elementen.

1.) Warum sind die Elemente schneller zu finden?
2.) Wieso sollte das Löschen schneller gehen? Ich muss doch trotzdem vorne anfangen?

Vielen Dank
lg, freakC++

CStoll

freakC++ schrieb:

1.) Warum sind die Elemente schneller zu finden?

Du kannst vom letzten Element anfangen und dich rückwärts durch die Liste durchhangeln, bis du am Ziel angekommen bist

2.) Wieso sollte das Löschen schneller gehen? Ich muss doch trotzdem vorne anfangen?

Beim Löschen geht man davon aus, daß du das zu löschende Listen-Element in der Hand hast - dann brauchst du nur noch den Vorgänger und Nachfolger zu greifen und miteinander zu verlinken. Bei der einfach verketteten Liste mußt du wieder von vorne anfangen, um den Vorgänger zu bestimmen.
(wenn du nur ein Kriterium in der Hand hast, um das zu löschende Element zu bestimmen, macht das keinen Unterschied - da kannst du dir den Vorgänger unterwegs auch merken)

freakC++

CStoll schrieb:

freakC++ schrieb:

1.) Warum sind die Elemente schneller zu finden?

Du kannst vom letzten Element anfangen und dich rückwärts durch die Liste durchhangeln, bis du am Ziel angekommen bist

Und was soll das bringen? Es ist doch gleichwertig, ob ich mich von vorne nach hinten oder von hinten nach vorne durchhangle. Es würde nur etwas bringen, wenn ich von vorne UND von hinten gleichzeitig durch die Liste iterieren kann.

CStoll schrieb:

Beim Löschen geht man davon aus, daß du das zu löschende Listen-Element in der Hand hast - dann brauchst du nur noch den Vorgänger und Nachfolger zu greifen und miteinander zu verlinken. Bei der einfach verketteten Liste mußt du wieder von vorne anfangen, um den Vorgänger zu bestimmen.
(wenn du nur ein Kriterium in der Hand hast, um das zu löschende Element zu bestimmen, macht das keinen Unterschied - da kannst du dir den Vorgänger unterwegs auch merken)

Das verstehe ich nicht so richtig. Bei der einfach verketteten Liste iteriere ich solange durch die sortierte Liste bis ich beim gesuchten Element bin, das ich lösche. Was meinst Du mit "Vorgänger und Nachfolger [...] verlinken"?

Danke dir
lg, freakC++

asc

freakC++ schrieb:

CStoll schrieb:

Du kannst vom letzten Element anfangen und dich rückwärts durch die Liste durchhangeln, bis du am Ziel angekommen bist

Und was soll das bringen? Es ist doch gleichwertig, ob ich mich von vorne nach hinten oder von hinten nach vorne durchhangle.

Je nach dem wo das gesuchte Element liegt, kann das schon einen wesentlichen Unterschied machen.

freakC++ schrieb:

CStoll schrieb:

Beim Löschen geht man davon aus, daß du das zu löschende Listen-Element in der Hand hast - dann brauchst du nur noch den Vorgänger und Nachfolger zu greifen und miteinander zu verlinken. Bei der einfach verketteten Liste mußt du wieder von vorne anfangen, um den Vorgänger zu bestimmen....

Das verstehe ich nicht so richtig. Bei der einfach verketteten Liste iteriere ich solange durch die sortierte Liste bis ich beim gesuchten Element bin, das ich lösche. Was meinst Du mit "Vorgänger und Nachfolger [...] verlinken"?

Verkette Listen bestehen ja aus Einzelnen Elementen die irgendwo im Speicher verteilt liegen, und nicht wie in einem Array hintereinander sind. Wenn du in einer verketteten Liste löschst, musst du bei dem Vorgänger den Verweis von dem Aktuellen Element (das zu löschende) auf das nachfolgende umsetzen.

Bei einer doppelt verketteten Liste ist das insofern einfacher, da du den Zeiger auf den Vorgänger und Nachfolger bereits kennst (Ist ja im zu Löschenden Element vorhanden).

In einer einfach verketteten Liste musst du dir entweder beim durchiterieren den Vorgänger immer separat merken, oder gänzlich neu ermitteln (Da du nur einen Zeiger auf den Nachfolger, nicht aber auf den Vorgänger hast).

Skym0sh0

asc schrieb:

freakC++ schrieb:

CStoll schrieb:

Du kannst vom letzten Element anfangen und dich rückwärts durch die Liste durchhangeln, bis du am Ziel angekommen bist

Und was soll das bringen? Es ist doch gleichwertig, ob ich mich von vorne nach hinten oder von hinten nach vorne durchhangle.

Je nach dem wo das gesuchte Element liegt, kann das schon einen wesentlichen Unterschied machen.

pass auf: du ahst eine liste mit 10 elementen (der einfachheit halber mit den zahlen von 1 - 10) und du suchst:
- die 3: dann nimmst du dein sanfangs element und itererierst solange bis du die 3 findest (also 2 mal in dem fall)
- die 7: das gleibe wie bei der 3 aber du brauchst 6 iterrationen

bei mder doppelten verketteten liste, machst du das anders:
- bei der 3: du beginnst deine iterationen bei deinem start element und brauchst so wie oben 2 iterationen
- bfür die 7: du beginnst nicht am anfang sondern am ende und brauchst so dann auch nur 2 iterationen
----> folglich ist es schneller wenn du unterscheidest wo deine elemente liegen...

freakC++

Das leuchtet ein. Aber ich weiß doch gerade nicht, wo das Element liegt. Das ist doch die Problematik. Sonst könnte ich mir das Suchen doch sparen. Woher will ich denn wissen, dass die "7" am Ende liegt oder dass die "2" am Anfang ist. Wenn ich das natürlich wüsste, dann wäre es gut, wenn man den Weg entscheiden könnte. Ich müsste also über das größte und das kleinste Element bescheid wissen und dann auch wissen, wie viel dazwischen liegt. Leider habe ich diese Infos nicht, weswegen mir eure Erklärung doch nicht einleuchtet.

Viele Grüße
freakC++

ipsec

Sehr häufiger Fall: ans Ende der Liste ein Element anfügen. Dazu brauchst du das letzte Element. Bei einer doppelt verketteten Liste bekommst du das in O(1), bei einer einfach verketteteten nur in O(n).
Generell haben einfach verkettete Listen bei vielen häufigen Operationen (Einfügen am Ende, Löschen an beliebiger Position, etc.) ein schlechteres Komplexitätsverhalten als doppelt verkettete, während es nur wenige Fälle gibt, wo der Speicheroverhead der doppelt verketteten Liste wirklich relevant ist.

volkard

ipsec schrieb:

Sehr häufiger Fall: ans Ende der Liste ein Element anfügen. Dazu brauchst du das letzte Element. Bei einer doppelt verketteten Liste bekommst du das in O(1), bei einer einfach verketteteten nur in O(n).

Falsch.
Ja, ich weiß, daß viele Lehrbücher diese Aussage verzapfen.
Machen wir ins next-Feld des allerletzen Knotens einfach nicht NULL rein, sondern die Adresse des ersten Knotens. Und merken wir uns als Anker nicht den ersten Knoten, sondern den letzten. Nu kannste am Ende einfügen und am Anfang löschen in O(1).
Viola!

ipsec schrieb:

Generell haben einfach verkettete Listen bei vielen häufigen Operationen (Einfügen am Ende, Löschen an beliebiger Position, etc.) ein schlechteres Komplexitätsverhalten als doppelt verkettete,

Das halte ich für ein Gerücht.

ipsec

Ich meinte jetzt die einfach verketten Listen aus Lehrbüchern und der Uni-Vorlesung. Natürlich gibt es dann noch Tricks. Am Anfang in O(1) löschen ging übrigens auch schon vorher. Am Ende oder in der Mitte in O(1) löschen geht aber immer noch nicht. Und irgendeinen Grund hat es sicher, warum die Standardbibliothek keine einfach verkettete Liste anbietet.

GPC

volkard schrieb:

ipsec schrieb:

Sehr häufiger Fall: ans Ende der Liste ein Element anfügen. Dazu brauchst du das letzte Element. Bei einer doppelt verketteten Liste bekommst du das in O(1), bei einer einfach verketteteten nur in O(n).

Falsch.
Ja, ich weiß, daß viele Lehrbücher diese Aussage verzapfen.
Machen wir ins next-Feld des allerletzen Knotens einfach nicht NULL rein, sondern die Adresse des ersten Knotens. Und merken wir uns als Anker nicht den ersten Knoten, sondern den letzten. Nu kannste am Ende einfügen und am Anfang löschen in O(1).
Viola!

Aber dann haben wir eine zirkuläre und keine lineare verkettete Liste mehr (auch wenn die zirkuläre natürlich die coolere ist ). Man kann aber neben dem first-Zeiger auch noch einen last-Zeiger verwalten, um linear zu bleiben, aber nicht O(n) zum anhängen zu brauchen.

volkard

ipsec schrieb:

Ich meinte jetzt die einfach verketten Listen aus Lehrbüchern und der Uni-Vorlesung. Natürlich gibt es dann noch Tricks. Am Anfang in O(1) löschen ging übrigens auch schon vorher. Am Ende oder in der Mitte in O(1) löschen geht aber immer noch nicht.

Am Ende löschen geht prima, wenn man darauf verzichten kann, am Anfang zu löschen. Eine einfach verkettete Liste kann's halt nicht in beide Richtungen.

ipsec schrieb:

Und irgendeinen Grund hat es sicher, warum die Standardbibliothek keine einfach verkettete Liste anbietet.

Und wenn Gott gewollt hätte, daß der Mensch fliegt, hätte er ihm Flügel wachsen lassen.

ipsec

volkard schrieb:

ipsec schrieb:

Und irgendeinen Grund hat es sicher, warum die Standardbibliothek keine einfach verkettete Liste anbietet.

Und wenn Gott gewollt hätte, daß der Mensch fliegt, hätte er ihm Flügel wachsen lassen.

Brauchen wir nicht, er gab uns die Fähigkeit, Fluggeräte zu bauen. Zusammenhang zur Liste?

Der Grund bei der Standardbibliothek ist, dass in allen Fällen eine doppelt verkettete Liste einer einfach verketteten (oder von mir aus auch einer zirkulären) überlegen ist bzw. gleich gut wie diese ist (von der Algorithmenkomplexität her), bei dem einzigen Nachteil, dass es pro Element einen zusätzlichen Pointer Speicher braucht. Die Fälle, in denen es wirklich auf diese 4 oder 8 Byte ankommt, sind aber sehr gering.

volkard

ipsec schrieb:

volkard schrieb:

ipsec schrieb:

Und irgendeinen Grund hat es sicher, warum die Standardbibliothek keine einfach verkettete Liste anbietet.

Und wenn Gott gewollt hätte, daß der Mensch fliegt, hätte er ihm Flügel wachsen lassen.

Brauchen wir nicht, er gab uns die Fähigkeit, Fluggeräte zu bauen. Zusammenhang zur Liste?

Das Denkenlassen.

ipsec schrieb:

Der Grund bei der Standardbibliothek ist, dass in allen Fällen eine doppelt verkettete Liste einer einfach verketteten (oder von mir aus auch einer zirkulären) überlegen ist bzw. gleich gut wie diese ist (von der Algorithmenkomplexität her), bei dem einzigen Nachteil, dass es pro Element einen zusätzlichen Pointer Speicher braucht. Die Fälle, in denen es wirklich auf diese 4 oder 8 Byte ankommt, sind aber sehr gering.

Zu flach gedacht. Die einfach verkettete Liste als Stack und als Queue kann nur deswegen weggelassen werden, weil deque so unglaublich speichersparend UND schnell ist und für kleine Objekte jede verkettete Liste plattmacht. Für große Objekte kann eine verkettete Liste günstiger sein, aber wir reden hier von GROSS, und da machen der eine Zeiger mehr und das Bißchen Mehrzeit für mehr Umketten nichts mehr aus. Prinzipiell braucht die doppelt verkettete Liste mehr Zeit, weil sie zwei Zeiger zu setzen hat statt nur einem, außer natürlich man verlangt von ihr etwas, was nicht vorgesehen ist. Die std::list ist aber wohl eigentlich zum splicen da und für ein paar Zweckentfremdungen, die man allesamt hier im Forum bestaunen kann.

ipsec

volkard schrieb:

ipsec schrieb:

volkard schrieb:

ipsec schrieb:

Und irgendeinen Grund hat es sicher, warum die Standardbibliothek keine einfach verkettete Liste anbietet.

Und wenn Gott gewollt hätte, daß der Mensch fliegt, hätte er ihm Flügel wachsen lassen.

Brauchen wir nicht, er gab uns die Fähigkeit, Fluggeräte zu bauen. Zusammenhang zur Liste?

Das Denkenlassen.

Dein Argument (was meines in verfälschter Form ist) weitergeführt: die Standardbibliothek bietet keinen XML-Parser, also sollte kein C++-Programmierer XML-Dateien parsen.
Ich wollte darauf hinaus, dass die Standardbibliothek alle Arten von Containern mitliefert, aber eben keine einfach verkettete Liste (nur eine doppelt verkettete). Die Macher werden sich schon etwas dabei gedacht haben, warum sie diese nicht mit reingepackt haben, sie haben sie wohl nicht als etwas gesehen, dass jeder C++-Programmierer häufig braucht (bzw. aus anderen Gründen in den Standard aufgenommen werden sollte).

volkard

ipsec schrieb:

Ich wollte darauf hinaus, dass die Standardbibliothek alle Arten von Containern mitliefert, aber eben keine einfach verkettete Liste (nur eine doppelt verkettete). Die Macher werden sich schon etwas dabei gedacht haben, warum sie diese nicht mit reingepackt haben, sie haben sie wohl nicht als etwas gesehen, dass jeder C++-Programmierer häufig braucht (bzw. aus anderen Gründen in den Standard aufgenommen werden sollte).

Das ist doch kein Argument. Und schon gar nicht ein Nachweis dafür, daß die doppelt verkettete Liste schneller wäre.
Weshalb hatten sie kein Array und keine Hastable dabei? Zu Unwichtig? Oho, aber dann haben sie sich hochoffiziell geirrt.

CStoll

freakC++ schrieb:

CStoll schrieb:

freakC++ schrieb:

1.) Warum sind die Elemente schneller zu finden?

Du kannst vom letzten Element anfangen und dich rückwärts durch die Liste durchhangeln, bis du am Ziel angekommen bist

Und was soll das bringen? Es ist doch gleichwertig, ob ich mich von vorne nach hinten oder von hinten nach vorne durchhangle. Es würde nur etwas bringen, wenn ich von vorne UND von hinten gleichzeitig durch die Liste iterieren kann.

Das kommt ganz darauf an, was du als Ausgangspunkt hast. Bei der Suche nach einem Element, das eine bestimmte Bedingung erfüllt, macht es keinen Unterschied. Aber es ging mir darum, in der Liste z.B. das n-te Element zu holen.

PS: In C++0x soll es auch eine einfach verkettete Liste geben

freakC++

ipsec schrieb:

Sehr häufiger Fall: ans Ende der Liste ein Element anfügen. Dazu brauchst du das letzte Element. Bei einer doppelt verketteten Liste bekommst du das in O(1), bei einer einfach verketteteten nur in O(n).

Das leuchtet mir ein. Wobei ich könnte auch einfach das letzte Element abspeichern. Dann hab ich in O(1) das letzte Element einer einfach verketteten Liste.

Wenn ich aber etwas einfügen will, dann weiß ich nicht, ob ich hinten oder vorne anfangen soll durchzuiterieren. In meinen Augen stellt die doppelt verkettete Liste in dieser Hinsicht also keinen Vorteil dar.

Was ist der Vorteil einer zirkulären Liste? Nur, dass es kein Ende gibt. Beim Suchen, Einfügen, Löschen muss ich trotzdem in einer Richtung durchiterieren.

volkard

freakC++ schrieb:

Was ist der Vorteil einer zirkulären Liste? Nur, dass es kein Ende gibt. Beim Suchen, Einfügen, Löschen muss ich trotzdem in einer Richtung durchiterieren.

Falls man sich einen leeren Pseudoknoten leisten kann, hat man keine Fallunterscheidungen mehr im Code für push und pop. Kein if.

freakC++

Ich habe das nur in Delphi gemacht und da kann man durchaus in eine if Abfrage ein nil einbauen. Und in C++ funktioniert das auch:

#include <iostream>
using namespace std;

int main()
{
	int* a;
	if (a == NULL)
		cout << "Gib mir ne Adresse.";

	return 0;
}

Oder was meinst Du?

volkard

Ich meine

template<typename T>
class Ring{
   struct NodeBase{
      NodeBase* prev;
      NodeBase* pred;
   };
   struct Node:NodeBase{
      T data;
      NodeBase(T const& t)
      :data(t){
      }
   }
   NodeBase anchor;//Dieser Pseudoknoten existiert immer, daher ist der Ring immer geschlossen. 
   Ring(Ring const&);
   Ring& operator=(Ring const&);
prublic:
   Ring(){
      anchor->prev=&anchor;
      anchor->pred=anchor;
   }
   ~Ring(){
      while(!isEMpty())
         popBack();
   }
   bool isEmpty(){
      return anchor->prev=&anchor;
   }
   void pushBack(T const& t){
      Node* n=new Node(t);
      n->prev=&anchor;
      n->pred=anchor->pred;
      n->prev->pred=n;
      n->pred->prev=n;
   }
   void pushFront(T const& t){
      Node* n=new Node(t);
      n->pred=&anchor;
      n->prev=anchor->prev;
      n->prev->pred=n;
      n->pred->prev=n;
   }
   void popBack(){
      Node* n=anchor->pred;
      n->pred->prev=n->prev;
      n->prev->pred=n->pred;
      delete n;
   }
   void popFront(){
      Node* n=anchor->prev;
      n->pred->prev=n->prev;
      n->prev->pred=n->pred;
      delete n;
   }
};

Auf die lästigen Casts habe ich mal verzichtet.