Was ist eine verknüpfte Liste?

Eine verknüpfte Liste ist eine nicht kontinuierliche, nicht sequentielle Speicherstruktur auf einer physischen Speichereinheit. Die logische Reihenfolge der Datenelemente wird durch die Zeigerverknüpfungsreihenfolge in der verknüpften Liste realisiert. Eine verknüpfte Liste besteht aus einer Reihe von Knoten (jedes Element in der verknüpften Liste wird als Knoten bezeichnet), und Knoten können zur Laufzeit dynamisch generiert werden. Jeder Knoten besteht aus zwei Teilen: Einer ist das Datenfeld, in dem Datenelemente gespeichert werden, und der andere ist das Zeigerfeld, in dem die Adresse des nächsten Knotens gespeichert wird. Im Vergleich zur linearen Tabellensequenzstruktur ist die Operation kompliziert. Da sie nicht in der richtigen Reihenfolge gespeichert werden muss, kann die verknüpfte Liste beim Einfügen eine O(1)-Komplexität erreichen, was viel schneller ist als eine andere lineare Liste oder eine sequentielle Liste, aber das Nachschlagen eines Knotens oder der Zugriff auf einen bestimmten nummerierten Knoten erfordert O( n) Zeit, und die entsprechenden Zeitkomplexitäten von linearen Tabellen und sequentiellen Tabellen sind O(logn) bzw. O(1).

Durch die Verwendung der verknüpften Listenstruktur kann der Nachteil der verknüpften Array-Liste behoben werden, dass die Datengröße im Voraus bekannt sein muss. Die verknüpfte Listenstruktur kann den Speicherplatz des Computers voll ausnutzen und eine flexible dynamische Speicherverwaltung erreichen. Allerdings verliert die verknüpfte Liste den Vorteil des zufälligen Lesens des Arrays. Gleichzeitig weist die verknüpfte Liste aufgrund der Vergrößerung des Zeigerfelds des Knotens einen relativ großen Speicherplatzaufwand auf. Der offensichtlichste Vorteil einer verknüpften Liste besteht darin, dass die Art und Weise, wie ein herkömmliches Array zugehörige Elemente anordnet, sich von der Reihenfolge unterscheiden kann, in der diese Datenelemente im Speicher oder auf der Festplatte angeordnet sind, und der Zugriff auf Daten häufig das Umschalten zwischen verschiedenen Anordnungen erfordert. Verknüpfte Listen ermöglichen das Einfügen und Entfernen von Knoten an jeder beliebigen Stelle in der Liste, erlauben jedoch keinen wahlfreien Zugriff. Es gibt viele verschiedene Arten von verknüpften Listen: einfach verknüpfte Listen, doppelt verknüpfte Listen und zirkulär verknüpfte Listen. Verknüpfte Listen können in verschiedenen Programmiersprachen implementiert werden. Die integrierten Datentypen von Sprachen wie Lisp und Scheme umfassen den Zugriff und Betrieb verknüpfter Listen. Programmier- oder objektorientierte Sprachen wie C, C++ und Java sind auf veränderbare Tools angewiesen, um verknüpfte Listen zu generieren.

Funktionen

Das Merkmal der verknüpften Speicherdarstellung einer linearen Tabelle besteht darin, einen Satz beliebiger Speichereinheiten zum Speichern der Datenelemente der linearen Tabelle zu verwenden (dieser Satz von Speichereinheiten kann sein). kontinuierlich oder unterschiedlich) kontinuierlich). Um die logische Beziehung zwischen jedem Datenelement und seinem direkten Nachfolgerdatenelement darzustellen, ist es daher für das Datenelement zusätzlich zur Speicherung seiner eigenen Informationen erforderlich, auch Informationen zu speichern, die seinen direkten Nachfolger angeben (dh die Speicherung). des direkten Nachfolgerstandortes). Diese beiden Informationen bilden einen „Knoten“ (wie in der Abbildung neben der Übersicht dargestellt), der ein Datenelement in der linearen Tabelle darstellt. Ein Nachteil der verknüpften Speicherdarstellung linearer Tabellen besteht darin, dass man zum Finden einer Zahl von vorne beginnen muss, was sehr mühsam ist.

Je nach Situation können Sie auch andere Erweiterungen der verknüpften Liste selbst entwerfen. Daten werden jedoch im Allgemeinen nicht an die Kanten angehängt, da die Punkte und Kanten der verknüpften Liste grundsätzlich in einer Eins-zu-Eins-Entsprechung stehen (mit Ausnahme des ersten oder letzten Knotens, es treten jedoch keine besonderen Umstände auf). Ein Sonderfall besteht jedoch darin, dass es möglicherweise praktischer ist, am Rand eine umgekehrte Markierung hinzuzufügen, wenn die verknüpfte Liste das Umkehren der vorderen und hinteren Zeiger in einem Abschnitt der verknüpften Liste unterstützt.

Bei nichtlinear verknüpften Listen können Sie auf andere verwandte Datenstrukturen wie Bäume und Diagramme verweisen. Es gibt auch eine Datenstruktur, die auf mehreren linear verknüpften Listen basiert: Sprunglisten. Die Geschwindigkeit grundlegender Operationen wie Einfügen, Löschen und Suchen kann O (nlogn) erreichen, genau wie bei einem ausgeglichenen Binärbaum.

Die Domäne, die Datenelementinformationen speichert, wird als Datendomäne bezeichnet (der Domänenname sei Daten), und die Domäne, die den Speicherort des direkten Nachfolgers speichert, wird als Zeigerdomäne bezeichnet (der Domänenname sei der nächste). . Die im Zeigerfeld gespeicherten Informationen werden auch Zeiger oder Kette genannt.

Eine verknüpfte Liste, die aus N Knoten besteht, die jeweils darstellen,,..., nacheinander verknüpft sind, wird als verknüpfte Speicherdarstellung einer linearen Liste bezeichnet, da jeder Knoten einer solchen verknüpften Liste nur einen Zeiger enthält Feld, daher wird es auch einfach verknüpfte Liste oder linear verknüpfte Liste genannt.

Das obige ist der detaillierte Inhalt vonWas ist eine verknüpfte Liste?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!