C++ Probleme bei Implementierung von verketteter Liste

[Esteba]

Ich bin eigentlich Java gewohnt und in C++ noch relativ unerfahren. Ich versuche gerade, in C++ eine einfach verkettete Liste zu implementieren, ganz simpel. Dazu habe ich eine Klasse MyList erstellt, die die Attribute "head" und "tail" aufweist, wobei es sich bei ersterem um ein Listenelement (Typ wstring) und bei letzterem um die referenzierte Restliste handelt.

class MyList {

	public:
		bool isEmpty();
		void shift(wstring newElement);
		void printElements();

	private:
		wstring head = L"";
		MyList *tail = NULL;

};

Mit der Methode isEmpty() kann getestet werden, ob die Liste oder Teilliste noch leer ist (also ob "head" ein leerer String ist). Nun sollen über die Methode shift() Elemente am Anfang der Liste eingefügt werden. Die Methode printElements() soll alle Elemente einer Liste schön formatiert in einer Zeile ausgeben:

/* check if the list is empty */
bool MyList::isEmpty() {
	return (this->head.empty());
}

/* add an element at the beginning of the list */
void MyList::shift(wstring newElement) {
	if (!isEmpty()) {
		// add the head to the existing tail
		if (this->tail != NULL) {
			(this->tail)->shift(this->head);
		} else { // create a new tail
			MyList newTail;
			newTail.shift(this->head);
			this->tail = &newTail;
		}
	}
	this->head = newElement;
}

/* print the elements of the list on the console */
void MyList::printElements() {
	if (isEmpty()) {
		wcout << L"|" << endl;
	} else {
		wcout << L"| " << this->head << L" ";
		if (this->tail != NULL) {
			 (this->tail)->printElements();
		} else {
			wcout << L"|" << endl;
		}
	}
}

Bei einigen Testaufrufen von shift() und printElements() verhält sich das Programm nicht wie erwartet. Je nachdem, in welcher Reihenfolge ich die Methoden ausführe und seltsamerweise scheinbar auch abhängig davon, welche Debug-Statements mit "wcout" ich noch drin habe, bleibt das Programm wahlweise an irgendeiner Stelle hängen (Endlosschleife?) oder das zweite Element der Liste ist Kauderwelsch. Ich habe jetzt stundenlang versucht, das mit Konsolenausgaben zu debuggen, finde aber einfach keinen Fehler.

Habe ich bei der Referenzierung bzw. Dereferenzierung von "tail" irgendetwas falsch gemacht? Oder hat es möglicherweise mit den wstrings und wcouts zu tun?

 

[michi.o]

In Zeile 13 wird kein neues Objekt erzeugt. Ich würde da ein "new" erwarten.

 

[Esteba]

Ich dachte eigentlich, dass die Instanziierung in C++ auch ohne "new" möglich ist. Habe aber den betreffenden Code-Teil mal durch das folgende ersetzt...

MyList* newTail = new MyList();
newTail->shift(this->head);
this->tail = newTail;

...und siehe da, es funktioniert!
Jetzt müsste ich nur noch verstehen, warum! Ich sollte mich wohl mal über Speicherallokation in C++ schlau machen.

Danke für den Hinweis!

 

[michi.o]

Ohne new erzeugst Du eine lokale Variable (im Stack), die beim Verlassen der Methode ungültig wird . Mit new wird neuer Speicherplatz allokiert (im Heap) und die Variable bleibt erhalten.

 

[Esteba]

Das erklärt, warum es in der main-Methode ohne new funktioniert hat! Danke!

 

[blackst0rm]

Du darfst dann natürlich nicht vergessen bei der Zerstörung des Objektes den Speicher wieder frei zu geben.

 

[antred]

Ich hoffe, du tust das nur zur Übungszwecken. Die Standardlibrary bietet bereits Listen-Container in Form von std::list und std::forward_list.

Noch ein paar Ratschläge.

1) Gewöhne dir frühzeitig const-korrektes Programmieren an ("wenn etwas const sein kann, dann sollte es auch const sein"). Weder deine isEmpty()-Methode noch deine printElements()-Methode modifiziert die Instanz, auf die sie angewendet wird, also sollten die Methoden die Signatur:

bool isEmpty() const;
void printElements() const;

haben.

2) Eine Instanz deine MyList-Klasse enthält einen Zeiger auf ein anderes MyList-Objekt, welches praktisch der ersteren "gehört". Wenn der Destruktor deiner MyList-Klasse korrekt die der jeweilgen Instanz gehörenden, untergeordneten MyList-Instanzen löscht, dann kann das gefährlich werden. Gehe in Gedanken mal ein Szenario durch, in dem ein Benutzer folgenden Code schreibt (und überlege dir genau, was passiert, wenn die angelegten MyList-Objekte ihr Leben beenden):

{
    MyList firstList;

    // Hier folgt Code, der firstList mit Inhalt befüllt ...
    // ...

    // Jetzt passiert etwas in diesem Falle fatales.
    MyList copyOfFirstList = firstList;

    // Und jetzt wird der Gültigkeitsbereich von firstList und copyOfFirstList  verlassen. Beide Listen werden zerstört.
    // ...
    // *RUMMS!!!* Verstehst du warum?
}

EDIT: Ich gehe in meinem Schreckensszenario davon aus, daß du Kopierkonstruktor und Kopierzuweisungsoperator tatsächlich noch nicht implementiert hast. Wenn du das bereits korrekt getan hast und die Implementierung hier bloß aus Platzgründen weggelassen hast, dann ist mein Einwand hinfällig.

Ergänzung (28. Oktober 2014)

Ohne new erzeugst Du eine lokale Variable (im Stack), die beim Verlassen der Methode ungültig wird .

Um es genau zu sagen, schon beim Verlassen des else-Blocks.

 

[convexus]

ich glaube deine Anstrengungen gehen in die falsche Richtung. In modernen C++ werden Pointer und Speicherallokierungen gemieden, stattdessen werden die Möglichkeiten der Standard-Bibliothek ausgenutzt, hier die Datenstrukturen und insbesondere die Algorithmen. Die STL heißt imo so, da sie bei jedem standardkonformen C++ dabei ist. Wenn es denn eine Liste sein muss, würde ich die von antred vorgeschlagenen Templates verwenden. Selber würde ich anstelle der Liste ehe einen Vector nehmen, Listen sind auf modernen CPU's weniger sinnvoll als man denkt. Ansonsten gibt einige C++ Idiome die du kennen solltest, z:B. RAII, pimpl, ..

 

[Esteba]

Entschuldigt die späte Antwort, ich habe gar nicht mitbekommen dass hier nochmal geantwortet wurde.

Das ganze ist natürlich nur eine Übungsaufgabe. In der Praxis würde ich natürlich eine der bereits bestehenden Listen-Implementierungen nutzen, oder gleich eine ganz andere Datenstruktur.
Trotzdem danke für eure Hinweise! Das sind so Feinheiten, die man erstmal lernen muss, wenn man von Java kommt, wo das doch alles ein bisschen bequemer ist...