Informationen sind überall um uns herum.

In der Welt der Software ist die Art und Weise, wie wir unsere Informationen organisieren, die halbe Miete. Hier ist jedoch die Sache: Es gibt so viele Möglichkeiten , ein Problem zu lösen. Und wenn es um die Organisation unserer Daten geht, gibt es viele Tools, die für diesen Job geeignet sind. Der Trick besteht darin, zu wissen, welches Tool das richtige ist .

Unabhängig davon, in welcher Sprache wir mit dem Codieren beginnen, sind Datenstrukturen eines der ersten Dinge, auf die wir stoßen. Dies sind die verschiedenen Arten, wie wir unsere Daten organisieren können. Variablen , Arrays , Hashes und Objekte sind alle Arten von Datenstrukturen. Dies sind jedoch immer noch nur die Spitze des Eisbergs, wenn es um Datenstrukturen geht. Es gibt noch viel mehr, von denen einige sehr kompliziert klingen, je mehr Sie davon hören.

Eines dieser komplizierten Dinge waren für mich immer verknüpfte Listen . Ich kenne verknüpfte Listen seit einigen Jahren, kann sie aber nie ganz im Kopf behalten. Ich denke nur wirklich an sie, wenn ich mich auf ein technisches Interview vorbereite (oder manchmal mitten in diesem), und jemand fragt mich nach ihnen. Ich werde ein wenig recherchieren und denken, dass ich verstehe, worum es geht, aber nach ein paar Wochen vergesse ich sie wieder. Das Ganze ist ziemlich ineffizient und alles ergibt sich aus der Tatsache, dass ich weiß, dass sie existieren, aber ich verstehe sie nicht grundlegend ! Es ist also Zeit, das zu ändern und die Frage zu beantworten: Was um alles in der Welt ist überhaupt eine verknüpfte Liste?

Lineare Datenstrukturen

Wenn wir die Grundlagen verknüpfter Listen wirklich verstehen wollen, ist es wichtig, dass wir darüber sprechen, um welche Art von Datenstruktur es sich handelt.

Ein Merkmal von verknüpften Listen ist, dass es sich um lineare Datenstrukturen handelt , was bedeutet, dass es eine Sequenz und eine Reihenfolge gibt, wie sie erstellt und durchlaufen werden. Wir können uns eine lineare Datenstruktur wie ein Hopscotch-Spiel vorstellen : Um an das Ende der Liste zu gelangen, müssen wir alle Elemente in der Liste der Reihe nach oder nacheinander durchgehen . Lineare Strukturen sind jedoch das Gegenteil von nichtlinearen Strukturen. In nichtlinearen Datenstrukturen müssen Elemente nicht in der richtigen Reihenfolge angeordnet werden, was bedeutet, dass wir die Datenstruktur nicht sequentiell durchlaufen können .

Wir werden es vielleicht nicht immer realisieren, aber wir alle arbeiten jeden Tag mit linearen und nichtlinearen Datenstrukturen! Wenn wir unsere Daten in Hashes (manchmal auch als Wörterbücher bezeichnet ) organisieren, implementieren wir eine nichtlineare Datenstruktur. Bäume und Grafiken sind auch nichtlineare Datenstrukturen, die wir auf unterschiedliche Weise durchlaufen, aber wir werden später im Jahr ausführlicher darauf eingehen.

Wenn wir Arrays in unserem Code verwenden, implementieren wir ebenfalls eine lineare Datenstruktur! Es kann hilfreich sein, sich Arrays und verknüpfte Listen so vorzustellen, wie wir Daten sequenzieren. In beiden Strukturen ist Ordnung wichtig . Aber was unterscheidet Arrays und verknüpfte Listen?

Speicherverwaltung

Das größte Unterscheidungsmerkmal zwischen Arrays und verknüpften Listen ist die Art und Weise, wie sie Speicher in unseren Maschinen verwenden. Diejenigen von uns, die mit dynamisch typisierten Sprachen wie Ruby, JavaScript oder Python arbeiten, müssen nicht darüber nachdenken, wie viel Speicher ein Array benötigt, wenn wir unseren Code täglich schreiben, da es am Ende mehrere Abstraktionsebenen gibt Wir müssen uns überhaupt nicht um die Speicherzuweisung kümmern.

Das heißt aber nicht, dass keine Speicherzuweisung stattfindet! Abstraktion ist keine Magie, sondern nur die Einfachheit, Dinge zu verstecken, die Sie nicht ständig sehen oder behandeln müssen. Selbst wenn wir beim Schreiben von Code nicht über die Speicherzuweisung nachdenken müssen, müssen wir auf die rudimentäre Ebene gelangen, wenn wir wirklich verstehen wollen, was in einer verknüpften Liste vor sich geht und was sie leistungsfähig macht.

Wir haben bereits über binäre gelernt haben und wie Daten werden aufgeteilt in Bits und Bytes. So wie Zeichen, Zahlen, Wörter und Sätze Speicherbytes benötigen, um sie darzustellen, so tun dies auch Datenstrukturen.

Wenn ein Array erstellt wird, benötigt es eine bestimmte Menge an Speicher. Wenn wir 7 Buchstaben hätten, die wir in einem Array speichern müssten, würden wir 7 Bytes Speicher benötigen, um dieses Array darzustellen. Aber wir würden all diesen Speicher in einem zusammenhängenden Block brauchen . Das heißt, unser Computer müsste 7 Bytes Speicher frei finden, ein Byte neben dem anderen, alles zusammen an einem Ort.

Wenn andererseits eine verknüpfte Liste erstellt wird, benötigt sie nicht 7 Byte Speicher an einem Ort. Ein Byte könnte irgendwo leben, während das nächste Byte an einem anderen Ort im Speicher gespeichert werden könnte! Verknüpfte Listen müssen keinen einzigen Speicherblock belegen. Stattdessen kann der von ihnen verwendete Speicher überall verteilt sein .

Der grundlegende Unterschied zwischen Arrays und verkettete Listen ist , dass Arrays sind statische Datenstrukturen , während die verkettete Listen sind dynamische Datenstrukturen . Für eine statische Datenstruktur müssen alle Ressourcen beim Erstellen der Struktur zugewiesen werden. Dies bedeutet, dass selbst wenn die Struktur größer oder kleiner werden soll und Elemente hinzugefügt oder entfernt werden sollen, immer eine bestimmte Größe und Speichermenge benötigt wird. Wenn einer statischen Datenstruktur mehr Elemente hinzugefügt werden müssen und nicht genügend Speicher vorhanden ist, müssen Sie beispielsweise die Daten dieses Arrays kopieren und mit mehr Speicher neu erstellen, damit Sie Elemente hinzufügen können es.

Andererseits kann eine dynamische Datenstruktur im Speicher schrumpfen und wachsen. Es muss keine festgelegte Speichermenge zugewiesen werden, um zu existieren, und seine Größe und Form können sich ändern, und die benötigte Speichermenge kann sich ebenfalls ändern.

Inzwischen können wir bereits einige wesentliche Unterschiede zwischen Arrays und verknüpften Listen feststellen. Dies wirft jedoch die Frage auf: Was ermöglicht es einer verknüpften Liste, ihren Speicher überall zu verteilen? Um diese Frage zu beantworten, müssen wir uns ansehen, wie eine verknüpfte Liste aufgebaut ist.

Teile einer verknüpften Liste

Eine verknüpfte Liste kann klein oder groß sein, aber unabhängig von der Größe sind die Teile, aus denen sie besteht, eigentlich ziemlich einfach. Eine verknüpfte Liste besteht aus einer Reihe von Knoten , die die Elemente der Liste sind.

Der Ausgangspunkt der Liste ist eine Referenz auf den ersten Knoten, der als Kopf bezeichnet wird . Fast alle verknüpften Listen müssen einen Kopf haben, da dies praktisch der einzige Einstiegspunkt in die Liste und alle ihre Elemente ist. Ohne diesen würden Sie nicht wissen, wo Sie anfangen sollen! Das Ende der Liste ist kein Knoten, sondern ein Knoten, der auf null zeigt , oder ein leerer Wert.

Ein einzelner Knoten ist auch ziemlich einfach. Es besteht nur aus zwei Teilen: Daten oder den Informationen, die der Knoten enthält, und einem Verweis auf den nächsten Knoten .

Wenn wir uns darum kümmern können, sind wir auf halbem Weg. Die Art und Weise, wie Knoten funktionieren, ist sehr wichtig und sehr leistungsfähig und kann wie folgt zusammengefasst werden:

Ein Knoten weiß nur, welche Daten er enthält und wer sein Nachbar ist.

Ein einzelner Knoten weiß nicht, wie lang die verknüpfte Liste ist, und er weiß möglicherweise nicht einmal, wo sie beginnt oder wo sie endet. Ein Knoten befasst sich nur mit den Daten, die er enthält, und auf welchen Knoten sein Zeiger verweist - auf den nächsten Knoten in der Liste.

Und das ist der Grund , warum eine verknüpfte Liste keinen zusammenhängenden Speicherblock benötigt. Da ein einzelner Knoten die „Adresse“ oder einen Verweis auf den nächsten Knoten hat, müssen sie nicht direkt nebeneinander leben, wie es die Elemente in einem Array tun müssen. Stattdessen können wir uns einfach darauf verlassen, dass wir unsere Liste durchlaufen können, indem wir uns auf die Zeigerreferenzen zum nächsten Knoten stützen. Dies bedeutet, dass unsere Maschinen keinen einzelnen Speicherblock blockieren müssen, um unsere Liste darzustellen.

Dies ist auch die Erklärung dafür, warum verknüpfte Listen während der Ausführung eines Programms dynamisch wachsen und schrumpfen können. Das Hinzufügen oder Entfernen eines Knotens mit einer verknüpften Liste ist so einfach wie das Neuanordnen einiger Zeiger, anstatt über die Elemente eines Arrays zu kopieren! Es gibt jedoch auch einige Nachteile von verknüpften Listen, die ich Ihnen noch nicht erwähne - aber mehr dazu in der nächsten Woche.

Im Moment werden wir uns nur daran erfreuen, wie cool verknüpfte Listen sind!

Listen für alle Formen und Größen

Auch wenn die Teile einer verknüpften Liste nicht ändern, die Art und Weise , dass wir unsere verkettete Listen strukturieren kann ganz unterschiedlich sein. Wie die meisten Dinge in der Software kann je nach dem Problem, das wir lösen möchten, eine Art von verknüpften Listen ein besseres Werkzeug für den Job sein als eine andere.

Einfach verknüpfte Listen sind die einfachste Art von verknüpften Listen, die ausschließlich darauf beruhen, dass sie nur in eine Richtung gehen. Es gibt eine einzelne Spur , in der wir die Liste durchlaufen können. Wir beginnen an dem Kopfknoten, und von der Wurzel bisder Traverse letzten Knoten, der an einem leeren endetNullwert.

Aber so wie ein Knoten auf seinen nachfolgenden Nachbarknoten verweisen kann, kann er auch einen Referenzzeiger auf seinen vorhergehenden Knoten haben! Dies wird als doppelt verknüpfte Liste bezeichnet , da in jedem Knoten zwei Referenzen enthalten sind: eine Referenz auf den nächsten Knoten sowie den vorherigen Knoten. Dies kann hilfreich sein, wenn wir unsere Datenstruktur nicht nur in einer einzelnen Spur oder Richtung, sondern auch rückwärts durchlaufen möchten.

Wenn wir beispielsweise zwischen einem Knoten und dem vorherigen Knoten springen möchten, ohne zum Anfang der Liste zurückkehren zu müssen , wäre eine doppelt verknüpfte Liste eine bessere Datenstruktur als eine einfach verknüpfte Liste. Alles erfordert jedoch Speicherplatz und Speicher. Wenn unser Knoten also zwei Referenzzeiger anstelle von nur einem speichern müsste, wäre dies eine andere zu berücksichtigende Sache.

Eine zirkuläre verknüpfte Liste ist insofern etwas seltsam, als sie nicht mit einem Knoten endet, der auf einen Nullwert zeigt. Stattdessen hat es einen Knoten, der als wirkt tail der Liste (anstatt der herkömmlichen Kopfknoten), und der Knoten nach dem Endknoten ist der Anfang der Liste. Diese Organisationsstruktur macht es wirklich einfach , etwas zu Ende der Liste hinzuzufügen, weil Sie es an dem durchqueren können beginnen Schwanz Knoten, als das erste Element und letztes Element Punkt zueinander. Zirkular verknüpfte Listen können wirklich verrückt werden, weil wir sowohl eine einfach verknüpfte Liste als auch eine doppelt verknüpfte Liste in eine zirkular verknüpfte Liste verwandeln können !

Aber egal wie kompliziert eine verknüpfte Liste ist, wenn wir uns an die Grundlagen eines Knotens erinnern können und wie er funktioniert und wie die verschiedenen Zeigerreferenzen in unserer Liste strukturiert sind, gibt es keine verknüpfte Liste, die wir nicht angehen können!

Nächste Woche, in Teil 2 dieser Serie, werden wir uns mit der Raum-Zeit-Komplexität verknüpfter Listen und dem Vergleich mit ihrem Cousin, dem Array, befassen. Ich verspreche, dass es tatsächlich viel mehr Spaß macht, als es sich anhört!

Ressourcen

Wenn Sie verknüpfte Listen für super cool halten, lesen Sie diese hilfreichen Ressourcen.

1. Unterschiede zwischen Arrays und verknüpften Listen , Damien Wintour
2. Datenstrukturen: Arrays vs Linked Lists , mycodeschool
3. Verknüpfte Listen: Die Grundlagen , Dr. Edward Gehringer
4. Einführung in verknüpfte Listen , Dr. Victor Adamchik
5. Datenstrukturen und Implementierungen , Dr. Jennifer Welch
6. Statische Datenstrukturen vs. dynamische Datenstrukturen , Ayoma Gayan Wijethunga