Zeigerkonstruktion á la next->next

Hallo Leute,

ich zerbrech mit derzeit bezüglich der dynamischen Speicherverwaltung voll den Kopf und habe komme einfach nich weiter. Mein Problem ist folgendes:

ich möchte eine doppelt verkettete Liste erstellen. Ich habe mir bereits Grafiken angesehen, verstehe diese auch. Jetzt hab ich mir was in Pseudocode aufgeschrieben:

// Definiert eine doppelt verkettete Liste
Struktur liste {
 Zeichenkette name[30];
 liste* next; // nächstes Element
 liste* prev; // vorheriges Element
}

liste* anfang; // Listenanfang
liste* ende; // Listenende
liste* zeiger_vor; // zeigt („wandert“) auf nächstes Element
liste* zeiger_rück; // zeigt („wandert“) auf vorheriges Element

// Zeiger müssen vorher initialisiert werden
Funktion Init() {
 anfang = neu liste; // Speicher für Listenanfang reservieren
 ende    = neu liste; // Speicher für Listenende reservieren

 anfang = leer; // zu Anfang leer
 ende    = leer; // zu Anfang leer
}

// Elemente werden jetzt eingefügt
Funktion Einfügen(Zeichenkette n[30]) {
 zeiger_vor = anfang; // zeigt jetzt auf den Anfang der Liste (bisher leer)

 Solange zeiger_vor->next nicht leer ist {
  // next zeigt immer auf das nächste Listenelement
  zeiger_vor   = zeiger_vor->next;
 }
 // next ist leer
 zeiger_vor->next    = neu liste; // neues Element wird erzeugt
 ende                        = zeiger->next: // ende zeigt auf das aktuell letzte Element

 kopiere n nach zeiger_vor->name;

 zeiger_vor->next   = leer;
 zeiger_rück->prev = leer;
}

Wie man unschwer erkennen kann, sind bereits alle Zeiger vorhanden, die benötigt werden. Bei meiner Suche durch diverse Foren und Bücher (unglaublich, aber man findet echt null zu doppelten Listen bzw. so wenig, dass man damit nix anfangen kann) bin ich auf die Konstruktion zeiger->next->next gestossen. Angewendet auf meine Liste würde das dann so aussehen:

zeiger_vor->next->next

Nun will ich allerdings einfach nich begreifen, wofür man solch eine Konstruktion benötigt. Ich stelle mir das so vor:

Ich zeige auf ein Element, wofür noch kein Speicher reserviert wurde. Ergo: Speicherüberlauf, Programmabbruch etc.

Oder sehe ich das Ganze falsch bzw. gehe ich an die Geschichte falsch ran?

Hier nochmal ein Codeschnipsel (einfach verkettete Liste, is soweit für mich verständlich und nachvollziehbar):

#include <iostream>

using namespace std;

// Definition des Typs für die Elemente der Liste als Struktur
struct listenelement {
 char daten[10];
 listenelement* next; // vorwärts
 listenelement* last; // rückwärts
};

// Zeiger auf Anfang der Liste
listenelement* listenanfang;

// Zeiger auf Ende der Liste
listenelement* listenende;

// Hilfszeiger, um in der Liste "vorwärts wandern" zu können
listenelement* hilfszeiger;

// Hilfszeiger, um in der Liste "rückwärts wandern" zu können
listenelement* hilfszeiger_rueck;

// Initialisieren der Liste
void init() {
 // erstes Element erzeugen
 listenanfang = new(listenelement);
 listenende   = new(listenelement);
 // Daten in das erste Element schreiben
 listenanfang->next   = NULL;
 listenanfang->last   = NULL;
 strcpy(listenanfang->daten, "Element 0");
}

// Funktion zum Einfügen von Elementen in die Liste
void einfuegen(char datenneu[30]) {
 // Hilfszeiger an den Anfang der Liste setzen
 hilfszeiger = listenanfang;

 // Durch die Liste gehen, bis das letzte Element erreicht ist
 while(hilfszeiger->next != NULL) {
  hilfszeiger = hilfszeiger->next;
 }

 // neues Element in die Liste einfügen
 hilfszeiger->next = new(listenelement);

 // Hilfszeiger auf das neue Element setzen
 hilfszeiger = hilfszeiger->next;

 // listenende erhält das aktuelle (letzte) Element
 listenende = hilfszeiger;

 // Daten im neuen Element eintragen
 strcpy(hilfszeiger->daten, datenneu);

 hilfszeiger->next = NULL;
}

// Alle Elemente der Liste ausgeben
void ausgeben() {
 // hilfszeiger auf den Anfang der Liste setzen
 hilfszeiger = listenanfang;

 // erstes Element ausgeben
 cout << hilfszeiger->daten << '\n';

 // Solange das Ende noch nicht erreicht ist:
 while(hilfszeiger->next != NULL) {
  // hilfszeiger auf nächstes Element setzen
  hilfszeiger = hilfszeiger->next;
  // Daten ausgeben
  cout << hilfszeiger->daten << '\n';
 }
}

Einige Anmerkungen dazu: Mir ist bewusst, dass dies mit Hilfe von Templates sehr viel schneller und eleganter gelöst werden kann. Nur erfordert die Aufgabe nunmal die Programmierung einer doppelt verketteten Liste (kleine Info: Ich mach grad ne Weiterbildung in C++-Programmierung). Demzufolge fehlen jetzt auch Klassen und andere Vorteile der OOP.

Ich hoffe, ihr könnt mir einen kleinen Denkanstoß geben, wie ich eine doppelt verkettete Liste realisieren kann bzw. was es mit zeiger->next->next auf sich hat.

Vielen Dank hierfür.

Gugi

Mh, ich weis leider nicht so ganz, was eigtl. dein Problem ist... weist du nicht, was eine doppelt verkettete Liste ist, oder wozu sie gut ist? Oder kommt beim kompilieren ein Fehler?

Naja, egal, aufjedenfall: Eine doppelt verkettete Liste hat den Vorteil, dass man die Kette rückwärts und vorwärts durchlaufen kann (indem man den Zeigern folgt, die die einzelnen Knoten verbinden).
Das bedeutet, dass bestimmte Optimierungen möglich sind z.B., da man auch hinten bei der Liste beginnen kann.
Übrigens nennt man ein Element einer solchen Liste Knoten (also ist eigtl. deine struktur-Bezeichnung falsch).
Einfach verkettete Liste: y --> x --> x --> x --> x --> z
Doppelt verkettete Liste: y <--> x <--> x <--> x <--> x <--> z
y ist der Kettenanfang (oft auch vom Typ x), z das letzte Element der Liste (auch oft einfach x).

Ich würde deinen Pseudocode so schreiben (eigtl. nicht, ich würde alles in eine Klasse kapseln^^):

// Definiert einen Knoten der doppelt verketteten Liste
Struktur Knoten {
 Zeichenkette name[30];
 Knoten* next; // nächstes Element
 Knoten* prev; // vorheriges Element
}

Knoten* anfang; // Listenanfang
Knoten* ende; // Listenende

// Zeiger müssen vorher initialisiert werden, damit sie nicht zufällig wohin zeigen.
Funktion Init() 
{
 anfang = NULL; // zu Anfang leer
 ende   = NULL; // zu Anfang leer
}

// Elemente werden jetzt eingefügt
Funktion Einfügen(Zeichenkette n[30]) 
{
 Knoten* zeiger_vor = anfang; // Beginne am Anfang der Liste

 Wenn zeiger_vor leer (d.h. NULL) ist
 {
   // Erstelle neuen Anfang
   zeiger_vor = neu Knoten; 
   zeiger_vor->next = NULL;
   zeiger_vor->prev = NULL;
   anfang = ende = zeiger_vor;
 }
 ansonsten
 {
  Solange zeiger_vor->next nicht leer ist 
  {
   // next zeigt immer auf das nächste Listenelement
   zeiger_vor   = zeiger_vor->next;
  }
  // next ist leer. Erstelle einen neuen Knoten in zeiger_vor->next.
  zeiger_vor->next = neu Knoten; // neues Element wird erzeugt
  zeiger_vor->next->next = NULL; // Muss leer sein, damit man weis, dass es hier nicht weitergeht.
  zeiger_vor->next->prev = zeiger_vor; // Verknüpfe den neuen Knoten mit dem vorherigen Knoten.
  ende = zeiger_vor->next: // ende zeigt auf das aktuell letzte Element
 }

 kopiere n nach zeiger_vor->next->name;
}

zeiger_vor und zeiger_rück sind doch eigtl. hier nur Hilfsvariablen, um die Liste zu durchlaufen. Darum denke ich sind sie besser als lokale Variablen aufgehoben (zumal zeiger_vor in der Einfügen Funktion immer wieder auf den Anfag zeigt und zeiger_zurück nichts macht).

Die struktur "liste", bzw. bei mir "Knoten" ist ja ein Element der Liste, das die eigtl. Daten enthält (hier eine Zeichenkette). Warum erstellst du dann davon 2 am Anfang? Initialisiere doch einfach die beiden Zeiger mit NULL.

Die Datenelemente des neu erstellten Objekts müssen auch initialisiert werden, und seis auch nur, damit sie nicht zufällig irgendwelche Daten beinhalten.

Weiterhin würde "kopiere n nach zeiger_vor->name;" nicht den Namen des neuen Elements aktualisieren (sondern den des alten), da das neue Element ja in zeiger_vor->next ist.

zeiger_vor->next->next
Kann schon sein, dass man so etwas mal braucht. Z.B. in dem Pseudocode benutzte ich es, um das 2. next mit NULL zu initialisieren.
Oder man muss mal schauen, ob es NULL ist oder nicht, und dementsprechend reagieren (z.b. vorwärts gehen in der Liste, oder so).

Der Knoten mit einem bestimmten Namen kann z.b. dann so rausgefunden werden:

Knoten* HoleKnoten(Name des Knoten NDK)
{
  Wenn anfang == NULL
    Gebe NULL zurück.

  Knoten* AktuellerKnoten = anfang;

  Solange AktuellerKnoten != NULL
  {
    Wenn (AktuellerKnoten->name gleich NDK ist)
      Gebe AktuellerKnoten zurück;
  }

  // Nichts gefunden --> gebe NULL zurück.
  Gebe NULL zurück.
}

ich probiers mal aus und sende mein Ergebnis dann...auf jeden Fall sind die Dinge, die du aufgezählt hast - also was man besser machen könnte - richtig....leider erfordert es die Aufgabenstellung so (ich persönlich würde es auch anders machen ;))

Ich versteh jetzt aber immer noch nicht, was das mit zeiger->next->next bzw. zeiger->next->prev soll...Vielleicht kannst du mir das nochmal genauer erklären

Gugi

naja, du benutzt ja eine Struktur für die Knoten, die die Membervariablen nicht selber mit NULL initialisiert, d.h. sie können irgendetwas enthalten (halt das, was zufällig an der Stelle im Speicher stand).

Das bedeutet, dass man beide Zeiger (prev und next) intialisieren sollte, bzw. hier auch muss.
"Muss" deshalb, weil in der Einfüge und der HoleKnoten Funktion überprüft wird, ob der nächste Knoten in der Liste gleich NULL ist, also ob er vorhanden ist. Wenn der Zeiger aber nicht initialisiert wurde, kann da irgendetwas stehen (0x0, 0x321e3564,...).

Der Ausdruck "zeiger_vor->next->next" kann manchmal nötig sein. Wenn die Liste 5 Knoten hat, dann ist auch folgendes vollkommen erlaubt:

anfang->next->next->next->next->name[0] = '\0';

Nur muss man halt sicher sein, dass die Liste wirklich so lang ist.
Aber so etwas ist eh nicht zu empfehlen, da keiner mehr nach 1 Woche weis, was das jetzt genau bedeutet (was ist das 5 next??).

In meiner Einfüge Funktion wird ein neues Objekt auf dem Heap erstellt und dessen Adresse wird in "zeiger_vor->next"gespeichert, d.h. dieser "next" Zeiger zeigt auf das Objekt auf dem Heap.
So, d.h. zeiger_vor->next ist jetzt definiert (erm, halt ungleich NULL).
Als das Objekt auf dem Heap erstellt wurde, wurden allerdings die Membervariablen des neuen Objekts noch nicht initialisiert, was nun noch geschehen muss.

zeiger_vor->next->next = NULL;

Das initialisiert den next Zeiger des neuen Objekts.

zeiger_vor->next->prev = zeiger_vor;

Das initialisiert den prev Zeiger des neuen Objekts, und zwar mit der Addresse des vorhergehenden Objekts, also zeiger_vor.

Oder, um es besser leserlich zu schreiben:

Knoten* NeuerKnoten = new Knoten();
zeiger_vor->next = NeuerKnoten;
NeuerKnoten->next = NULL;
NeuerKnoten->prev = zeiger_vor;

Durch das setzten von zeiger_vor->next und NeuerKnoten->prev wird die Verbindung zwischen beiden Objekten hergestellt, die das navigieren in der Liste ermöglicht.

Ich denke, ich verstehe was du meinst..........Ich fass mal zusammen:

eine Konstruktion wie zeiger->next->next=NULL bedeutet, dass das nächste Element NACH dem nächsten Element (sozusagen das übernächste) Element gleich NULL ist...
Das bedeutet aber auch, dass zeiger->next bereits einen Wert erhalten haben muss, sonst sollte es zu einem Speicherüberlauf, Programmabsturz etc. kommen, richtig?...

bei einer doppelten Liste könnte man jetzt auch sagen zeiger->next->prev...Das heißt dann, dass das nächste Element gleichzeitig im prev-Zeiger gespeichert wird...

Ich hoffe, ich habs jetzt richtig wiedergegeben....

queer_boy

? prev steht für previous und bezeichnet das vorherige element in der liste.
element->next->prev ist also gleich bedeutend mit "das element, das vor dem nächsten element liegt" und bezeichnet damit "element" selbst.
/edit: doppelt verkettet heißt nicht, dass dieselbe information zweimal gespeichert ist, sondern dass die liste "nach vorne und nach hinten" verkettet ist.

dust

"Speicherüberlauf, Programmabsturz" - nix Overflow, damit hat es nichts zu tun. Sowas nennt man NULLPOINTERDURCHGRIFF (punch-through) und führt zu unvorhersehbaren Ergebnissen (Schutzverletzung, Absturz, im besten Fall flasche Ergebnisse/keine Auswirkung)

hustbaer

Also den Begriff "punch-through" hab ich in dem Zusammenhang noch nie gehört...
Ich sag mal ich halte das für ein Gerücht dass das eine übliche Bezeichnung für das Dereferenzieren eines ungültigen Pointers bzw. Null-Pointers ist.

NULLPOINTERDURCHGRIFF ist im Übrigen ein Wort welches du wohl gerade erfunden haben wirst. Zumindest Google findet dazu keine einzige Seite. Auch nicht für "NULLPOINTER DURCHGRIFF" oder "NULL POINTER DURCHGRIFF".

dust

Das ist mir auch aufgefallen, aber unser Prof. benutzt es immerzu, und der ist Experte, außerdem klingt es auch logisch.

Wie auch immer, jedenfalls handelt es sich nicht um einen Überlauf, sondern wie gesagt um Dereferenzierung eines NULLPOINTERs, wie auch immer man das nennen mag.

"Speicherüberlauf, Programmabsturz" - nix Overflow, damit hat es nichts zu tun. Sowas nennt man NULLPOINTERDURCHGRIFF (punch-through) und führt zu unvorhersehbaren Ergebnissen (Schutzverletzung, Absturz, im besten Fall flasche Ergebnisse/keine Auswirkung)

@dust:Kann ja sein, dass ich mich irre, aber hast du hier nicht grad dasselbe wie ich geschrieben?

dust

Nein, ich habe dir mitgeteilt, dass es KEINEN overflow gibt, wenn man einen Zeiger dereferenziert, der ins Nirvana zeigt. Und ich habe geäußert wie man sowas wohl nennt (zumindest unser Prof. für Datenstrukturen^^), der müsstes ja eigentlich wissen.

Is ja nich so wichtig........Auf jeden Fall meinen wir beide das Gleiche....ich habe mich da wohl etwas falsch ausgedrückt.....

Um nochmal auf mein Problem zurückzukommen: Ich habe das mit zeiger_vor->next->last mal ausprobiert.........wenn ich das so ausführe, erhalte ich einen Speicherzugriffsfehler, sprich, es geht nicht weiter....

Wenn ich allerdings sage zeiger_vor->last ist wieder alles in Ordnung....Hier nochmal der Quelltext zum Vergleich (nur Einfüge-Funktion):

void einfuegen(char datenneu[30]) {
 // Hilfszeiger an den Anfang der Liste setzen
 hilfszeiger = listenanfang;

 // Durch die Liste gehen, bis das letzte Element erreicht ist
 while(hilfszeiger->next != NULL) {
  hilfszeiger = hilfszeiger->next;
  hilfszeiger->last = hilfszeiger; // Verknüpfe das neuen Element mit dem Vorherigen
 }

 // neues Element in die Liste einfügen
 hilfszeiger->next = new(listenelement);

 // Hilfszeiger auf das neue Element setzen
 hilfszeiger = hilfszeiger->next;

 // listenende erhält das aktuelle (letzte) Element
 listenende = hilfszeiger;

 // Daten im neuen Element eintragen
 strcpy(hilfszeiger->daten, datenneu);

 hilfszeiger->next = NULL;
 hilfszeiger->last = NULL;
}

wie man gut sehen kann, hab ich lediglich die Zeiger anders verbunden...Dennoch führt das nicht zum gewünschten Ergebnis, die Elemente rückwärts auszugeben...

Meine Ausgabefunktion:

// Elemente rückwärts ausgeben
void ausgaberueckwaerts() {
 hilfszeiger_rueck = listenende;

 cout << hilfszeiger_rueck->daten << '\n';

 // Durch die Liste gehen, bis das erste Element erreicht ist
 while(hilfszeiger_rueck->last != NULL) {
  hilfszeiger_rueck = hilfszeiger->last;

  cout << hilfszeiger_rueck->daten << '\n';
 }
}

Jetzt wird vielleicht verständlich, wofür ich hilfszeiger_rueck bzw. zeiger_rück benötige

Gugi

Ich glaube du hast immer noch nicht so ganz das Prinzip von eine doppelt verketteten Liste verstanden.

Ich kommentiere mal deinen Code:

void einfuegen(char datenneu[30]) 
{
 //-->Warum muss hilfszeiger global sein? Wäre besser, ihn lokal zu halten
 //--> Außerdem: listenanfang kann doch NULL sein, oder nicht? Das bedeutet, dass "hilfszeiger->next" nach der Schleife einen Fehler auslöst, weil ja hilfszeiger NULL ist.
 // Hilfszeiger an den Anfang der Liste setzen
 hilfszeiger = listenanfang;

 // Durch die Liste gehen, bis das letzte Element erreicht ist
 while(hilfszeiger->next != NULL) 
 {
  hilfszeiger = hilfszeiger->next;

// -->Das hier ist völliger Schwachsinn^^. last zeigt jetzt auf hilfszeiger, d.h. auf das eigene Objekt (last == this, wenn man sich im Objekt befinden würde).
  hilfszeiger->last = hilfszeiger; // Verknüpfe das neuen Element mit dem Vorherigen
 }

 // neues Element in die Liste einfügen
 hilfszeiger->next = new(listenelement);

 // Hilfszeiger auf das neue Element setzen
 hilfszeiger = hilfszeiger->next;

 // listenende erhält das aktuelle (letzte) Element
 listenende = hilfszeiger;

 // Daten im neuen Element eintragen
 strcpy(hilfszeiger->daten, datenneu);

 // -->Erm, hilfszeiger zeigt auf das neue Objekt. Warum setzt du last im neuen Objekt auf NULL? Das bedeutet, dass das Objekt zum vorherigen Objekt nicht verknüpft ist.
 hilfszeiger->next = NULL;
 hilfszeiger->last = NULL;
}

In deiner Ausgabefunktion kann ich auch keinen Grund erkennen, warum hilfszeiger_rueck global sein sollte.

Also, um nochmal zu der Theorie von verketteten Listen zurückzukommen:
Eine verkettete Liste wird oft als erschaffen, wenn man ein dynamisches array benötigt.
Eine verkettete Liste besteht aus Objekten, die miteinander (über Zeiger) verbunden sind.
x1 -> x2 -> x3 -> NULL
x1 ist mit x2 verbunden, dass heißt wenn man dem zeiger folgt, erhält man x2.
Wenn es nicht weitergeht, wird der Zeiger normalerweise auf NULL gesetzt.

Das eben war eine einfach verkettete Liste. Eine doppelt verkettete Liste ist eigtl. auch nichts anderes, also eine Reihe von Objekten, die miteinander verknüpt werden. Allerdings kann man sich in einer doppelt verketteten Liste nicht nur vorwärts, sondern auch rückwärts bewegen.
NULL <- x1 <-> x2 <-> x3 -> NULL
Man kann jetzt z.b. bei x1 beginnen und auf x2 kommen, oder man beginnt bei x3 und folgt dem rückwärts-Zeiger, um auf x2 zu kommen.

Um es mal bildlich zu beschreiben: Stell mehrere Räume vor, die mit Türen verbunden sind.
- Einfach verkettete Liste: Die Türen kann man nur von einer Seite öffnen, d.h. man kann beim ersten Raum anfangen und somit bis zum letzten Raum gelangen. Allerdings kommt man nicht wieder zurück, man muss "ausenrum" gehen und wieder am Anfang anfangen.
- Doppelt v. L.: Die Türen gehen von beiden Seiten auf. D.h. man kann die Räume auch in umgekehrter Reihenfolge durchlaufen, oder in der Mitter einfach umdrehen.

Die Räume sind die Objekte.
Eine Tür, die nur von einer Seite aufgeht (d.h. nur 1 Türklinke hat), ist 1 Zeiger.
Eine Tür, die von beiden Seiten aufgeht (d.h. sie hat beidseitig je 1 Türklinke), repräsentiert 2 Zeiger.

hustbaer

dust schrieb:

Das ist mir auch aufgefallen, aber unser Prof. benutzt es immerzu, und der ist Experte, außerdem klingt es auch logisch.

Rofl.
"Ja, er ist der einzige der das so nennt, aber er ist Experte"

Dein Professor hält sich wohl für schlau. Ich halte ihn nicht für schlau.

dust

lol, und ich halte deine omma für schlau ... es interessiert keinen ... nur weil man was nicht bei google findet, heißt es noch längst nicht, dass es das nicht gibt ... v.a. bei zusammengesetzen Wörtern (das man durch Pointer durchgreift ist doch wohl allgemein bekannt (findest du auch bei google), und wenn man durch einen Nullpointer druchgreift, dann ist das eben ein NULLPOINTERDURCHGRIFF .. was ist da so schwer dran zu raffen, das Wort "Tomatenventilator" findest du bei google auch nicht, aber es ist dochwohl denkbar, dass man einen Ventilator, der wie eine Tomate aussieht so nennt) ... und jetzt Schluss mit dem Gespamme!

queer_boy

du unterhältst dich hier mit leuten, die teilweise schon deutlich länger und professioneller (z.b. beruflich) programmieren als du, und vielleicht sogar dein professor? das ist zwar eine schöne metapher, "durch" einen zeiger "durchzugreifen", aber wenn du dich einmal mit anderen leuten unterhalten willst, die programmieren, wirst du damit weniger weit kommen, als wenn du sagen würdest, du greifs mit einem zeiger auf etwas zu. und wenn du einmal hilfe per google suchst, dann wirst du mit der kombination zeiger und zugriff auch deutlich mehr treffer haben, als mit zeiger und "durchgriff". "nullpointerzugriff" sagt man aber IMO auch nicht unbedingt. der richtige begriff wäre das "dereferenzieren eines nullzeigers". einen zeiger dereferenziert man, man greift nicht durch.

von daher lässt sich viel eher sagen: es interessiert keinen, dass du das nullpointerdurchgriff nennst. sei also lieber froh, dass du an dieser stelle darauf hingewiesen wirst, dass man das nicht so sagt, anstatt dich über die vermeintliche inkompetenz hier aufzuregen. sprich lieber deinen prof darauf an.

Schön zu sehen, wie sehr ihr euch über das Dereferenzieren von Zeigern aufregt :D...

@Gugi: Also von der Theorie her isses ja nich schwer nachzuvollziehen...das begreife ich ja........vermutlich versteif ich mich da in irgendetwas....

Ich merke, ich muss wohl mal den gesamten Code posten, damit Ihr seht, warum die Zeiger global und nicht lokal sind.....

Also nochmal:

/*##########################
     Einsendeaufgabe 5.2
  ##########################*/
#include <iostream>

using namespace std;

// Definition des Typs für die Elemente der Liste als Struktur
struct listenelement {
 char daten[10];
 listenelement* next; // vorwärts
 listenelement* last; // rückwärts
};

// Zeiger auf Anfang der Liste
listenelement* listenanfang;

// Zeiger auf Ende der Liste
listenelement* listenende;

// Hilfszeiger, um in der Liste "vorwärts wandern" zu können
listenelement* hilfszeiger;

// Hilfszeiger, um in der Liste "rückwärts wandern" zu können
listenelement* hilfszeiger_rueck;

// Funktion zum Einfügen von Elementen in die Liste
void einfuegen(char datenneu[30]) {
 // Hilfszeiger an den Anfang der Liste setzen
 hilfszeiger = listenanfang;
 hilfszeiger_rueck = NULL;

 // Durch die Liste gehen, bis das letzte Element erreicht ist
 while(hilfszeiger->next != NULL) {
  hilfszeiger = hilfszeiger->next;
  hilfszeiger_rueck->last = hilfszeiger; // Verknüpfe das neue Element mit dem Vorherigen
 }

 // neues Element in die Liste einfügen
 hilfszeiger->next = new(listenelement);

 // Hilfszeiger auf das neue Element setzen
 hilfszeiger = hilfszeiger->next;

 // listenende erhält das aktuelle (letzte) Element
 listenende = hilfszeiger;

 // Daten im neuen Element eintragen
 strcpy(hilfszeiger->daten, datenneu);

 hilfszeiger->next = NULL;
 hilfszeiger_rueck->last = NULL;
}

// Alle Elemente der Liste ausgeben
void ausgeben() {
 // hilfszeiger auf den Anfang der Liste setzen
 hilfszeiger = listenanfang;

 // erstes Element ausgeben
 cout << hilfszeiger->daten << '\n';

 // Solange das Ende noch nicht erreicht ist:
 while(hilfszeiger->next != NULL) {
  // hilfszeiger auf nächstes Element setzen
  hilfszeiger = hilfszeiger->next;
  // Daten ausgeben
  cout << hilfszeiger->daten << '\n';
 }
}

// Initialisieren der Liste
void init() {
 // erstes Element erzeugen
 listenanfang = new(listenelement);

 // Daten in das erste Element schreiben
 listenanfang->next   = NULL;
 listenanfang->last   = NULL;
 strcpy(listenanfang->daten, "Element 0");
}

// Liste leeren und Speicher freigeben
void ende() {
 // Solange noch Elemente in der Liste sind
 while(listenanfang != NULL) {
  // hilfszeiger auf das erste Element der Liste
  hilfszeiger = listenanfang;

  // Zeiger für den Listenanfang auf das nächste Element setzen
  listenanfang = listenanfang->next;

  // Das herausgenommene Element löschen
  delete(hilfszeiger);
 }
}

// Elemente rückwärts ausgeben
void ausgaberueckwaerts() {
 hilfszeiger_rueck = listenende;

 cout << hilfszeiger_rueck->daten << '\n';

 // Durch die Liste gehen, bis das erste Element erreicht ist
 while(hilfszeiger_rueck->last != NULL) {
  hilfszeiger_rueck = hilfszeiger_rueck->last;

  cout << hilfszeiger_rueck->daten << '\n';
 }
}

int main() {
 init();
 einfuegen("Element 1");
 einfuegen("Element 2");
 einfuegen("Element 3");
 ausgeben();
 ausgaberueckwaerts();
 ende();

 return 0;
}

camper

unwichtig schrieb:

Ich merke, ich muss wohl mal den gesamten Code posten, damit Ihr seht, warum die Zeiger global und nicht lokal sind.....

Das ist allerdings daraus nicht zu erkennen. Überflüssig und störend (störend deshalb, weil es den Lesefluss unterbricht) sind zunächst einmal die Kommentare - die sagen nur, was der Code macht. Das geht aber aus ihm selbst hervor. Was dem Code nicht zu entnehmen ist und Gegenstand der Kommentare sein müsste, ist das warum eines bestimmten Konstrukts (und in Fällen, in denen das selbstevident ist, heißt das eben: nicht kommentieren).

Was die eigentliche Implementation angeht, stelle ich fest, dass weder listenende noch hilfszeiger_rueck noch last wirklich (jedenfalls nicht systematisch und konsequent) verwendet werden: damit ist das
a) keine doppelt verkette Liste, und
b) der Grund für ihre Existenz gerade nicht dem Code zu entnehmen und noch weniger, weshalb diese nun global sein müssen.

Könnt ich denn theoretisch auch nur einen "hilfszeiger" nutzen? Ist sowas möglich?

das dürfte ja nicht funktionieren oder?

Zeigerkonstruktion á la next-&gt;next

Zeigerkonstruktion á la next->next