verkettete Listen

!Beispiel Verkette Liste.png

Basics

• Verkette Liste: Elemente bestehen aus Inhalt und Nachfolger.
• Jedes Element “verweist” auf seinen Nachfolger.
• Elemente können an beliebiger Stelle eingefügt und gelöscht werden.
• Dabei wird „nur“ der Verweis auf den Nachfolger umgesetzt.
• Und der [[Speicher|Speicher]] des gelöschten Elements freigegeben
• Implementierung benötigt
  • Elemente bestehend aus
    • Inhalt
    • Verweis auf Nachfolger
  • Und die Logik zum
    • Einfügen
    • Durchlaufen und Ausgeben
    • Löschen
• Listenelemente sind ein zusammengesetzter Datentyp
  • Datenwert
  • Verweis auf das nächste Element
• Wurzel
  • Erstes Element wird oft „Wurzel“ (engl. „root“), „Anker“ oder „Kopf“ der Liste genannt
  • enthält die Informationen
    • Länge
    • erstes Element

Implementierung

Listenoperationen

Suchen

• Durchlaufen der Liste
  • Bis das gewünschte Element gefunden wurde
  • Oder das Ende der Liste erreicht ist
• Laufzeit: O(n)

Einfügen

• Elemente werden nur „eingehängt“
• Einfügen „hinter“ bekannter Stelle ist O(1). Position ist durch Pointer bekannt.
• Einfügen an unbekannter Stelle ist O(n).
  • Warum? Position muss erst gesucht werden: Kosten O(n)

Entfernen

• Beim Entfernen wird ein Element, dessen Position bekannt ist, aus der Liste entfernt
• Laufzeit Entfernen bei bekannter Position: O(1)
• Laufzeit Entfernen bei unbekannter Position: O(n)

Versetzen eines Elements

• Um bei Arrays die Reihenfolge der Elemente zu ändern, müssen alle Elemente dazwischen verschoben werden.
• Bei verketteten Listen werden Elemente einfach versetzt
• Laufzeit bei bekannten (Pointern an) Positionen: O(1)
  • (statt O(k), k Anzahl der Stellen, bei Arrays)
• Es gibt zahlreiche Variationsmöglichkeiten bei der Implementierung.
  • “Beste” Variante hängt vom Problem ab.

Struct Definition für Elemente (Namenskonvention _typename):

/* Datentyp für einfach verkettete Liste */ 
typedef struct _slist {
	int value;           // Daten 
	struct _slist *next; // Nachfolger 
	} slist; 
	slist meine_liste;   // Deklaration

Durchlaufen der linked list:

• Anfang an der Wurzel
• Solange wie ein Nachfolger existiert
  • Gib den Wert aus
  • Gehe zum Nachfolger
• wenn kein Nachfolger existiert bzw. NULL-Pointer -> fertig

typedef struct _slist { 
	int value;                  // Daten 
	struct _slist *next;        // Nachfolger 
} slist; 
slist *root, *tmp; 
tmp = root;                    // Anfang an der Wurzel 
while(tmp != NULL) {           // Solange Nachfolger 
	printf("%d\n", tmp->value); // Wert 
	tmp = tmp->next;            // Nächstes Element 
}

Minimale Implementierung:

Datentyp für das erste Element (etwas modifiziert)

typedef struct _list_el { 
	int value;             // Daten 
	struct _list_el *next; // Nachfolger 
} list_el; 

head (Kopfzeiger): Zeigt auf das erste Element der Liste.

typedef struct _list { 
	int count;      // Anzahl Listeneinträge 
	list_el *first; // Erstes Element der Liste 
} list; 

Methoden / Funktionen:

Initialisieren

list * warenliste = calloc(1, sizeof(list)); 
void init_list(list *list_pointer){ 
	list_pointer->first = NULL; 
	list_pointer->count = 0; 
} 
init_list(warenliste);

Find element

• Durchlaufen

Insert element

• Neuen Knoten anlegen
• Knoten initialisieren
• Knoten einfügen

list * warenliste = calloc(1, sizeof(list)); 
void list_insert(list *list_pointer, int value){ 
	list_el * new = (list_el *) calloc(1, sizeof(list_el)); 
	new->value = value; 
	new->next = list_pointer->first; 
	list_pointer->first = new; 
	list_pointer->count++; +
} 
list_insert(warenliste, 100);

• Delete element // Löschen

Ausgeben

list * warenliste = calloc(1, sizeof(list)); 
void list_print(list *list_pointer){ 
	list_el *tmp = list_pointer->first; 
	while(tmp) { 
		printf(“cur: %d “, tmp->value); 
		tmp = tmp->next; 
	} printf(“\n“); 
} 
list_print(warenliste);

Implementierungsvarianten

• es gibt Zahlreiche Möglichkeiten
• "Beste Variante" hängt von Problem ab

Minimale Implementierung:

• head (Kopfzeiger): Zeigt auf das erste Element der Liste.
• Methoden / Funktionen:
  • Find element
  • Insert element
  • Delete element

Verkette Liste mit extra Wurzel

• Allerdings braucht man häufig weitere Informationen
  • Anzahl (#) Listenelemente
  • Letztes Element der Liste
    • Anders als bei Arrays. Bei Array ist durch initialisierung Länge klar definiert
• Lösung:
  • Separate Wurzel für Verwaltungsinformation
    • funktioniert wie ein Inhaltsverzeichnis

Einfacher Kopfzeiger

• !introprog-v04-listen, p.118
• head zeigt auf das erste Element.
• Das Ende der Folge ist durch einen leeren Zeiger (Wert = NULL) gekennzeichnet.
  • Die leere Folge wird dann durch einen leeren Kopfzeiger repräsentiert.
• Nichtleere Folge
• Hinweis zur Implementierung:
  • head muss immer auf das erste Element zeigen (Beachte z.B. insert und delete)

zyklische Verkettung

• !introprog-v04-listen, p.120
• Man kann die Zeigerkette schließen
  • Das erleichtert das Ablaufen in vielen Fällen.
• letztes Element zeigt auf erstes
• Kopfzeiger mit Nullelement (dummy)
• !introprog-v04-listen, p.128
• Neben dem Kopfzeiger wird ein Nullelement verwendet, jedoch mit zyklischer Verkettung.
• Nicht leere Folge
• Auf diese Weise lassen sich viele Listenoperationen recht kompakt und elegant formulieren.