[Musikwiedergabe] DOUG LLOYD: Alles klar. Also, wenn Sie gerade, dass Video-on einfach verkettete Listen leid, Ich ließ sie weg auf ein wenig ein Cliffhanger. Aber ich bin froh, dass Sie hier sind, um zu beenden die Geschichte von doppelt verketteten Listen. 

Also, wenn Sie von erinnern dass Video, sprachen wir wie einfach verknüpften Listen Sie besuchen unsere Fähigkeit, mit Informationen umzugehen wobei die Anzahl der Elemente, oder die Anzahl der Elemente in eine Liste können wachsen oder schrumpfen. Jetzt können wir behandeln so was, wo wir konnten nicht damit umgehen mit Arrays. 

Aber sie wissen von einem leiden kritischen Beschränkung, ist, dass mit einer einfach verknüpften Liste, die wir immer nur bewegen kann in einer einzigen Richtung durch die Liste. Und die einzige wirkliche Situation wobei das kann ein Problem werden, war, als wir wurden zu versuchen, ein einzelnes Element zu löschen. Und wir haben nicht einmal zu diskutieren, wie es geht in einer einfach verknüpften Liste in Pseudocode. Es ist sicherlich machbar, aber kann es ein bisschen wie ein Streit. Also, wenn Sie sich selbst zu finden in einer Situation, in der Sie versuchen, zu löschen sind einzelne Elemente aus der Liste oder es wird erforderlich sein dass Sie werden Löschen Einzelelemente aus Die folgende Liste enthält, möchten Sie vielleicht zu prüfen, mit einer doppelt verketteten Liste anstelle einer einfach verknüpften Liste. Weil doppelt verknüpfte Listen können Sie um sowohl vorwärts und rückwärts bewegen, durch die Liste statt nur vorwärts durch die list-- nur durch Zugabe von einem zusätzlichen Element um unsere Strukturdefinition die doppelt verkettete Liste Knoten. 

Auch wenn Sie nicht zu gehen Löschen werden einzelne Elemente vom list-- weil wir das Hinzufügen ein extra Feld, um unsere Struktur Definition, die Knoten selbst für doppelt verknüpfte Listen gehen, größer zu sein. Sie gehen zu nehmen mehr Byte Speicher. Und so, wenn das ist nicht etwas, Sie gehen zu müssen, um zu tun, könnten Sie sich entscheiden, es ist nicht wert, die Trade-off zu haben, um das extra Byte Speicher erforderlich für eine doppelt verknüpfte Liste, wenn Sie nicht sein werden, das Löschen einzelner Elemente. Aber sie sind auch cool für andere Dinge auch. 

Also wie gesagt, wir müssen nur hinzufügen, ein einziges Feld, um unsere Struktur definition-- diese Vorstellung eine vorherige Zeiger. Also mit einer einfach verknüpften Liste, die wir haben den Wert und die Next-Zeiger, so dass die doppelt verknüpfte Liste nur hat ein Weg, um rückwärts zu bewegen als auch. 

Jetzt in der einfach verknüpften Liste Video, sprachen wir über diese fünf der wichtigsten Dinge, die Sie benötigen zu sein der Lage zu tun, um mit verketteten Listen arbeiten. Und für die meisten von diesen ist die Tatsache, dass es eine doppelt verknüpfte Liste ist nicht wirklich ein großer Sprung. Wir können immer noch durch eine Suche nach gerade Vorwärtsbewegung von Anfang bis Ende. Wir können immer noch einen Knoten aus erstellen Luft, so ziemlich die gleiche Weise. Wir können Listen ziemlich löschen der gleichen Weise zu. Die einzigen Dinge, sind auf subtile Weise anders, wirklich, sind Einfügen neue Knoten in die Liste, und wir werden schließlich über das Löschen zu sprechen ein einzelnes Element aus der Liste als gut. Auch ziemlich die anderen drei sind wir nicht gehen, um über sie zu sprechen gerade jetzt, weil sie einfach sind sehr kleinere Verbesserungen auf den Ideen diskutiert in der einfach verknüpften Liste Video. 

Lassen Sie uns also legen Sie einen neuen Knoten in einer doppelt verketteten Liste. Wir sprachen über das tun dies für einfach verkettete Listen sowie, aber es gibt ein paar zusätzliche einholt doppelt verketteten Listen. Wurden [? vorbei?] in den Kopf des Liste hier und einige willkürlicher Wert, und wir wollen, um den neuen Kopf zu bekommen der Liste aus dieser Funktion. Deshalb ist es eine dllnode Sterne zurück. Also, was sind die Schritte? Sie sind wiederum sehr ähnlich auf einfach verkettete Listen mit einem zusätzlichen hinaus. Wir wollen Platz für eine neue zuordnet Knoten und überprüfen, um sicherzustellen, es ist gültig. Wir wollen, dass der Knoten zu füllen mit dem, was Informationen, die wir wollen in sie. Das letzte, was wir brauchen, um die do-- zusätzliche Sache, die wir tun müssen, rather-- ist es, die vorherige Zeiger beheben der alten Kopf der Liste. Denken Sie daran, dass, weil der doppelt verketteten Listen, können wir vorankommen und die backwards-- bedeutet, dass jeder Knoten zeigt tatsächlich zu zwei anderen Knoten statt nur einem. Und so müssen wir beheben der alte Kopf der Liste um rückwärts an den neuen Chef der Punkt der verknüpften Liste, die etwas nicht wir haben nicht vor zu tun. Und nach wie vor, wir haben nur eine Rück Zeiger auf die neue Spitze der Liste. 

So, hier ist eine Liste. Wir wollen in diese Liste einfügen 12. Bemerkt, daß das Diagramm ist etwas anders. Jeder Knoten enthält drei fields-- Daten und eine nächste Zeiger in rot, und eine vorherige Zeiger in blau. Nichts kommt, bevor die 15 Knoten, so seine früheren Zeiger ist null. Es ist der Anfang der Liste. Es gibt nichts, bevor es. Und nichts kommt nach der 10 Knoten und so ist es nächste Zeiger NULL ist als gut. 

Lassen Sie uns also zu dieser Liste hinzufügen 12. Wir müssen [unverständlich] Raum für den Knoten. Wir stellen 12 darin. Und dann wieder, wir müssen wirklich sein, Achten Sie darauf, um die Kette zu brechen. Wir wollen die neu anordnen Zeiger in der richtigen Reihenfolge. Und manchmal, dass vielleicht mean-- wie wir vor allem sehen, mit delete--, die wir tun müssen, einige redundanten Zeiger, aber das ist OK. 

Also, was wollen wir zuerst tun? Ich würde das empfehlen Dinge, die Sie wahrscheinlich zu tun, um die Zeiger der 12 zu füllen Knoten, bevor Sie berühren alle anderen. Also, was ist 12 als nächstes zeigen auf? 15. Was kommt vor dem 12.? Gar nichts. Jetzt haben wir ausgefüllt haben die Zusatzinformationen in 12 so hat es Zurück, Weiter und Wert. 

Jetzt können wir diese zusätzliche 15-- Schritt wurden wir about-- wir sprechen können 15 Punkt wieder auf 12. Und jetzt können wir den Kopf zu bewegen der verknüpften Liste, um auch 12 sein. So ist es ziemlich ähnlich, was wir wurden mit einfach verknüpften Listen machen, mit Ausnahme der zusätzlichen Schritt Anschluss des alten Kopf der Liste zurück zu den neuen Kopf der Liste. 

Lassen Sie uns nun endgültig zu löschen ein Knoten aus einer verketteten Liste. Also lassen Sie uns sagen, wir haben eine andere Funktion, ist das Finden eines Knotens wir löschen möchten und hat uns einen Zeiger auf Gewissheit angegebn der Knoten, die wir löschen möchten. Wir wissen nicht einmal sagen, die need-- Kopf ist immer noch global deklariert. Wir haben nicht den Kopf brauchen hier. All diese Funktion tut, wir haben fanden einen Zeiger auf den Knoten genau wir wollen loswerden. Lassen Sie es loswerden. Es ist viel einfacher, mit doppelt verketteten Listen. First-- es ist eigentlich nur ein paar Dinge. Wir müssen nur fix die umliegende Knoten 'Zeiger, so dass sie zu überspringen der Knoten wir wollen, um zu löschen. Und dann können wir diesen Knoten zu löschen. Also noch einmal, wir sind gerade dabei durch hier. Wir haben offenbar beschlossen, dass wir den Knoten X löschen möchten Und wieder, was ich Dabei hier-- vom way-- ist ein allgemeiner Fall für ein Knoten, der in der Mitte ist. Es gibt ein paar zusätzliche Einschränkungen, die Sie beachten müssen, wenn Sie das Löschen der Anfang der Liste oder ganz am Ende der Liste. Es gibt ein paar spezielle Grenzfälle mit dort behandeln. 

So funktioniert das zum Löschen jeder Knoten in der Mitte des list-- eine, ein berechtigtes Zeiger vorwärts und eine legitime Zeiger rückwärts, legitime Zurück und Weiter-Zeiger. Auch wenn Sie gerade arbeiten wobei die Enden Sie brauchen, um diejenigen zu behandeln etwas anders, und wir sind nicht zu gehen reden über das jetzt. Aber man kann wohl herauszufinden, was benötigt um nur durch die Beobachtung dieses Video durchgeführt werden. 

Also haben wir getrennt habe X. X ist der Knoten Wir wollen aus der Liste löschen. Was machen wir? Zuerst müssen wir neu anordnen die außerhalb von Zeigern. Wir müssen neu anordnen 9 ist neben über 13 überspringen und weisen auf die 10-- ist, was wir gerade getan haben. Und wir müssen auch neu anordnen 10 die vorherige bis zu 9 statt auf 13 Punkt. 

Also noch einmal, das war die Diagramm für den Anfang. Dies war unser Kette. Wir müssen über 13 überspringen, aber wir müssen auch zu bewahren die Integrität der Liste. Wir wollen nicht zu einem zu verlieren Informationen in beide Richtungen. Also müssen wir ordnen die Zeiger genau so dass wir die Kette nicht brechen überhaupt. 

So können wir sagen 9 Next-Zeiger Punkte an der gleichen Stelle dass dreizehn Next Zeiger verweist jetzt. Weil wir irgendwann gehen, um mehr als 13 überspringen zu wollen. Also überall dort, wo mit 13 Punkten weiter, Sie soll neun bis es stattdessen zeigen. So ist das also. Und dann, wo immer 13 Punkte zurück zu, was auch immer vor 13 kommt, wir wollen, dass 10 zu Punkt auf, dass anstelle von 13. Nun beachtet, wenn Sie folgen die Pfeile, können wir 13 fallen ohne wirklich zu verlieren, keine Informationen. Wir haben die Integrität der Liste gehalten wird, Bewegen sowohl vorwärts und rückwärts. Und dann können wir einfach so von reinigen Sie es oben ein wenig durch Ziehen der Liste zusammen. So neu arrangiert wir die Zeiger auf beiden Seiten. Und dann befreiten wir die X Knoten, 13 enthalten sind, und wir haben die Kette nicht brechen. Also haben wir gut. 

Abschließender Hinweis hier auf verkettete Listen. Also sowohl einzeln-und doppelt verketteten Listen, wie wir gesehen haben, Unterstützung wirklich effizient Insertion und Löschen von Elementen. Sie können ziemlich viel zu tun es in konstanter Zeit. Was haben wir zu tun, um zu löschen ein Element nur eine Sekunde vor? Wir zogen einen Zeiger. Wir zogen einen anderen Zeiger. Wir befreiten X-- dauerte drei Operationen. Es dauert immer drei Operationen zu löschen Sie diesen node--, um einen Knoten zu befreien. 

Wie können wir ein? Nun, wir sind einfach immer Heften auf Beginn wenn wir effizient Einfügen. Also müssen wir rearrange-- je nachdem, ob es eine einfach oder doppelt verknüpfte Liste, könnten wir zu drei tun müssen oder vier Operationen max. Aber noch einmal, es ist immer drei oder vier. Es spielt keine Rolle, wie viele Elemente sind in unserer Liste, es ist immer drei oder vier operations-- wie Löschen ist immer drei oder vier Operationen. Es ist konstante Zeit. Also das ist wirklich toll. 

Bei Arrays wurden wir tun so etwas wie Insertion Sort. Sie erinnern sich vielleicht, dass die Insertion Art ist keine Konstante Algorithmus. Es ist eigentlich ziemlich teuer. Also das ist viel besser für das Einfügen. Aber als ich in den genannten einfach verknüpften Liste Video, wir haben eine Kehrseite auch hier richtig gemacht? Wir haben die Fähigkeit, verlorene zufällig auf Elemente. Wir können nicht sagen, ich will Element Nummer vier oder Elementnummer 10 einer verketteten Liste So wie wir können, zu tun, dass mit einer Reihe oder wir können einfach direkt Index in Elements unser Angebot. 

Und so versuchen, ein zu finden Element einer verketteten list-- wenn Suche ist important-- kann nun die lineare Zeit. Da die Liste wird immer länger, es könnte eine zusätzliche Schritt zu machen für jedes einzelne Element in der Liste in um zu finden, was wir suchen. Also gibt es Kompromisse. Es ist ein bisschen wie ein Profi und con Element. 

Und doppelt verknüpfte Listen sind nicht letzten Art von Datenstruktur-Kombination dass wir darüber zu sprechen, wobei alle grundlegenden Gebäude Blöcke von C eine Zusammenstellung. Denn in der Tat können wir sogar besser als dies tun um eine Datenstruktur zu schaffen, dass Sie könnten durch zu suchen sein, in konstanter Zeit auch. Aber mehr dazu in einem anderen Video. 

Ich bin Doug Lloyd. Dies ist CS50.