Was sind die Merkmale verknüpfter Listen?

Das Merkmal einer verknüpften Liste besteht darin, einen Satz willkürlicher Speichereinheiten zum Speichern der Datenelemente der linearen Liste zu verwenden. Um die logische Beziehung zwischen jedem Datenelement und seinen direkten Nachfolgerdatenelementen auszudrücken, Für Datenelemente müssen zusätzlich zur Speicherung zusätzlich zu den eigenen Informationen auch Informationen gespeichert werden, die den unmittelbaren Nachfolger angeben.

Funktionen

Einfach verknüpfte Liste, das Ende des Pfeils ist der Knoten

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 kontinuierlich sein oder diskontinuierlich). 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 sind die Merkmale verknüpfter Listen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!