Doppelt verkettete lineare Liste

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.

volkard

freakC++ schrieb:

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:

Ja, aber ich will kein if haben. Da muß ich so viel nachdenken dabei. Und der Prozessor muß eine Sprungvorhersage wagen. Gefällt mich nicht.

void pushBack(T const& t){
      Node* n=new Node(t);
      if(first==NULL){//ganz leer
         first=n;
         last=n;
         n->prev=0;
         n->pred=0;
      }
      else{
         n->prev=last;
         n->pred=0;
         last=n;
      }
}