Wie funktioniert die verkettete Liste?

DerDebugger

Hi leute,

kann mir einer erklären, wie eine verkettete Liste funktioniert?
Also ich hab hier sogar das Buch "Einstieg in C++" und ich versteh's trotzdem noch nicht so ganz.

#include <iostream>
using namespace std;

struct TListenKnoten
{
	int data;
	TListenKnoten *next;
};

TListenKnoten *Anker = 0;

int main()
{
	int Inhalt;
	do
	{
		cout << "Zahl eingeben (0 fuer Ende)" << endl;
		cin >> Inhalt;
		if(Inhalt != 0)
		{
			TListenKnoten *Knoten = new TListenKnoten;	
			Knoten->data = Inhalt;
			Knoten->next = Anker;
			Anker = Knoten;
		}
	} while(Inhalt != 0);

	while(Anker)
	{
		cout << Anker->data << endl;
		Anker = Anker->next;
	}

	cin.sync();
	cin.get();
}

Zeigt der Zeiger next auf den neuen Zeiger next?

Oder zeigt der Zeiger next auf den neuen Datentyp TListenKnoten?

Ich versteh es nicht

Hoffe mir kann jemand helfen?

Bei Fragen einfach schreiben.

SeppJ

http://en.wikipedia.org/wiki/Linked_list

edit: Man sollte vielleicht noch anfügen, dass außer für Übungszwecke die korrekte Implementierung einer Liste so aussieht: #include <list>

Cyres

2 Sekunden Google

Hilft dir das Bild weiter? (Wikipedia)

Edit: verdammt, ein wenig zu spät

DerDebugger

Ne hilft mir nicht weiter

Ich hab mir schon zig 1000 Bilder angeschaut, aber ich weiss nicht genau, wie eine verkettete Liste funktioniert.

Cyres

Hast du den Artikel, den SeppJ gepostet hat, mal durchgelesen?

Clundsch

ich habs auch nicht so ganz am anfang verstanden. macht nix.
eine liste ist eine Kette aus beliebig vielen Knoten (Listenelemente), die untereinander über Zeiger verbunden sind.
jedes Listenelement besteht aus dem Inhalt (int, char, vlt auch class, usw.) und einem Zeiger, der auf das nächste Listenelement zeigt.
an sich hat ein Knoten keinerlei Information, wo er in der Liste liegt. er weiß lediglich, wo das nächste Element liegt.
am Anfang musst du einen Listenkopf erzeugen.

ListenElement *lAnfang = new ListenElement;

dann kannst du Elemente hinzufügen.

ListenElement *neuesElement = new ListenElement;
neuesElement->Inhalt = variable //oder was du halt willst

jetzt muss du die aber noch verknüpfen (hab jetzt mal meine fertige Funktion genommen:

void AddElement(T Element)
{
       Listenelement *ne = new Listenelement; //neues Element
       ne->Inhalt = Element;                  //Inhalt füllen
       if (lAnfang->Nachfolger == NULL)       //prüfen, ob Listenkopf bereits
                                              //einen Nachfolger hat
       ae = lAnfang = ne;                     //wenn ja, AltesElement = lAnfang = NeuesElement
       ae->Nachfolger = ne;                   //Den Zeiger vom letzten Element auf das aktuelle Element setzten
       Ende = ae = ne;                        //Ende der Liste definieren
}

dafür wird allerdings noch die Zeile

Listenelement *Anfang, *Ende, *ae;

benötigt.
hoffe du hast es einigermaßen verstanden, wenn nicht, hier die ausführlichere Version: http://www.virtual-maxim.de/dynamische-datenstrukturen-–-einfach-verkettete-liste/