====== 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.


===== Knoten =====

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

<code c>
typedef struct listnode{
	
	int data;
	listnode *next;
	
};
</code>


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

{{:inf:inf8bi_201819:3:pasted:20190125-084712.png}}

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

{{:inf:inf8bi_201819:3:pasted:20190125-084737.png}}


Eine einfach verkettete Liste mit einem Kopf und zwei Knoten. 

===== Knoten befüllen & einfügen =====

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:

<code c>

	//1. Knoten erstellen
	listnode *node1;
        node1=new listnode;


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

</code>

{{:inf:inf8bi_201819:3:pasted:20190128-202236.png}}

<code c>
	
	
	//2. Knoten erstellen
	listnode *node2;
        node2=new listnode;
  	node2->data=2;
	node2->next=NULL;
	//1. Knoten zeigt auf 2. Knoten
	node1->next=node2;

</code>

{{:inf:inf8bi_201819:3:pasted:20190128-202425.png}}

<code c>
	
	//Knoten 12 zwischen Knoten 1 und 2 einfügen
	listnode *node12;
        node12=new listnode;
 	node12->data=12;
	node12->next=node2;
	node1->next=node12;

</code>

=== Schritt 1 ===

{{:inf:inf8bi_201819:3:pasted:20190128-202640.png}}

=== Schritt 2 ===

{{:inf:inf8bi_201819:3:pasted:20190128-202754.png}}

===== Automatisiertes Hinzufügen von Knoten =====


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.

<code c>

#include <iostream>


using namespace std;

typedef struct listnode{
	
	int data;
	listnode *next;
	
};

int main(int argc, char** argv) {
	
	
	//Kopf der Liste
	listnode *head=NULL;
	

	//10 Knoten hinzufügen
	for(int i=1; i<10; i++)
	{
		listnode *node = new listnode;
		node->data=i;
		node->next=head;
		head=node;
	}
	
	
	//Knoten ausgeben
	listnode *help=NULL;
	help=head;
	
	while(help!=NULL)		//Solange Hilfszeiger nicht auf NULL zeigt
	{
		cout << help->data << endl;	
		help=help->next;
	}

        return 0;
}

</code>

  * [[:inf:inf8bi_201920:1:1_03:1_03_01| 1.3.1) Musterbeispiel ]]