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
Tipp auf eine Zeit – das Video springt genau dorthin.
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
Zum Nachlesen
Liste (Datenstruktur)Eine verkettete Liste ist eine dynamische Datenstruktur, in der Datenelemente geordnet gespeichert sind.
DatenstrukturIn der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine …
Sentinel (Programmierung)Wird auf die Datenstruktur parallel (konkurrent) zugegriffen, dann gehört auch das Suchen per SearchWithSentinel in einen kritischen Abschnitt, der durch ein …
BinärbaumBinärbäume sind in der Informatik die am häufigsten verwendete Unterart der Bäume. Im Gegensatz zu anderen Arten von Bäumen können die Knoten eines …