[Powered by Google Translate] Bei der Programmierung müssen wir oft Listen von Werten darstellen, wie die Namen der Schüler in einem Abschnitt oder deren Noten auf dem neuesten Quiz. 

In der Sprache C, erklärte Arrays verwendet werden können um Listen speichern. Es ist einfach, die Elemente einer Liste aufzuzählen gespeichert in einem Array, und wenn Sie den Zugriff auf oder ändern das i-te Listenelement für einige beliebiger Index I, Das kann in konstanter Zeit durchgeführt werden, aber Arrays haben auch Nachteile. 

Wenn wir ihnen erklären, wir müssen sagen, vorne wie groß sie sind, das heißt, wie viele Elemente sie speichern können und wie groß diese Elemente sind, die durch deren Art bestimmt. Zum Beispiel, int arr (10) können 10 Einträge speichern das sind die Größe eines int. 

Wir können nicht ändern eines Arrays der Größe nach Erklärung. Wir haben ein neues Array machen, wenn wir mehr Elemente speichern möchten. Der Grund dafür Einschränkung besteht darin, dass unsere Programm speichert das gesamte Array als zusammenhängender Block arbeiten. Sagen, das ist der Puffer, wo wir in unserem Array gespeichert. Es können auch andere Variablen befindet sich direkt neben dem Array im Speicher, so können wir nicht nur das Array größer. 

Manchmal möchten wir die Array-schnellen Datenzugriff Geschwindigkeit Handel für etwas mehr Flexibilität. Geben Sie die verknüpfte Liste, weitere grundlegende Datenstruktur Sie ist vielleicht nicht so vertraut sind. Auf einer hohen Ebene, eine verkettete Liste speichert Daten in einer Folge von Knoten daß miteinander mit Links verbunden sind, daher der Name "verketteten Liste." Wie wir sehen werden, ist dieser Unterschied im Design führt zu unterschiedlichen Vor-und Nachteile als ein Array. 

Hier einige C-Code für eine sehr einfache verknüpfte Liste von Zahlen. Sie können sehen, dass wir jeden Knoten vertreten in der Liste als eine Struktur, welche 2 Dinge enthält, eine ganze Zahl zu speichern als 'val' und einen Link zu dem nächsten Knoten in der Liste die wir vertreten als Zeiger namens "Weiter". Auf diese Weise können wir den gesamten Liste mit nur einem Zeiger auf den ersten Knoten und dann können wir folgen die nächsten Zeiger dem zweiten Knoten, dem dritten Knoten, dem vierten Knoten, und so weiter, bis wir an das Ende der Liste zu gelangen. 

Sie könnten in der Lage sein ein Vorteil, dies zu sehen über die statische Array-Struktur - mit einer verketteten Liste, wir brauchen nicht einen großen Teil des Speichers insgesamt. Der erste Knoten der Liste könnte an dieser Stelle in Erinnerung zu leben, und der zweite Knoten könnte den ganzen Weg hierher sein. Wir können alle Knoten zu erhalten, egal wo im Speicher sind, , weil ab dem 1. Knoten, wobei jeder Knoten nächste Zeiger sagt uns genau, wo zum nächsten gehen. 

Darüber hinaus haben wir nicht zu sagen, bis vor wie groß eine verlinkte Liste wird die Art, wie wir mit statischen Arrays, da können wir halten das Hinzufügen von Knoten zu einer Liste Solange es Raum irgendwo im Speicher zum neuen Knoten. Daher sind verkettete Listen einfach zu dynamisch ändern. Sprich, später im Programm haben wir weitere Knoten hinzufügen müssen in unsere Liste. Um einen neuen Knoten in unsere Liste einzufügen on the fly, alles, was wir tun müssen, ist Speicher für diesen Knoten plop in dem Datenwert, und dann legen Sie sie, wo wir durch Einstellung der entsprechenden Zeigern wollen. 

Zum Beispiel, wenn wir wollten, um einen Knoten zwischen platzieren die zweite und dritte Knoten der Liste  hätten wir nicht die zweite oder dritte Knoten überhaupt zu bewegen. Sagen, dass wir das Einfügen dieses rote Knoten. Alles, was wir zu tun haben möchte, ist die neue Knoten nächste Zeiger gesetzt um zu der dritten Knotenpunkt und dann verkabeln des zweiten Knotens nächste Zeiger bis zum neuen Knotenpunkt. So können wir unsere Listen on the fly ändern da unsere Computer nicht Indexierung verlassen, sondern auf die Verknüpfung mit Zeigern, um sie zu speichern. 

Allerdings verknüpft ein Nachteil von Listen ist, dass, im Gegensatz zu einem statischen Array, Der Computer kann nicht nur auf die Mitte der Liste zu springen. Da der Computer muss jeder Knoten in der verketteten Liste zu besuchen um zum nächsten zu gelangen, es wird länger dauern, einen bestimmten Knoten zu finden als es in einem Array. Zu durchqueren die gesamte Liste braucht Zeit proportional der Länge der Liste, oder O (n) in asymptotischen Notation. Im Durchschnitt erreichen alle Knoten Auch braucht Zeit proportional zu n. 

Lassen Sie uns nun tatsächlich Code schreiben das funktioniert mit verknüpften Listen. Lassen Sie uns sagen, wir wollen eine verknüpfte Liste von Zahlen. Wir können einen Knoten in unserer Liste wieder vertreten als struct mit 2 Feldern, ein Integer-Wert namens "val" und ein nächster Zeiger auf den nächsten Knoten in der Liste. Nun, es scheint einfach genug. 

Lassen Sie uns sagen, wir wollen eine Funktion schreiben die Traversen die Liste ein und druckt die Wert in den letzten Knoten der Liste gespeichert. Nun, das heißt, wir müssen alle Knoten in der Liste durchlaufen um den letzten zu finden, aber da wir nicht das Hinzufügen oder etwas zu löschen, wollen wir nicht zu ändern Die innere Struktur der nächste Zeiger in der Liste. 

Also, wir einen Zeiger speziell brauchen für Traversierung die nennen wir "Crawler". Es wird durch alle Elemente der Liste kriechen indem Sie die Kette der nächsten Zeiger. Alle uns gespeichert ist ein Zeiger auf den ersten Knoten, oder "Kopf" der Liste. Kopf zeigt auf den ersten Knoten. Es ist vom Typ Zeiger-zu-Knoten. 

Um die tatsächliche ersten Knoten in der Liste zu bekommen, Wir haben zu dereferenzieren diesen Zeiger, aber bevor wir es dereferenzieren, müssen wir überprüfen, wenn sich der Zeiger null erste. Wenn es null ist, ist die Liste leer, und wir sollten Sie auch eine Nachricht, die, weil die Liste leer ist, es gibt keine letzte Knoten. Aber, sagen wir mal die Liste nicht leer ist. Wenn es nicht ist, dann sollten wir uns durch die gesamte Liste zu kriechen bis wir zu dem letzten Knoten der Liste und wie können wir sagen, ob wir bei der letzten Knoten in der Liste suchen? 

Nun, wenn eines Knotens nächste Zeiger null, Wir wissen, dass wir am Ende seit der letzten nächste Zeiger hätte keine nächsten Knoten in der Liste, um zu zeigen. Es ist gute Praxis, immer der letzte Knoten der nächste Zeiger mit null initialisiert eine standardisierte Eigenschaft, die uns warnt, wenn wir das Ende der Liste erreicht haben müssen. 

Also, wenn Crawler → weiter null ist, daran erinnern, dass der Pfeil-Syntax eine Abkürzung für Dereferenzierung ist ein Zeiger auf eine struct, dann Zugriff auf ihre nächste Feld entspricht der misslichen: (* Crawler). Nächsten. Nachdem wir den letzten Knoten gefunden, Wir wollen Crawler → val drucken, der Wert in dem aktuellen Knoten die wir kennen, ist das letzte. Andernfalls, wenn wir noch nicht auf dem letzten Knoten in der Liste, Wir müssen weiter an den nächsten Knoten in der Liste und prüfen, ob das ist das letzte. Um dies zu tun, setzen wir einfach unser Crawler Zeiger Um zu den aktuellen Knotens nächsten Wert darauf, das heißt, der nächste Knoten in der Liste. Dies wird getan, indem Crawler = Crawler → weiter. Dann wiederholen wir diesen Prozess mit einer Schleife zum Beispiel bis wir den letzten Knoten. So, zum Beispiel, wenn Crawler wurde Kopf nach, setzen wir Crawler zu Crawler → weiter zeigen, das ist der gleiche wie der nächste Feld des ersten Knotens. So, jetzt unser Crawler auf den zweiten Knoten zeigt, und wiederum wiederholen wir dies mit einer Schleife, bis wir den letzten Knoten gefunden, das heißt, wo der Knoten nächsten Zeiger zeigt auf null. Und da haben wir es, haben wir den letzten Knoten in der Liste gefunden, und um seinen Wert zu drucken, verwenden wir nur Crawler → val. 

Verfahrgeschwindigkeit ist nicht so schlimm, aber was ist das Einfügen? Lets sagen, wir wollen eine ganze Zahl in die vierte Position einzufügen in einer Integer-Liste. Das heißt zwischen den 3. und 4. aktuellen Knoten. Auch hier haben wir die Liste nur zu durchqueren bekommen die dritte Element, die wir nach dem Einsetzen sind. So schaffen wir einen Crawler Zeiger wieder auf die Liste zu durchlaufen, überprüfen, ob unser Kopf Zeiger ist null, und wenn es nicht ist, zeigen unsere Crawler Zeiger auf dem Head-Knoten. Also, wir sind auf dem ersten Element. Wir müssen vorwärts gehen 2 weitere Elemente, bevor wir einfügen können, so können wir eine for-Schleife verwenden int i = 1; i <3; i + + und in jeder Iteration der Schleife, voranzutreiben unser Crawler Zeiger vorwärts mit 1 Knoten durch Prüfen, ob der aktuelle Knoten der nächsten Feld null ist, und wenn es nicht ist, bewegen unsere Crawler Zeiger auf den nächsten Knoten indem sie gleich des aktuellen Knotens nächste Zeiger. So, da unsere for-Schleife, sagt das zu tun zweimal, wir haben den dritten Knoten erreicht, und einmal unser Crawler Zeiger hat den Knoten erreicht nach die wollen wir unsere neuen Integer einzufügen, Wie können wir eigentlich nicht das Einfügen? 

Nun, unsere neue Zahl in die Liste eingefügt werden als Teil seiner eigenen Knoten struct, da dies eigentlich eine Sequenz von Knoten. Also, lasst uns einen neuen Zeiger auf Knoten namens 'new_node " und setzen Sie ihn in den Speicher verweisen, dass wir nun die Möglichkeit auf dem Heap für den Knoten selbst, und wie viel Speicher brauchen wir zu vergeben? Nun, in der Größe eines Knotens, und wir wollen ihre val Feld auf die Zahl, die wir einfügen wollen eingestellt. Lassen Sie uns sagen, 6. Nun enthält der Knoten unserer Integer-Wert. Es ist auch ratsam, des neuen Knotens nächste Feld zu initialisieren darauf auf null aber was nun? 

Wir müssen die innere Struktur der Liste zu ändern und die nächsten Zeiger in der Liste der vorhandenen enthalten Dritte und vierte Knoten. Da die nächsten Zeiger bestimmt die Reihenfolge der Liste, und da wir das Einfügen unserer neuen Knoten direkt in die Mitte der Liste, kann es ein bisschen schwierig. Dies liegt daran, denkt daran, unsere Computer kennt nur die Position der Knoten in der Liste wegen der nächsten Zeiger in den vorherigen Knoten gespeichert. Also, wenn wir jemals aus den Augen verloren einem dieser Orte, sagen, indem einer der nächsten Zeiger in unserer Liste zum Beispiel, sagen wir, verändert der dritte Knoten nächsten Feld bis zu einem gewissen Knoten über hier zu zeigen. Wir hatten kein Glück, denn würden wir nicht eine Idee haben, wo der Rest der Liste zu finden, und das ist natürlich wirklich schlecht. Also, wir haben wirklich vorsichtig sein über die Reihenfolge in denen wir manipulieren unsere nächsten Zeiger beim Einführen. 

Also, um dies zu vereinfachen, sagen wir, dass unser erstes 4-Knoten heißen A, B, C und D, mit den Pfeilen, die die Kette von Zeigern , die die Knoten verbinden. Also müssen wir unsere neuen Knoten einfügen im zwischen den Knoten C und D. Es ist wichtig, um sie in der richtigen Reihenfolge zu tun, und ich werde Ihnen zeigen, warum. 

Lasst uns an der falschen Weg, um es zuerst tun suchen. Hey, kennen wir die neuen Knoten zu kommen, nachdem C rechts, also lasst uns gesetzt C der nächste Zeiger zeigen soll new_node. Alles klar, scheint okay, wir haben nur zu Ende zu bringen nun durch Damit ist das neue Knoten nächste Zeiger Punkt D, aber warten, wie können wir das tun? Das einzige, was uns sagen konnte, wo D war, wurde der nächste Zeiger zuvor in C gespeichert, aber wir schrieben den Zeiger auf den neuen Knotenpunkt, so haben wir nicht mehr eine Ahnung, wo D ist in Erinnerung, und wir haben den Rest der Liste verloren. Überhaupt nicht gut. 

Also, wie machen wir das richtig verstanden? Zum einen weisen die neuen Knoten der nächsten Zeiger auf D. Nun werden sowohl die neuen Knotens und C der nächste Zeiger sind mit dem gleichen Knoten, D weisende, aber das ist in Ordnung. Jetzt können wir zeigen C der nächste Zeiger auf den neuen Knoten. Also haben wir diese ohne Datenverlust durchgeführt. In Code ist C der aktuelle Knoten dass die Traversierung Zeiger Crawler verweist, und D wird durch den Knoten, auf die durch den aktuellen Knotens nächste Feld repräsentiert, oder Crawler → weiter. Also, wir zunächst des neuen Knotens nächste Zeiger zu Crawler → weiter zeigen, auf die gleiche Weise haben wir gesagt new_node der nächste Zeiger sollte weisen auf D in der Abbildung. Dann, können wir des aktuellen Knotens nächste Zeiger auf unserer neuen Knoten so wie wir warten, bis Punkt C in der Zeichnung new_node hatte. Jetzt ist alles in Ordnung, und wir nicht verlieren den Überblick über alle Daten, und wir konnten nur aufkleben unserem neuen Knotens in der Mitte der Liste ohne Umbau der ganzen Sache oder sogar verschieben alle Elemente die Art und Weise würden wir mit einem festen Array der Länge gehabt haben. 

So sind verkettete Listen eine grundlegende, aber wichtige dynamische Datenstruktur die haben beide Vor-und Nachteile gegenüber Arrays und anderen Datenstrukturen, und wie es oft der Fall, in der Informatik, ist es wichtig zu wissen, wann man jedes Werkzeug verwendet, so können Sie abholen das richtige Werkzeug für den richtigen Job. 

Für weitere Übungen versuchen, schriftlich Funktionen Löschen von Knoten aus einer verketteten Liste - erinnern, vorsichtig zu sein über die Reihenfolge, in der Sie neu anordnen Ihren nächsten Zeiger um sicherzustellen, dass Sie nicht verlieren ein Stück Ihrer Liste - oder eine Funktion, um die Knoten in einer verknüpften Liste zählen, oder eine lustige ein, um die Reihenfolge der alle Knoten in einer verknüpften Liste rückgängig zu machen. 

Mein Name ist Jackson Steinkamp, ​​ist dies CS50.