Doppelt verkettete Liste

[WinDWalker]

Hallo,;-)

Vorab erst mal, ich weiss dass es zig Möglichkeiten gibt verkettete Listen zu bauen, selbstverständlich auch nur mit Klassen als Container usw. mir geht es aber hier ums Verständnis der hier benutzten Art von verketteten Listen.
Das Problem ist wahrscheinlich sehr gering aber ich dreh mich schon seit Tagen um mich selbst und find den Bug nicht!

Was Funktioniert:
1. Die Liste wird korrekt angelegt und ausgegeben auch die Anzahl der Elemente.
2. Das neue erste Element wird korrekt angelegt und die Liste wird ebenso korrekt ausgegeben auch die Anzahl der Elemente.


Was nicht funktioniert:
Das neue letzte Element wird wahrscheinlich nicht richtig angelegt und deshalb wird das letzte Element nicht ausgegeben wenn die Liste ausgegeben wird.

Wird jedoch der obere Teil in der Funktion addNewLastElement(int wert) einkommentiert,
in diesem Teil füge ich das letzte Element wie bei einer einfach verketteten Liste ein dann funktioniert alles.

Ich gehe übrigens davon aus dass sich schon ein Element in der Liste befindet (keine Plausibilitätsprüfung) da ich die Liste ja zuvor erstellt habe.
Ich habe versucht alles so gut und so verständlich wie möglich zu kommentieren.

Hier der Code für die main():

#include "List.h"

void main()
{
	mvList mvListe;
	int i;
	int j = 1;
	

	cout << "Liste ist leer  ==> Liste mit 3 Elementen bauen" << endl;
	
	for (i = 0; i < 3; i++)
	{
		mvListe.addElement(j++);
	}
	mvListe.showElements();
	

	cout << "Neues Erstes Element einfuegen" << endl;
	mvListe.addElement(5, FIRST);
	mvListe.showElements();
	
	cout << "Neues letztes Element einfuegen" << endl;
	mvListe.addElement(10, LAST);
	mvListe.showElements();
	
}

Hier der Code für die List.h:

#include <iostream>
using namespace std;

enum { NONE = 0,FIRST, LAST, MIDDLE };

class mvList
{
private:

//*************************************** SRTUCT ERSTELLEN *************************************
	struct Listenknoten
	{
		int data;
		Listenknoten *next;
		Listenknoten *prev;
	};

public:
//******************************* ZEIGER AUF STRUCT ERSTELLLEN *********************************
	Listenknoten *neu;
	Listenknoten *head;
	Listenknoten *tail;
	Listenknoten *current1;
	Listenknoten *current2;
	int			  counterElements;

//********************************** KONSTRUKTOR / DESTRUKTOR **********************************
	mvList()
	{
		neu				=	NULL; // Zeiger mit Null initialisieren
		head			=	NULL; // Zeiger mit Null initialisieren
		tail			=	NULL; // Zeiger mit Null initialisieren
		current1		=	NULL; // Zeiger mit Null initialisieren
		current2		=	NULL; // Zeiger mit Null initialisieren
		counterElements =	0;
	}

	~mvList()
	{
		neu				=	NULL; // Zeiger mit Null initialisieren
		head			=	NULL; // Zeiger mit Null initialisieren
		tail			=	NULL; // Zeiger mit Null initialisieren
		current1		=	NULL; // Zeiger mit Null initialisieren
		current2		=	NULL; // Zeiger mit Null initialisieren

		delete neu;			
		delete head;			
		delete tail;			
		delete current1;		
		delete current2;			 
	}


//******************************* PROTOS DER MEMBERFUNKTIONEN **********************************
	void showElements();
	
	void addElement(int wert, int , int);
	void addNewFirstElement(int wert);
	void addNewLastElement(int wert);
	void addNewMiddleElement(int wert, int atPosition);
};


//**********************************************************************************************
//******************************* ENTSCHEIDUNG FUNKTIONAUFRUFE *********************************

void mvList::addElement(int wert, int atPos = NONE, int pos = 0)
{
	if (atPos != NONE)
	{
		switch(atPos)
		{
		case FIRST:	addNewFirstElement(wert);
			break;
		case LAST:	addNewLastElement(wert);
			break;
		default:
		    break;
		}
	}else
	{
		addNewFirstElement(wert);
	}
}
//**********************************************************************************************
//****************************** NEUES ERSTES ELEMENT EINFÜGEN *********************************

void mvList::addNewFirstElement(int wert)
{
	neu = new Listenknoten;

	neu->prev = NULL;
	neu->next = head;
	head = neu;
 
	neu->data = wert;

	counterElements++;
	cout << "Elemente: "  << counterElements;
}


//**********************************************************************************************
//************************* NEUES LETZTES ELEMENT EINFUEGEN INSERT AFTER ***********************

void mvList::addNewLastElement(int wert)
{

	neu = new Listenknoten;			
// 
// 
// 	current1 = head;					// einkommentieren
// 	while (current1->next != NULL)		// einkommentieren
// 	{									// einkommentieren
// 		current1 = current1->next;		// einkommentieren
// 	}									// einkommentieren
// 	neu->next = NULL;					// einkommentieren
// 										// einkommentieren
// 	current1->next = neu;				// einkommentieren
//										// einkommentieren
// 	neu->data = wert;					// einkommentieren	
	
	

	neu->next = NULL;					// auskommentieren	
	neu->prev = tail;					// auskommentieren
	
	tail = neu;							// auskommentieren
 
	neu->data = wert;					// auskommentieren
	
	counterElements++;
	cout << "Elemente: " << counterElements;
}

Vorab schon mal vielen Dank für eure Mühe
WindWalker

 

[Thomas Kuse]

Dir fehlen wohl zwei prev-Zeiger :

	neu->prev = NULL;
	neu->next = head;
	head->prev=neu;//fehlt bisher
	head = neu;

	neu->next = NULL;					// auskommentieren	
	neu->prev = tail;					// auskommentieren
	tail->next=neu;//fehlt bisher
	tail = neu;							// auskommentieren
	neu->data = wert;					// auskommentieren

Ausserdem bewirkt Dein Destruktor überhaupt nix!
Das NULL-Setzen der Zeigeradressen kannst Du Dir wirklich sparen, das bewirkt nur, dass der Speicher an den eigentlichen Adressen beim delete nicht gelöscht wird

 

[Martin Schroeder]

Ausserdem bewirkt Dein Destruktor überhaupt nix!
Das NULL-Setzen der Zeigeradressen kannst Du Dir wirklich sparen, das bewirkt nur, dass der Speicher an den eigentlichen Adressen beim delete nicht gelöscht wird

Ich würde sogar sagen, das Programm stürzt noch auf den letzten Drücker ab...
Wenn überhaupt, dann setzt man die Zeiger nach dem delete auf NULL.
Aber in einen Destruktor ist das sinnlos, da danach sowieso die Zeiger nicht mehr existieren und also auch nicht mehr auf freigegebene Speicherbereiche zeigen können.

 

[Thomas Kuse]

Ja stimmt!

Ansonsten muss es natürlich heissen:

if(head)head->prev = neu;
...
if(tail)tail->next = neu;

Dann klappt auch alles.

 

[deepthroat]

Hi.

Ich würde sogar sagen, das Programm stürzt noch auf den letzten Drücker ab...

Nein. In C++ ist das Löschen eines Nullzeigers mit delete bzw. delete[] eine sichere Operation - wenn auch völlig sinnfrei.

Allerdings wird der Speicher natürlich nicht ordentlich freigegeben, weil ja die entsprechenden Zeiger einfach auf 0 gesetzt werden.

Gruß

 

[Martin Schroeder]

Echt?
Das wusste ich noch garnicht
Dann kann man sich ja die Abfrage im Destruktor sparen, ob überhaupt Speicher reserviert wurde, wenn man Zeiger NULL-initialisiert.
Cool