[Musikwiedergabe] 

DOUG LLOYD: OK, so zumin dieser Punkt im Verlauf, wir haben eine Menge von den Grundlagen der C abgedeckt Wir wissen eine Menge über Variablen, Arrays, Zeiger, alles, gute Sachen. Das sind alles Art gebaut in die als die Grundlagen sehen aber wir können noch mehr tun, nicht wahr? Wir können Dinge zu kombinieren zusammen auf interessante Weise. 

Und so wollen wir das tun, lassen Sie uns beginnen um aus dem, was C gibt uns zu verzweigen, und beginnen, unsere eigenen Daten zu erstellen Strukturen unter Verwendung dieser Gebäude Blöcke zusammen, um etwas zu tun, wirklich wertvoll, nützlich. Ein Weg, können wir dies zu tun ist über Sammlungen sprechen. Also so weit haben wir eine Art von Daten hatte Struktur zum Darstellen Sammlungen der gerne Werte, ähnliche Werte. Das wäre ein Array sein. Wir haben Sammlungen von ganzen Zahlen oder Sammlung von Zeichen und so weiter. 

Strukturen werden auch von einem Daten sortieren Struktur zum Sammeln von Informationen, aber es ist nicht für das Sammeln wie Werte. Es mischt sich in der Regel unterschiedliche Datentypen zusammen in einer einzigen Box. Aber es ist nicht selbst zusammen zur Ketten oder miteinander verbinden ähnliche Einzelteile, wie ein Array. Arrays sind für Element auf, sondern Rückruf , dass es sehr schwierig ist um in ein Array einfügen, es sei denn, wir sind bei Einsetzen das Ende des Arrays. 

Und das beste Beispiel habe ich denn das ist Insertion Sort. Wenn Sie sich unser Video erinnern on Insertion Sort, es gab eine Menge von Aufwand mit einbezogen abholen Elemente und verschieben sie aus dem Weg, um etwas zu passen in der Mitte des Arrays. Arrays leiden auch unter einem anderen Problem, das ist mangelnde Flexibilität. Wenn wir erklären, ein Array, wir bekommen einen Schuss auf ihn. Wir bekommen zu sagen, ich will so viele Elemente. Vielleicht 100, könnte es sein 1000, könnte es sein, worin x eine Zahl ist, dass der Benutzer hat uns mit einer Eingabeaufforderung oder in der Befehls Linie. 

Aber wir nur einen Schuss auf ihn zu bekommen, die wir nicht bekommen, um dann sagen, oh, eigentlich habe ich benötigt 101, oder ich brauchte x plus 20. Zu spät, die wir bereits erklärt haben, die Array und wenn wir wollen, um 101 oder erhalten x plus 20, müssen wir erklären, ein ganz anderes Array, kopieren Sie alle Elemente des Arrays über, und dann haben wir genug. Und was, wenn wir uns wieder falsch sind, was wenn wir wirklich brauchen 102 oder x plus 40, müssen wir dies wieder tun. So sind sie sehr unflexibel für die Größenänderung unsere Daten, aber wenn wir zusammen etwas zu kombinieren von den Grundlagen, die wir bereits haben über Zeiger und Strukturen gelernt, insbesondere unter Verwendung von dynamischen Speicher Belegung mit malloc, wir können diese Stücke zusammen um eine neue Daten structure-- a erstellen einfach verkettete Liste könnten wir sagen-- dass ermöglicht es uns, zu wachsen und Schrumpf eine Sammlung von Werten und wir werden keinen Platz verschwendet. 

Also noch einmal, nennen wir diese Idee, dieser Begriff, eine verknüpfte Liste. Insbesondere in diesem Video sind wir reden einfach verkettete Liste, und dann ein anderes Video wir reden etwa doppelt verkettete Listen, die ist nur eine Variation über ein Thema hier. Aber eine einfach verkettete Liste wird aus Knoten, Knoten gerade eine abstrakte term-- es ist nur etwas, was ich rufe das ist eine Art von Struktur, im Grunde bin ich? Nur gehen, nennen es einen node-- und dies Knoten zwei Mitglieder oder zwei Felder. Es verfügt über Daten, in der Regel ein ganze Zahl, ein Zeichen, float, oder könnte ein anderer Datentyp sein , dass Sie mit einer Art def definiert haben. Und einen Zeiger auf enthält einen anderen Knoten des gleichen Typs. 

So haben wir zwei Dinge im Inneren des Dieser Knoten, Daten und einen Zeiger zu einem anderen Knoten. Und wenn Sie beginnen zu visualisieren Damit kann man darüber nachdenkt, wie eine Kette von Knoten, sind miteinander verbunden. Wir haben den ersten Knoten, es Daten enthält, und einen Zeiger an den zweiten Knoten, der enthält Daten und einen Zeiger auf den dritten Knoten. Und damit ist, warum es eine nennen wir verknüpften Liste, sie miteinander verbunden sind. 

Was bedeutet diese Sonder Knotenstruktur aus? Nun, wenn Sie aus unserem Video on erinnern Definition von benutzerdefinierten Typen, mit Typ-def, können wir eine structure-- definieren und Geben Sie definieren eine Struktur wie diese. tyepdef struct sllist, und dann bin ich Verwendung hier das Wort ein Wert beliebig um beliebige Datentypen richtig anzuzeigen. Sie könnten auf Integer oder Float übergeben, könnten Sie haben, was Sie wollen. Es ist nicht nur beschränkt ganzen Zahlen, oder so etwas. So Wert ist nur ein beliebiger der Datentyp und dann ein Zeiger an einen anderen Knoten des gleichen Typs. 

Nun, es ist ein wenig fangen hier mit der Definition einer Struktur wenn es eine Selbstbezugsstruktur. Ich habe einen temporären zu haben, Namen für meine Struktur. Am Ende des Tages habe ich es nennen wollen, klar SLL-Knoten, das ist schließlich das neue nennen Teil meiner Typ-Definition, aber ich kann nicht verwenden sll Knoten in der Mitte davon. Der Grund dafür ist, habe ich nicht schuf eine sll Knotentyp genannt bis ich hier aus den letzten Punkt. Bis zu diesem Zeitpunkt muss ich haben Ein anderer Weg zu dieser Datentyp. 

Und dies ist ein selbst Referenzdatentyp. Es; s Datentyp ein Struktur, die einen Daten enthält, und einen Zeiger auf ein anderes Struktur des gleichen Typs. Also muss ich in der Lage, zu beziehen sein Dieser Datentyp wenigstens vorübergehend so gibt es eine vorübergehende Name des struct sllist erlaubt mir dann sagen, ich möchte ein Zeiger auf eine andere Struktur sllist, eine Struktur sllist Sterne, und dann nachdem ich die Definition abgeschlossen ist, Jetzt kann ich diese Art ein sll Knoten nennen. 

Also das ist, warum Sie sehen, es gibt hier einen temporären Namen, sondern eine dauerhafte Namen hier. Manchmal werden Sie vielleicht sehen, Definitionen der Struktur, zum Beispiel, die nicht selbst verweis, dass keine Spezifizierer Namen hier. Es würde einfach sagen, typedef struct, öffnen geschweifte Klammer und dann definieren. Aber wenn Sie struct ist selbst referentielle, als dieses ist, Sie brauchen, um ein angeben Namen temporärer Art. Aber letztlich jetzt dass wir das getan, wir können einfach zu beziehen diese Knoten, diese Einheiten, wie sll Knoten für Zwecke der Rest dieses Video. 

Na gut, so dass wir wissen, wie man erstellen Sie eine verknüpfte Liste Knoten. Wir wissen, wie zu definieren, eine verbundene Liste Knoten. Nun, wenn wir gehen, um zu starten mit ihnen, um Informationen zu sammeln, es gibt ein paar Operationen wir müssen verstehen, und die Arbeit mit. Wir müssen wissen, wie das Erstellen eine verknüpfte Liste aus der Luft gegriffen. Wenn es keine Liste bereits, wir wollen zu starten. Also müssen wir zu können , eine verknüpfte Liste zu erstellen, wir müssen wahrscheinlich zu suchen durch die Link-Liste um ein Element wir finden. Wir müssen in der Lage, einzufügen neue Dinge in die Liste, wir wollen, dass unsere Liste, um zu wachsen. Und in ähnlicher Weise zu können wollen wir die Dinge aus unserer Liste zu löschen, wir wollen, dass unsere Liste, um zu schrumpfen. Und am Ende der Programme, insbesondere Wenn Sie sich erinnern, dass wir die dynamische Zuweisung von Speicher diese Listen in der Regel zu bauen, wir alle, dass Speicher frei möchten wenn wir fertig sind mit ihm arbeiten. Und so müssen wir in der Lage, einen zu löschen gesamten verknüpften Liste in einem nicht Schlag. Lassen Sie uns also durchlaufen einige dieser Operationen und wie wir sie sichtbar zu machen, Gespräche in Pseudocode spezifisch. So, um eine erstellen möchten wir verknüpften Liste, so dass wir vielleicht möchte eine Funktion zu definieren Mit diesem Prototyp. sll Knoten Sterne, zu erstellen, und ich bin vorbei in einem Argument, einige beliebige Daten erneut eingeben, der einer beliebigen Datentyp. Aber ich bin returning-- diese Funktion sollten kehrt zu mir einen Zeiger auf eine einzeln verknüpften Liste Knoten. Auch hier versuchen wir, zu erstellen eine verknüpfte Liste aus der Luft gegriffen, so brauche ich einen Zeiger auf dass die Liste, wenn ich fertig bin. 

Also, was sind die Schritte hier beteiligt? Nun, ich bin erste, was zu tun ist, dynamisch Speicherplatz zuweisen für einen neuen Knoten. Auch hier schaffen wir es aus dem Nichts Luft, so müssen wir malloc Platz dafür. Und natürlich sofort nachdem wir malloc, wir prüfen immer, um sicherzustellen, dass unsere pointer-- wir nicht wieder null. Denn wenn wir versuchen, Ehrerbietung einen Null-Zeiger, wir werden leiden ein segfault und wir wollen das nicht. 

Dann, im Bereich füllen möchten wir, wir den Wert Feld initialisiert werden soll und initialisieren Sie das nächste Feld. Und dann zu-- schließlich als das wollen wir Funktionsprototyp indicates-- wir wollen, einen Zeiger auf ein sll Knoten zurückzukehren. Also, was machen diese sehen aus wie optisch? Nun, zunächst einmal, wir werden dynamisch Speicherplatz zuweisen für eine neue sll Knoten, so dass wir malloc-- das ist, eine visuelle Darstellung des Knotens wir gerade erstellt. Und wir überprüfen, ob es ist in diesem Fall nicht null--, das Bild nicht hätte up gezeigt, wenn es null, wir würden über genügend Arbeitsspeicher ausgeführt haben, so sind wir gut, dorthin zu gehen. So, jetzt sind wir zu dem Schritt C, initialisieren Sie den Knoten Wertefeld. Nun, auf der Grundlage dieser Funktion aufrufen Ich verwende hier, sieht aus wie ich in 6 übergeben, so werde ich 6 im Wertefeld. Nun, initialisieren Sie das nächste Feld. Nun, was soll ich nur tun gibt, gibt es nichts weiter, rechts, Das ist das einzige, was in der Liste. Also, was ist das nächste, was in der Liste? 

Es sollte auf nichts, richtig. Es gibt nichts anderes gibt, so was ist das Konzept kennen wir, das ist nothing-- Zeiger auf nichts? Es sollte vielleicht wir wollen, einen Null-Zeiger dort setzen, und ich werde die Null stellen Zeiger als nur ein rotes Feld, wir können nicht weiter gehen. Wie wir später ein wenig zu sehen, wir schließlich Ketten Pfeile Verbindungs diese Knoten zusammen, aber wenn Sie drücken Sie die rotes Feld, das ist null, wir können nicht weiter gehen, das ist das Ende der Liste. 

Und schließlich wollen wir nur liefern einen Zeiger auf diesen Knoten. Also werden wir es nennen neue, und neue Rück so kann es verwendet werden in was auch immer-Funktion geschaffen hat. Es gibt also wir gehen, haben wir ein einfach erstellt verknüpften Liste Knoten aus der Luft gegriffen, und jetzt haben wir eine Liste wir arbeiten können. 

Nun lassen Sie uns sagen, dass wir bereits haben eine große Kette, und wir wollen etwas in ihm zu finden. Und wir wollen, eine Funktion, die gehen true oder false zurück, je davon ab, ob ein Wert in der Liste vorhanden ist. Ein Funktionsprototyp oder Erklärung für die Funktion, aussehen könnte this-- bool zu finden, und dann wollen wir in zwei Argumente übergeben. 

Das erste ist ein Zeiger auf die erste Element der verketteten Liste. Das ist eigentlich etwas, das Sie wollen immer, um zu verfolgen, und tatsächlich könnte etwas sein, dass Sie sogar in einer globalen Variablen gesetzt. Sobald Sie eine Liste zu erstellen, Sie immer, immer wollen den Überblick über die sehr zu halten erste Element der Liste. So können Sie auf alle anderen beziehen Elemente nur durch Anschluss an die Kette, ohne Zeiger zu halten intakt zu jedem einzelnen Element. Sie müssen nur den Überblick über die ersten zu halten eine, wenn sie alle miteinander verkettet. 

Und dann die zweite Sache, wir sind wieder vorbei in beliebig some-- unabhängig von Datentyp sind wir Suche nach gibt es im Inneren des hoffentlich einen der Knoten in der Liste. Also, was sind die Schritte? Nun, das erste, was wir tun, ist schaffen wir eine Querzeiger zeigte auf den Listen Kopf. Nun, warum wir das tun, haben wir bereits einen Zeiger an der Listen Kopf, warum nicht wir bewegen nur, dass man in der Umgebung? Nun, wie ich gerade gesagt habe, es ist wirklich wichtig für uns, um immer den Überblick über die zu halten allererste Element in der Liste. Und so ist es tatsächlich besser ein Duplikat daß schaffen, und verwenden, die in der Umgebung von nie zu bewegen, so dass wir versehentlich weg, oder wir immer einen Zeiger zu einem bestimmten Zeitpunkt, das ist direkt auf das erste Element der Liste. So ist es besser, einen zu erstellen zweite, die wir verwenden, um zu bewegen. 

Dann vergleichen wir nur, ob das Wertefeld an diesem Knoten ist das, was wir suchen, und wenn es nicht, wir haben nur an den nächsten Knoten zu verschieben. Und wir weiterhin tun, dass über und über und über, bis wir entweder zu finden das Element, oder wir treffen null-- wir das Ende erreicht auf der Liste und es ist nicht da. Dies sollte hoffentlich eine Glocke läuten Ihnen als nur lineare Suche, wir sind nur zu replizieren es in eine einfach verkettete Liste Struktur anstelle der Verwendung einer Anordnung, um dies zu tun. 

Also hier ist ein Beispiel dafür, eine einfach verkettete Liste. Dieser besteht aus fünf Knoten, und wir haben ein Zeiger auf den Kopf des Liste, die Liste aufgerufen wird. Das erste, was wir tun wollen, ist wieder, noch zu einer Durchquerung Zeiger. So haben wir jetzt zwei Zeiger dass auf die gleiche Sache. 

Jetzt bemerken auch hier habe ich nicht müssen keine Platz für trav malloc. Ich habe nicht gesagt trav gleich malloc etwas, bereits vorhanden ist, dass der Knoten, dass Platz im Speicher vorhanden ist. Also alles, was ich eigentlich tun ist die Schaffung einer anderen Zeiger darauf. Ich bin nicht mallocing eine zusätzliche Raum, haben gerade zwei Zeiger , die auf die gleiche Sache. 

So ist 2, was ich suche? Nun, nein, so dass anstelle Ich bin gehen, um zum nächsten zu bewegen. Also im Grunde würde ich sagen, trav gleich trav nächsten. Ist 3, was ich suche, nein. Also habe ich weiter gehen durch, bis schließlich bekommen bis 6 das ist, was ich suche für die auf der Funktionsaufruf auf der Basis Ich habe an der Spitze dort, und so bin ich fertig. 

Nun, was ist, wenn das Element Ich bin suche, ist nicht in der Liste, ist es immer noch zur Arbeit zu gehen? Nun, feststellen, dass die Liste Hier ist auf subtile Weise anders, und das ist eine andere Sache, die ist wichtig verkettete Listen, Sie müssen nicht zu erhalten sie in einer bestimmten Reihenfolge. Sie können, wenn Sie wollen, aber Sie vielleicht schon bemerkt haben dass wir nicht die Verfolgung von welche Nummer Element stehen wir. 

Und das ist eine Art von Handel, die wir haben mit verknüpften Liste Verse Arrays, wird wir nicht Direktzugriff mehr. Wir können nicht einfach sagen, ich will an der 0-ten Element zu gehen, oder das 6. Element meiner Array, die ich in einem Array zu tun. Ich kann nicht sagen, ich will, um unterwegs 0. Element oder das 6. Element, oder das 25. Element meiner verknüpften Liste, es gibt keinen Index mit ihnen verbunden sind. Und so ist es nicht wirklich wichtig, wenn wir unsere Liste, um zu bewahren. Wenn Sie Sie wollen sicherlich kann, aber es gibt keinen Grund, warum sie brauchen in beliebiger Reihenfolge erhalten werden. Also noch einmal, lassen Sie uns versuchen und finden 6 in dieser Ansicht. Nun, fangen wir an die Anfang, wir nicht finden, 6, und dann weiter wir nicht finden, 6, bis wir schließlich zu uns kommen. So jetzt trav Punkte an den Knoten mit 8 und sechs ist nicht drin. 

Der nächste Schritt wäre, um zum nächsten Zeiger zu gehen, so sagen trav gleich trav nächsten. Nun, trav nächsten, angezeigt durch die rote Box gibt, ist null. So gibt es nirgendwo anders zu gehen, und so an dieser Stelle können wir feststellen, dass wir erreicht haben das Ende der verketteten Liste, und 6 ist nicht drin. Und es zurückgegeben werden würde falsch in diesem Fall. 

OK, wie können wir setzen Sie eine neue Knoten in der verknüpften Liste? So haben wir in der Lage, zu erstellen eine verknüpfte Liste aus dem Nichts, aber wir wollen wahrscheinlich Aufbau einer Kette und nicht erstellen eine Reihe von unterschiedlichen Listen. Wir wollen eine Liste haben, dass hat eine Reihe von Knoten drin, nicht ein Haufen von Listen mit einem einzigen Knoten. So können wir nicht nur halten mit der CREATE Funktion zuvor definierten wir, jetzt sind wir wollen in ein einfügen Liste, die bereits vorhanden ist. 

Also hier, wir gehen in zwei Argumente übergeben, der Zeiger auf den Kopf, dass verknüpften Liste, die wir hinzufügen möchten. Wieder, das ist, warum es so wichtig, dass wir immer im Auge behalten, denn es ist die einzige Art, wie wir wirklich haben, um sich auf die ganze Liste nur durch einen Zeiger auf das erste Element. So dass wir in eine weitergeben wollen Zeiger auf das erste Element, und was wir Wert möchte in die Liste aufzunehmen. Und schließlich diese Funktion wird einen Zeiger zurück auf den neuen Chef einer verketteten Liste. 

Was sind die Schritte hier beteiligt? Nun, genau wie bei zu erstellen, wir brauchen, um dynamisch zuzuweisen Platz für einen neuen Knoten, und überprüfen Sie, dass wir nicht über genügend Arbeitsspeicher ausgeführt, wieder, weil wir unter Verwendung von malloc. Dann, um zu bevölkern wollen wir und fügen Sie den Knoten, so setzen die Zahl, was auch immer val ist, in den Knoten. Wir wollen den Knoten einfügen der Anfang der verknüpften Liste. 

Es gibt einen Grund, dass ich dies tun wollen, und es vielleicht lohnt sich ein zweiter sein um das Video hier zu unterbrechen, und darüber, warum ich zu wollen, denken Einsatz am Anfang einer verknüpften Liste. Auch erwähnte ich vorher , dass es nicht wirklich egal, ob wir es zu bewahren in jeder um, so vielleicht ist das ein Anhaltspunkt. Und man sah, was geschehen würde, wenn wir wollte zu-- oder von nur einer Sekunde vor, wenn wir wollten durch Suche können Sie konnte, was sehen könnte passieren, wenn wir versuchten, am Ende der Liste eingefügt. Denn wir haben nicht ein Zeiger auf das Ende der Liste. 

Also der Grund, dass ich würde zu Beginn einzufügen, ist, weil ich es sofort tun. Ich habe einen Zeiger am Anfang, und Wir werden dies in einer visuellen in einem zweiten zu sehen. Aber wenn ich am Ende einfügen, Ich muss am Anfang beginnen, queren den ganzen Weg zu der Ende, und dann tack sie auf. So würde das bedeuten, dass Einsetzen am Ende der Liste wäre ein o n geworden Betrieb, geht zurück unsere Diskussion Rechenkomplexität. Es wäre ein o n Betrieb, in dem sich die Liste wurde größer und größer, und größer, es wird mehr werden und schwieriger, etwas zu heften am Ende. Aber es ist immer wirklich einfach, tack etwas am Anfang, du bist immer am Anfang. 

Und wir werden sehen, noch einmal eine visuelle dafür. Und dann, sobald wir fertig sind, einmal wir haben den neuen Knoten eingefügt, wir unsere Zeiger zurückgeben möchten der neue Leiter einer verknüpften Liste, die da wir in der Einführungs beginnen, tatsächlich sein wird ein Zeiger zu dem Knoten wir gerade erstellt. Lassen Sie uns dies zu visualisieren, weil ich denke, es wird Ihnen helfen. 

Also hier ist unsere Liste, es besteht aus vier Elemente, ein Knoten, der 15, was auf einem Knoten enthält 9, die verweist auf einen Knoten mit 13 der an einem Knotenpunkt der Punkte enthält 10, die den null hat Zeiger als nächstes Zeiger damit ist das Ende der Liste. So ein einfügen wollen wir neuen Knoten mit dem Wert 12 am Anfang dieses Liste, was sollen wir tun? Nun, zunächst malloc wir Raum für die Knoten, und dann haben wir 12 drin. 

So, jetzt haben wir erreicht haben, ein Entscheidungspunkt, nicht wahr? Wir haben ein paar Hinweise, dass wir zu bewegen, die einen sollten wir zuerst zu bewegen? Sollten wir 12 Punkt der neue Leiter des list-- oder entschuldigen Sie, sollten wir 12 auf den alten Kopf der Liste? Oder sollten wir sagen, dass die Liste beginnt nun bei 12. Es gibt einen Unterschied gibt, und wir werden sehen was sowohl in einem zweiten Fall. 

Dies führt jedoch zu einer großes Thema für die Seitenleiste, die, dass einer der ist heikelsten Dinge mit verknüpften Listen wird der Zeiger zu arrangieren in der richtigen Reihenfolge. Wenn Sie die Dinge in Ordnung zu bewegen, können Sie versehentlich am Ende verwaisen den Rest der Liste. Und hier ist ein Beispiel dafür. Lassen Sie uns also mit dem Gedanken gehen von-- Nun, wir haben gerade 12. Wir wissen, dass 12 sein wird, der neue Kopf der Liste, und so, warum wir nicht einfach bewegen Die folgende Liste enthält Zeiger auf es verweisen. 

OK, das ist gut. So, jetzt wo endet 12 nächste Punkt? Ich meine, wir sehen können visuell dass es bis 15 zeigen, als Menschen, es ist zu uns wirklich auf der Hand. Wie funktioniert der Computer wissen? Wir haben nichts zeigt auf 15 mehr, oder? 

Wir haben keine Möglichkeit, bis 15 beziehen sich verloren. Wir können nicht sagen neue Pfeil neben equals etwas, da ist nichts. Tatsächlich haben wir verwaiste habe der Rest der Liste Auf diese Weise haben wir Versehen Sie die Kette gebrochen. Und wir wollen sicher nicht, das zu tun. 

Also lassen Sie uns gehen Sie zurück und noch einmal versuchen. Vielleicht ist das Richtige zu tun, ist es, 12 der nächste Zeiger gesetzt zur alten Kopf der Liste zuerst dann können wir die Liste über zu bewegen. Und in der Tat ist, dass das richtigen Reihenfolge, dass wir folgen müssen, wenn wir Arbeiten mit einfach verkettete Liste. Wir wollen immer die verbinden neues Element in der Liste, bevor wir diese Art von wichtiger Schritt des Änderns wo der Kopf der verketteten Liste ist. Wieder ist, dass eine solche grundlegende Sache, wir wollen nicht zu verfolgen, es zu verlieren. 

Also, um sicherzustellen, dass wir wollen alles miteinander verkettet, bevor wir diesen Zeiger. Und so wäre dies die richtige Reihenfolge zu sein, die an der Liste Verbinden 12, dann sagen, dass die Liste beginnt eine 12. Wenn wir die Liste beginnt bei 12 und dann versucht, in die Liste zu verbinden 12, Wir haben bereits gesehen, was passiert. Wir verlieren die Liste aus Versehen. 

OK, so dass eine weitere Sache, darüber zu sprechen. Was ist, wenn wir wollen, um loszuwerden, eine ganze verbundene Liste auf einmal? Auch hier sind wir mallocing all das Platz, und so haben wir brauchen, um es zu befreien, wenn wir fertig sind. So, jetzt löschen möchten wir die gesamte verknüpfte Liste. Nun, was wollen wir tun? 

Wenn wir die Null-Zeiger zu erreichen, haben wir aufhören, sonst, einfach löschen der Rest der Liste und dann befreie mich. Löschen Sie den Rest der Liste, und dann befreien den aktuellen Knoten. Wie klingt das wie, Welche Technik haben wir sprachen über zuvor Klingt das wie? Alle löschen anderes, dann kommen zurück, und löschen Sie mich. 

Das ist die Rekursion, die wir gemacht haben die Problem ein wenig kleiner, wir sagen löschen jedermann anderes, dann können Sie mir zu löschen. Und weiter die Straße hinunter, dass der Knoten wird sagen, löschen Sie alle anderen. Aber irgendwann werden wir um das zu bekommen Punkt, an dem die Liste ist null, und das ist unser Basisszenario. 

Werfen wir also einen Blick auf diese, und wie dies funktionieren könnte. Also hier ist unsere Liste, ist es das gleiche Liste waren wir nur darüber zu reden, und es gibt die Schritte. Es gibt eine Menge von Text hier, aber hoffentlich die Visualisierung hilft. 

Also haben wir have-- und ich zog auch unsere Stapelrahmen illustration aus unserem Video auf Abruf-Stacks, und hoffentlich all dies zusammen wird Ihnen zeigen, was los ist. Also hier ist unsere Pseudocode. Wenn wir ein Null zu erreichen Zeiger zu stoppen, sonst, löschen Sie den Rest der Liste, dann kostenlos den aktuellen Knoten. So jetzt, list-- der Zeiger, die wir sind vorbei an den Punkten 12 zu zerstören. 12 ist kein Null-Zeiger, so sind wir gehen, um den Rest der Liste zu löschen. 

Was ist das Löschen der Rest von uns beteiligt? Na ja, bedeutet dies, dass ein anrufen, um zu zerstören, zu sagen dass 15 ist der Beginn der Rest der Liste, die wir zerstören wollen. Und so wird der Anruf zu zerstören 12 ist eine Art zu halten. Es gibt eingefroren und warten auf die anrufen, um zu zerstören 15, um seine Arbeit zu beenden. 

Nun, 15 ist kein Null-Zeiger, und also wird es zu sagen, alles in Ordnung, gut, löschen Sie den Rest der Liste. Der Rest der Liste beginnt 9, und so werden wir nur warten Sie, bis Sie alle zu löschen, dass stuff, dann kommen Sie und löschen Sie mich. Gut 9 geht zu sagen, na ja, Ich bin nicht eine Null-Zeiger, Der Rest der Liste von hier so zu löschen. Und so versuchen und zu zerstören 13. 13, sagt, ich bin mir nicht Null-Zeiger, elbe ist, leitet sie den Schwarzen Peter zuschieben. 10 nicht Null-Zeiger, 10 enthält eine Null-Zeiger, aber 10 nicht selbst ein NULL-Zeiger gerade jetzt, und so ist es passiert den Schwarzen Peter zu. 

Und jetzt gibt es Punkte aufzulisten, es wirklich möchte darauf zu some-- wenn ich mehr Platz in dem Bild, es wäre, um einige zufällige Platz zeigen dass wir nicht wissen, was es ist. Es ist der Null-Zeiger, obwohl die Liste ist buchstäblich nun eingestellt, es ist Werte null. Es ist nach rechts innerhalb dieses roten Feld. Wir erreichten einen Null-Zeiger, so können wir aufhören, und wir sind fertig. 

Und so, dass lila Rahmen ist now-- bei der Anfang der stack--, die der aktive Frame ist, aber es geht. Wenn wir eine Null-Zeiger erreicht, Halt. Wir haben nichts zu tun, haben wir kann nicht frei einen Null-Zeiger, wir haben nicht jede malloc Raum, und so sind wir fertig. So dass Funktionsrahmen zerstört wird, und wir resume-- wir bauen, wo wir aufge mit der nächsthöheren ein, die ist dieser dunkelblauen Rahmen hier. So holen wir genau da, wo wir aufgehört haben. Wir löschen den Rest des Liste bereits, so jetzt sind wir gehen, um die aktuellen Knoten zu befreien. So, jetzt können wir diese Knoten zu befreien, und nun wir haben das Ende der Funktion erreicht. Und so, dass Funktionsrahmen zerstört wird, und wir holen Sie am hellblaue. 

So ist es says-- Ich habe bereits done-- Löschen der Rest der Liste, so befreien den aktuellen Knoten. Und nun die gelben Rahmen ist wieder an der Spitze des Stapels. Und so, wie Sie sehen, jetzt sind wir Zerstören der Liste von rechts nach links. 

Was wäre geschehen, wenn auch, wenn wir die Dinge in die falsche Richtung getan? Genau wie als wir versuchten, um ein Element hinzuzufügen. Wenn wir vermasselt die Kette, wenn wir nicht schließen Sie die Zeiger in der richtigen Reihenfolge, wenn wir nur befreit das erste Element, wenn wir nur befreit die Kopf der Liste, jetzt sind wir haben keine Möglichkeit, zu beziehen der Rest der Liste. Und so hätten wir verwaiste alles, wir hätten was ist rief ein Speicherverlust. Wenn Sie aus unserem Video erinnern auf dynamische Speicherzuweisung, das ist nicht sehr gute Sache. 

So, wie ich sagte, es sind mehrere Operationen dass wir verwenden, um zu arbeiten mit Liste effektiv verknüpft. Und Sie haben vielleicht bemerkt, ich eines weggelassen, Löschen eines einzelnen Elements aus einer verknüpften Liste. Der Grund, warum ich das getan habe ist es eigentlich ganz schwierig, wie Sie denken, zu löschen ein einzelnes Element aus einem einzeln verknüpften Liste. Wir müssen in der Lage zu überspringen sein etwas in der Liste, die bedeutet, dass wir auf eine point-- wir bekommen wollen diese node-- löschen aber um es so zu machen wir nicht verlieren alle Informationen, wir brauchen, um diese zu verbinden Knoten über hier, hier. 

So wohl habe ich das falsch in optischer Hinsicht. So dass wir am Anfang sind unsere Liste, sind wir durch fortgefahren wird, Wir wollen diesen Knoten zu löschen. Wenn wir einfach löschen, wir haben die Kette gebrochen. Dieser Knoten hier bezieht sich auf alles andere, sie enthält die Kette von hier an heraus. 

Also, was wir tatsächlich tun müssen, nachdem wir zu diesem Punkt, ist, müssen wir einen Schritt zurück, und verbinden Sie diesen Knoten über diesem Knoten, so können wir löschen der eine in der Mitte. Aber einfach verkettete Listen nicht geben uns einen Weg, um rückwärts zu gehen. Also müssen wir entweder zu halten zwei Zeiger, und verschieben Sie sie Art von off Schritt hinter andere, wie wir gehen, oder sich zu einem Punkt und senden Sie dann einen anderen Zeiger durch. Und wie Sie es sehen können kann ein wenig chaotisch. Glücklicherweise haben wir Ein anderer Weg, zu beschließen, wenn wir über die doppelt verkettete Listen zu sprechen. 

Ich bin Doug Lloyd, ist dies CS50.