Welche Datenstruktur hat eine verknüpfte Liste?

Eine verknüpfte Liste ist eine nicht kontinuierliche und nicht sequentielle Speicherstruktur auf einer physischen Speichereinheit. Die logische Reihenfolge der Datenelemente wird vereinfacht gesagt durch die vom verknüpften Speicher generierte Tabelle realisiert Struktur einer linearen Liste. Sie wird als „verknüpfte Liste“ bezeichnet. Jedes Datenelement in der verknüpften Liste besteht aus zwei Teilen: 1. Der Information selbst, dem sogenannten „Datenfeld“ 2. Dem Zeiger auf den direkten Nachfolger, dem sogenannten „Zeigerfeld“. Diese beiden Informationsteile bilden die Speicherstruktur von Datenelementen, die als „Knoten“ bezeichnet werden; n Knoten sind über Zeigerfelder miteinander verknüpft, um eine verknüpfte Liste zu bilden.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, Dell G3-Computer.

Datenstruktur ist die Art und Weise, wie Computer Daten speichern und organisieren. Eine Datenstruktur bezieht sich auf eine Sammlung von Datenelementen, die eine oder mehrere spezifische Beziehungen zueinander haben. Oftmals können sorgfältig ausgewählte Datenstrukturen zu einer höheren Betriebs- oder Speichereffizienz führen. Datenstrukturen hängen oft mit effizienten Abrufalgorithmen und Indexierungstechniken zusammen.

Die 链表

verknüpfte Liste in der Datenstruktur ist eine nicht kontinuierliche und nicht sequentielle Speicherstruktur auf der physischen Speichereinheit. Die logische Reihenfolge der Datenelemente wird durch die Zeigerverknüpfungsreihenfolge in realisiert die verknüpfte Liste. 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.

Daten, die in der logischen Struktur nacheinander stehen, liegen bei der tatsächlichen Speicherung nicht wie eine Sequenztabelle nebeneinander. Im Gegensatz dazu werden die Daten zufällig an verschiedenen Stellen im Speicher verteilt. Diese Speicherstruktur wird als verknüpfte Speicherung einer linearen Liste bezeichnet.

Aufgrund der dezentralen Speicherung muss jedes Datenelement mit einem Zeiger ausgestattet sein, der beim Speichern auf sein direktes Nachfolgeelement zeigt, d. h. jedes Datenelement zeigt auf das nächste Datenelement Elemente (das letzte zeigt auf NULL).

Wie im Bild oben gezeigt, wird eine Kette gebildet, wenn jedes Datenelement mit seinem nächsten Datenelement verknüpft wird, und der Kopf dieser Kette befindet sich am ersten Datenelement. Eine solche Speicherung Die Methode ist Kettenspeicher.

Die durch die verknüpfte Speicherstruktur der linearen Liste generierte Tabelle wird als „verknüpfte Liste“ bezeichnet.

Die Zusammensetzung der Datenelemente in der verknüpften Liste

Jedes Element selbst besteht aus zwei Teilen:

• Die Informationen selbst werden als „Datenfeld“ bezeichnet;

• Der Zeiger auf den unmittelbaren Nachfolger heißt „Zeigerfeld“.

Diese beiden Informationsteile bilden die Speicherstruktur von Datenelementen, die als „Knoten“ bezeichnet werden. n Knoten werden über Zeigerfelder miteinander verknüpft, um eine verknüpfte Liste zu bilden.

Kopfknoten, Kopfzeiger und erster Knoten

Kopfknoten: Manchmal wird vor dem ersten Knoten der verknüpften Liste ein zusätzlicher Knoten hinzugefügt, und das Datenfeld des Knotens wird im Allgemeinen nicht gespeichert. Daten (in In einigen Fällen können auch Informationen wie die Länge der verknüpften Liste gespeichert werden.) Dieser Knoten wird als Kopfknoten bezeichnet.

Wenn das Zeigerfeld des Kopfknotens NULL ist, bedeutet dies, dass die verknüpfte Liste eine leere Liste ist. Der Kopfknoten ist für die verknüpfte Liste nicht erforderlich. Bei bestimmten Problemen wird das Problem durch Hinzufügen eines Kopfknotens zur verknüpften Liste vereinfacht.

Erster Knoten: Der Knoten, auf dem sich das erste Element in der verknüpften Liste befindet. Es ist der erste Knoten nach dem Kopfknoten.

Kopfzeiger: Zeigt immer auf die Position des ersten Knotens in der verknüpften Liste (wenn die verknüpfte Liste einen Kopfknoten hat, zeigt der Kopfzeiger auf den Kopfknoten; andernfalls zeigt der Kopfzeiger auf den ersten Knoten).

Der Unterschied zwischen Kopfknoten und Kopfzeiger: Der Kopfzeiger ist ein Zeiger, der auf den Kopfknoten oder den ersten Knoten der verknüpften Liste zeigt. Der Kopfknoten ist ein tatsächlicher Knoten, der Datenfelder und Zeigerdomänen enthält. Die direkte Manifestation der beiden im Programm besteht darin, dass der Kopfzeiger nur deklariert, aber kein Speicherplatz zugewiesen wird, und der Kopfknoten deklariert wird und der tatsächliche physische Speicher eines Knotens zugewiesen wird.

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 vollständig nutzen und einen flexiblen dynamischen Speicher erzielen Management. 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.

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 Speichereinheiten kann kontinuierlich oder diskontinuierlich sein). 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 Informationsteile bilden einen „Knoten“ (wie in der Abbildung unten gezeigt), 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 verlinkten Liste selbst gestalten. 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 praktischer sein kann, am Rand eine umgekehrte Markierung hinzuzufügen, wenn die verknüpfte Liste die Umkehrung der Vorder- und Rückseitenzeiger 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 nacheinander verknüpft sind, wird als verknüpfte Speicherdarstellung einer linearen Liste bezeichnet. Da jeder Knoten dieser Art verknüpfter Liste nur ein Zeigerfeld enthält wird auch einfach verknüpfte Liste oder linear verknüpfte Liste genannt.

Einfügen und Entfernen von Knoten aus verknüpften Listen

Verknüpfte Listen ermöglichen das Einfügen und Entfernen von Knoten an jeder Position in der Tabelle, ein wahlfreier Zugriff ist jedoch nicht zulässig.

1. Fügen Sie einen Knoten in die verknüpfte Liste ein.

• Fügen Sie den Kopfknoten in die verknüpfte Liste ein. Dieser ist entsprechend der Einfügeposition in drei Typen unterteilt:

• In den Kopf der verknüpften Liste einfügen ist, der Kopfknoten und das erste Element In der Mitte des Knotens wird

• ganz am Ende der verknüpften Liste eingefügt;

• Obwohl die Einfügungsstellen unterschiedlich sind, verwenden sie alle die gleiche Einfügungstechnik. Es ist in zwei Schritte unterteilt, wie im Bild oben gezeigt:

Richten Sie den nächsten Zeiger des neuen Knotens auf den Knoten nach der Einfügeposition.

Richten Sie den nächsten Zeiger des Knotens vor der Einfügeposition der Einfügeknoten;

• Tipps: Wenn Sie einen Einfügevorgang durchführen, müssen Sie zuerst den vorherigen Knoten an der Einfügeposition finden, dh Knoten 1. Der entsprechende Knoten 2 kann durch den nächsten Zeiger dargestellt werden von Knoten 1. Fahren Sie auf diese Weise zunächst mit Schritt 1 und dann mit Schritt 2 fort. Während des Implementierungsprozesses müssen keine weiteren Hilfszeiger hinzugefügt werden.

2. Einen Knoten aus der verknüpften Liste löschen

• Wenn Sie einen Knoten aus der verknüpften Liste löschen müssen, müssen Sie zwei Schritte ausführen:

Wählen Sie den Knoten aus der verknüpften Liste aus.

Manuell freigeben Der Knoten Klicken Sie hier, um den vom Knoten belegten Speicherplatz zu recyceln.

• Weitere Informationen zu diesem Thema finden Sie in der Spalte „FAQ“!

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