Lineare Listen (=Einfach verkettete Listen)

Einfach verkettete Listen oder linked lists sind eine fundamentale Datenstruktur, die ich hier anhand von Code-Beispielen und Grafiken erklären will.

Einfach verkettete Listen zeichnen sich dadurch aus, dass man besonders einfach Elemente einfügen kann, wodurch sie sich besonders gut für Insertion Sort eignen.

Listen (besonders verkettete) bieten gegenüber Arrays den großen Vorteil der dynamischen Größenanpassung und effizienter Einfüge-/Löschoperationen (oft mit konstantem Aufwand), da sie nicht an feste Speicherblöcke gebunden sind und sich zur Laufzeit anpassen können, was Speicherplatzverschwendung reduziert; Arrays punkten hingegen bei direktem Zugriff auf Elemente (Index-basiert) und besserer Speicher-Performance bei statischen Datenmengen.

Listen können zur Laufzeit wachsen oder schrumpfen, ohne dass der gesamte Speicher neu zugewiesen werden muss, was sie ideal für unbekannte Datenmengen macht.

Das Hinzufügen oder Entfernen von Elementen ist oft sehr schnell (konstanter Zeitaufwand), da nur Zeiger angepasst werden müssen, anstatt Daten zu verschieben.

Sie vermeiden die Reservierung von zu viel oder zu wenig Speicher, da der Speicherbedarf sich an die tatsächliche Anzahl der Elemente anpasst.

Der Zugriff auf ein Element über seinen Index ist sehr schnell, da der Speicher zusammenhängend ist.

Arrays speichern nur die Daten selbst, ohne die zusätzlichen Zeiger, die verkettete Listen benötigen, was zu geringerem Speicherverbrauch führt.

Für feste Datengrößen sind Arrays oft einfacher zu implementieren und zu handhaben.

Wenn sich die Anzahl der Elemente häufig ändert, Sie oft Elemente am Anfang, Ende oder in der Mitte einfügen oder löschen müssen, oder wenn die Anzahl der Elemente unbekannt ist.

Wenn die Größe der Sammlung bekannt ist und sich nicht ändert und Sie häufig Elemente direkt über ihren Index ansprechen müssen (z.B. bei mathematischen Operationen

Eine einfach verkettete Liste besteht aus Knoten, Englisch nodes, die einen Zeiger auf das nächste Element und Daten beinhalten.

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

Eine leere Liste besteht aus einem Kopf (Head) und nichts sonst:

Wenn man mehrere Elemente einfügt, sieht das so aus:

Eine einfach verkettete Liste mit einem Kopf und zwei Knoten.

Wenn man einen Zeiger auf ein Element der Liste hat, ist es einfach, ein Element dahinter einzufügen.

Dazu muss man den next-Zeiger der Liste auf das neue Element setzen, und den next-Zeiger des neuen Element auf den alten Wert des next-Zeigers der Liste:

	//1. Knoten erstellen
	list *node1 = new List();
 
	//1. Knoten befüllen
	node1->data=1;    //oder (*node1).data=1;
	node1->next=NULL;

 
	//2. Knoten erstellen
	list *node2 = new List();;
  	node2->data=2;
	node2->next=NULL;
	//1. Knoten zeigt auf 2. Knoten
	node1->next=node2;

	//Knoten 12 zwischen Knoten 1 und 2 einfügen
	list *node12 = new List();;
 	node12->data=12;
	node12->next=node2;
	node1->next=node12;

Ein neuer Listenknoten wird durch Aufruf von new erzeugt. Dabei muss darauf geachtet werden, dass der Zeiger next gleich korrekt gesetzt wird. Wenn Sie nicht sofort den Nachfolger einhängen können, setzen Sie den Zeiger auf NULL.

#include <iostream>
 
 
using namespace std;
 
typedef struct list{
 
	int data;
	list *next;
 
};
 
int main(int argc, char** argv) {
 
 
	//Kopf der Liste
	list *head=NULL;
 
 
	//10 Knoten hinzufügen
	for(int i=1; i<10; i++)
	{
		list *node = new list;
		node->data=i;
		node->next=head;
		head=node;
	}
 
 
	//Knoten ausgeben
	list *help=NULL;
	help=head;
 
	while(help!=NULL)		//Solange Hilfszeiger nicht auf NULL zeigt
	{
		cout << help->data << endl;	
		help=help->next;
	}
 
        return 0;
}

//Datum: 30.09.2025
//Autor: Lahan
 
#include <iostream>
 
using namespace std;
 
struct Auto
{
	string marke = "";
	int tueren = 0;
	Auto* next = NULL;
};
 
//Funktionsdeklaration für das Einfügen eines Elements in die Liste
void insertElement(Auto *begin, string m, int t);
void printListe(Auto* begin);
void deleteElement(Auto** begin, string m); //Löscht ein Element anhand der eindeutigen Marke
 
//Funktionsdeklaration für das Ausgeben der Elemente der Liste
 
int main()
{
	Auto* start = new Auto();
 
 
 
	insertElement(start, "Mercedes", 3);
	//cout << start->marke;
	insertElement(start, "Dacia", 5);
	//cout << start->next->marke;
	insertElement(start, "BMW", 5);
	//cout << start->next->next->marke;
	insertElement(start, "Renault", 5);
	insertElement(start, "Peugeot", 5);
	insertElement(start, "Mustang", 5);
	insertElement(start, "Toyota", 5);
	insertElement(start, "VW", 5);
	insertElement(start, "Audi", 5);
	insertElement(start, "Porsche", 5);
 
	printListe(start);
 
	deleteElement(&start, "BMW");
 
	printListe(start);
 
	deleteElement(&start, "Mercedes");
 
	printListe(start);
 
	deleteElement(&start, "Porsche");
	printListe(start);
 
}
 
//Funktionsdefinition für das Einfügen eines Elements in die Liste
void insertElement(Auto* begin, string m, int t)
{
	Auto* hilf = NULL;
 
	//Wenn das erste Element noch nicht befüllt, dann füge bei begin die Werte ein
	if (begin->marke.length() == 0)
	{
		begin->marke = m;
		begin->tueren = t;
		begin->next = NULL;
	}
	else //Liste beinhaltet zumindest schon ein Element 
	{
		hilf = begin;
		while (hilf->next != NULL)
		{
			hilf = hilf->next;
		}
		hilf->next = new Auto();
		hilf->next->marke = m;
		hilf->next->tueren = t;
		hilf->next->next = NULL;
	}
 
}
 
void printListe(Auto* begin) 
{
	Auto* hilf = begin;
	int zaehler = 1;
 
	while (hilf != NULL)
	{
		cout << zaehler << ". Element: \t" << hilf->marke << "\t"
			 << hilf->tueren << " Tueren" << endl;
		hilf = hilf->next;
		zaehler++;
	}
}
 
void deleteElement(Auto** begin, string m)
{
	Auto* hilf = *begin, *hilf2 = NULL;
 
 
	//1. FALL - Das zu löschende Element ist das erste Element
	//Schritt 1: Prüfen ob das erste Element das zu löschende Element ist
	if ((*begin)->marke == m)
	{
		//Schritt 2: Speichere die Adresse des nachfolgenden Elements
		hilf = (*begin)->next;
 
		//Schritt 3: Löschen des Elements
		delete(*begin);
 
		//Schritt 4: Zeiger begin auf das "neue" erste Element zeigen lassen
		*begin = hilf;
	}
 
	//2. FALL - Element ist zwischen zwei anderen Elementen 
	//Schritt 1: Finde die Position vor dem zu löschenden Element
	while (hilf->next != NULL)
	{
		if (hilf->next->marke == m)
		{
			cout << endl << "Zu loeschendes Element:" << hilf->next->marke << endl << endl;
 
			//Lösche das Element und verbinde das vorherige Element mit dem nachfolgenden
			//Schritt 2: Speichere die Adresse des nachfolgenden Elements zwischen (hilf2)
			hilf2 = hilf->next->next;
 
			//Schritt 3: Löschen des Elements
			delete(hilf->next);
 
			//Schritt 4: Einfach verkettete Liste wieder verbinden
			hilf->next = hilf2;
 
			break;
		}
		hilf = hilf->next;
	}
 
}