Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Was ist eine Liste? - (Dynamische) Datenstrukturen 4
Das Wichtigste aus dem Video
Transkriptautomatisch erstellt · 52 Zeilen
- Moin Leute, ihr kennt bestimmt die Anwesenheitsliste
- #ichwarniedaabertrotzdemaufderListe die to Do Liste die Einkaufsliste und und und
- Aber kennt ihr auch die Liste in Informatik? Nein gut!
- Das ändert sich jetzt. Viel Spaß!
- Also dann: Eine Liste gehört zu den dynamischen Datenstrukturen, soweit wisst ihr ja schon bescheid.
- Das heißt wir können in die Liste ganz easy Elemente einfügen und so den Speicherbedarf dynamisch anpassen.
- So ne Liste besteht aus einzelnen Knoten. Ein Knoten wiederum ist zusammengesetzt aus Daten also irgendnem Inhalt und einem Zeiger.
- 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.
- Deswegen nennt man die auch oft verkettete Listen. Bei Listen gibt es jetzt verschiedene Typen: - die einfach verkettete Liste
- - die doppelt verkettete Liste - die Kreisförmigverkette Liste - usw…
- 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
- Elemente. Genauer gesagt hat so ne einfach verkettete Liste folgende Bestandteile:
- - Einen Anker...Hä?Was laberscht du? Kei Angst siehste gleich, Kollege - Ein oder mehreren Knoten
- - Und eine Endmarke Null. Wie kann ich mir die jetzt also vorstellen?
- 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.
- Dazwischen haben wir ganz viele Knoten. Jede Person zeigt auf seinen Nebenmann.
- Das heißt jeder Knoten kennt seinen unmittelbaren Nachfolger. Außer die Null, die kennt überhaupt kein.
- Ist ja auch das Ende der Kette. Klar?
- Ne? Dann nochmal Allgemein: Das erste Element einer Liste ist der sogenannte
- Start Zeiger, auch gerne als Anker bezeichnet. Der freshe Anker zeigt auf den ersten Knoten der Liste.
- Den Knoten nennt man dann auch Kopf der Liste. Besteht die Liste nur aus diesem Listenelement zeigt der Kopf auf das NULL Element.
- Das Null Element stellt das Ende der Liste dar. Bei größeren Listen zeigt einfach immer der letzte Knoten auf Null.
- Wichtig zu merken ist: Jeder Knoten kennt bei der einfach verketteten Liste nur seinen unmittelbaren Nachfolger.
- Das heißt Knoten 1 weiß alles über Knoten 2, aber rein gar nix über Knoten 3. Jo soweit so gut!
- Der Vorteil bei einer Liste ist, dass man am Anfang nicht schon die Größe dafür wissen muss.
- So ne Liste kann zunächst Leer sein und anschließend beliebig oft mit Elementen bzw. Knoten aufgestockt werden.
- Die Liste verfügt dabei über folgenden Operationen: - Einfügen - Löschen - Suchen
- 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
- - Einfügen am Ende - oder einfügen an x beliebiger Stelle. Im Prinzip funktioniert das Einfügen aber gleich:
- Nehmen wir mal an wir haben eine Liste mit einem Kopf und 2Knoten. Jetzt wollen wir ein Knoten nach dem Kopf einfügen.
- Dazu basteln wir uns ein neuen Knoten. Der Knoten zeigt jetzt auf den ersten Knoten in der alten Liste.
- Jetzt da wir wissen dass jeder wieder ein Nachfolger hat, können wir den Zeiger vom Kopf umstellen.
- Der zeigt jetzt auf den neuen Knoten. Das gleich funktioniert auch beim Einfügen an x belieber Stelle.
- 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.
- Und schwups die wups ist der Knoten eingefügt. Janz Wichtisch!
- Erst den Nachfolger vom neuen Knoten bestimmen und dann erst den Zeiger auf den neuen Knoten setzen.
- Löschen is auch gansch Easy! Wir ham jetzt da unsre Liste und wollen den neuen Knoten wieder löschen.
- Zuerst ändern wir den Zeiger von Knoten 1. Der zeigt jetzt wieder auf Knoten 2.
- Und dann können wir den neuen Knoten auch schon vernichten. So schnell gehts :) Will man ein Element in der Liste suchen,
- hangelt man sich von Element zu Element bis man das gewünschte gefunden hat oder das NULL Element erreicht hat.
- Da jedes Element immer nur seinen Nachfolger kennt, ist so eine längere Suche nötig. Noice!
- Neben der einfach verketteten Liste gibt es noch andere Formen. Bekannt ist noch die doppelt verkettete Liste.
- Bei der doppelt verketteten Liste besitzt jedes Element zwei Zeiger. Ein Zeiger zeigt auf ein Nachfolger und ein Zeiger auf den Vorgänger.
- Ist kein Nachfolger vorhanden wird wieder auf die Null verwiesen. Ist auch kein Vorgänger vorhanden zeigt das Element auch auf die Null.
- 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.
- Oh yeah so viel dazu! Was habt ihr heut gelernt?
- Die Liste gehört zu den dynamischen Datenstrukturen. Eine Listenelement auch Knoten genannt besteht aus einem Inhalt und einem Zeiger.
- Eine Liste kann leer oder eben nicht leer sein. Bei der einfach verkettete Liste kennt jeder Knoten seinen unmittelbaren Nachfolger.
- In Listen kann man neue Elemente einfügen, man kann sie löschen oder auch nach ihnen suchen.
- 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.
- Oder die kreisförmigverkettete Liste, bei der das Ende wieder auf den Anfang zeigt. Jo jo so viel dazu!
- Wenn ihr jetzt bock auf mehr habt, dann schaut doch bei SimpleClub.de vorbei. Bis dahin haut rein und Ciao