Was ist eine Liste? - (Dynamische) Datenstrukturen 4
Informatik - simpleclub
https://www.youtube.com/watch?v=x0k8MjvWNWw

Transkript (automatisch erstellt)

0:00 Moin Leute, ihr kennt bestimmt die Anwesenheitsliste
0:12 #ichwarniedaabertrotzdemaufderListe die to Do Liste die Einkaufsliste und und und
0:15 Aber kennt ihr auch die Liste in Informatik? Nein gut!
0:19 Das ändert sich jetzt. Viel Spaß!
0:24 Also dann: Eine Liste gehört zu den dynamischen Datenstrukturen, soweit wisst ihr ja schon bescheid.
0:30 Das heißt wir können in die Liste ganz easy Elemente einfügen und so den Speicherbedarf dynamisch anpassen.
0:36 So ne Liste besteht aus einzelnen Knoten. Ein Knoten wiederum ist zusammengesetzt aus Daten also irgendnem Inhalt und einem Zeiger.
0:45 Der Zeiger zeigt dabei in der Regel auf das nächste Element der Liste. Die Elemente einer Liste hängen wie Glieder an einer Kette zusammen.
0:53 Deswegen nennt man die auch oft verkettete Listen. Bei Listen gibt es jetzt verschiedene Typen: - die einfach verkettete Liste
1:00 - die doppelt verkettete Liste - die Kreisförmigverkette Liste - usw…
1:05 Wir beschäftigen uns jetzt erstmal mit der einfach verketteten Liste. So ne Liste kann Leer sein oder sie besteht aus Elementen mit Zeiger auf eine weitere
1:13 Elemente. Genauer gesagt hat so ne einfach verkettete Liste folgende Bestandteile:
1:19 - Einen Anker...Hä?Was laberscht du? Kei Angst siehste gleich, Kollege - Ein oder mehreren Knoten
1:21 - Und eine Endmarke Null. Wie kann ich mir die jetzt also vorstellen?
1:30 Ihr sitzt zusammen mit euren Buddys im Kino und habt ne ganze Reihe reserviert. Die erste Person stellt den Start-Zeiger da und die letzte Person ist die Null.
1:40 Dazwischen haben wir ganz viele Knoten. Jede Person zeigt auf seinen Nebenmann.
1:44 Das heißt jeder Knoten kennt seinen unmittelbaren Nachfolger. Außer die Null, die kennt überhaupt kein.
1:50 Ist ja auch das Ende der Kette. Klar?
1:52 Ne? Dann nochmal Allgemein: Das erste Element einer Liste ist der sogenannte
1:56 Start Zeiger, auch gerne als Anker bezeichnet. Der freshe Anker zeigt auf den ersten Knoten der Liste.
2:02 Den Knoten nennt man dann auch Kopf der Liste. Besteht die Liste nur aus diesem Listenelement zeigt der Kopf auf das NULL Element.
2:10 Das Null Element stellt das Ende der Liste dar. Bei größeren Listen zeigt einfach immer der letzte Knoten auf Null.
2:16 Wichtig zu merken ist: Jeder Knoten kennt bei der einfach verketteten Liste nur seinen unmittelbaren Nachfolger.
2:23 Das heißt Knoten 1 weiß alles über Knoten 2, aber rein gar nix über Knoten 3. Jo soweit so gut!
2:30 Der Vorteil bei einer Liste ist, dass man am Anfang nicht schon die Größe dafür wissen muss.
2:35 So ne Liste kann zunächst Leer sein und anschließend beliebig oft mit Elementen bzw. Knoten aufgestockt werden.
2:41 Die Liste verfügt dabei über folgenden Operationen: - Einfügen - Löschen - Suchen
2:46 Am besten wir ziehen uns mal rein wie das genau funktioniert. Beim Einfügen haben wir drei Möglichkeiten: - Einfügen am Anfang also am Kopf
2:55 - Einfügen am Ende - oder einfügen an x beliebiger Stelle. Im Prinzip funktioniert das Einfügen aber gleich:
3:01 Nehmen wir mal an wir haben eine Liste mit einem Kopf und 2Knoten. Jetzt wollen wir ein Knoten nach dem Kopf einfügen.
3:08 Dazu basteln wir uns ein neuen Knoten. Der Knoten zeigt jetzt auf den ersten Knoten in der alten Liste.
3:15 Jetzt da wir wissen dass jeder wieder ein Nachfolger hat, können wir den Zeiger vom Kopf umstellen.
3:20 Der zeigt jetzt auf den neuen Knoten. Das gleich funktioniert auch beim Einfügen an x belieber Stelle.
3:26 Zunächst wird ein Knoten erstellt, dieser zeigt dann auf das nächste Element. Und der Zeiger des vorherigen Elements zeigt dann auf den neuen Knoten.
3:34 Und schwups die wups ist der Knoten eingefügt. Janz Wichtisch!
3:38 Erst den Nachfolger vom neuen Knoten bestimmen und dann erst den Zeiger auf den neuen Knoten setzen.
3:44 Löschen is auch gansch Easy! Wir ham jetzt da unsre Liste und wollen den neuen Knoten wieder löschen.
3:50 Zuerst ändern wir den Zeiger von Knoten 1. Der zeigt jetzt wieder auf Knoten 2.
3:54 Und dann können wir den neuen Knoten auch schon vernichten. So schnell gehts :) Will man ein Element in der Liste suchen,
4:01 hangelt man sich von Element zu Element bis man das gewünschte gefunden hat oder das NULL Element erreicht hat.
4:07 Da jedes Element immer nur seinen Nachfolger kennt, ist so eine längere Suche nötig. Noice!
4:13 Neben der einfach verketteten Liste gibt es noch andere Formen. Bekannt ist noch die doppelt verkettete Liste.
4:18 Bei der doppelt verketteten Liste besitzt jedes Element zwei Zeiger. Ein Zeiger zeigt auf ein Nachfolger und ein Zeiger auf den Vorgänger.
4:26 Ist kein Nachfolger vorhanden wird wieder auf die Null verwiesen. Ist auch kein Vorgänger vorhanden zeigt das Element auch auf die Null.
4:33 Eine weitere Form der verketteten Liste ist die kreisförmig verkettete Liste. Hier zeigt das letzte Element einfach wieder auf das erste und nicht auf das Null Element.
4:43 Oh yeah so viel dazu! Was habt ihr heut gelernt?
4:47 Die Liste gehört zu den dynamischen Datenstrukturen. Eine Listenelement auch Knoten genannt besteht aus einem Inhalt und einem Zeiger.
4:55 Eine Liste kann leer oder eben nicht leer sein. Bei der einfach verkettete Liste kennt jeder Knoten seinen unmittelbaren Nachfolger.
5:02 In Listen kann man neue Elemente einfügen, man kann sie löschen oder auch nach ihnen suchen.
5:08 Neben der einfach verketteten Liste gibt es noch Formen wie die doppelt verkettete Liste. Da hat jedes Element zwei Zeiger für Vorgänger und Nachfolger.
5:16 Oder die kreisförmigverkettete Liste, bei der das Ende wieder auf den Anfang zeigt. Jo jo so viel dazu!
5:23 Wenn ihr jetzt bock auf mehr habt, dann schaut doch bei SimpleClub.de vorbei. Bis dahin haut rein und Ciao