Was ist das Konzept und die Struktur einer verknüpften Liste in der Java-Datenstruktur?

1. Das Konzept der verknüpften Liste

Konzept: Die verknüpfte Liste ist eine physische Speicherstruktur, die nicht kontinuierlich und nicht sequentiell ist durch die verknüpfte Liste.

1 Die verknüpfte Liste besteht aus einer Reihe von Knoten (jedes Element in der verknüpften Liste wird als Knoten bezeichnet).

2. Knoten können zur Laufzeit dynamisch generiert werden (malloc).

3. 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 (Einzelheiten finden Sie im Abschnitt 1.2 Knoten).

4. Im Vergleich zur linearen Listensequenzstruktur ist die verknüpfte Listenoperation kompliziert. Da die verknüpfte Liste jedoch nicht in der richtigen Reihenfolge gespeichert werden muss, kann sie beim Einfügen eine O(1)-Komplexität erreichen, was jedoch viel schneller ist als die sequentielle Liste, die jedoch für die Suche nach einem Knoten oder den Zugriff auf einen Knoten mit einer bestimmten Nummer erforderlich ist O(n)-Zeit, und die Sequenzliste benötigt nur O(1)

2 Knoten

Die verknüpfte Liste besteht aus Knoten, und jeder Knoten hat die Form eine Struktur. Die ersten Variablen in der Struktur werden nach Bedarf angegeben. Die letzte Variable ist ein Zeiger dieses Strukturtyps, der zum Speichern der ersten Adresse des nächsten Knotens verwendet wird #🎜🎜 #Datendomäne: speichert verschiedene tatsächliche Daten

Zeigerdomäne: speichert die Adresse des nächsten Knotens

(Das Bild zeigt die Sentinel-Position (verknüpfte Liste des Hauptknotens)

3. Verwendungsszenarien verknüpfter Listen

Lineare Listen eignen sich, wenn

häufig Datenelemente eingefügt oder gelöscht werden müssen#🎜 🎜# Kettenspeicherstruktur übernehmen.

Denn für eine verknüpfte Liste erfordert das Einfügen oder Löschen von Daten lediglich das Erstellen eines Knotens, die Eingabe von Daten, das Ändern des Zeigers und das Verbinden des Knotens mit einer bestimmten Position in der verknüpften Liste, und für eine Sequenzliste das Einfügen Bei einigen Daten kann es erforderlich sein, andere Daten zu verschieben, was sehr komplex ist. 4. Klassifizierung verknüpfter Listen und häufig verwendete Strukturen

Obwohl Die Kombination Es stehen insgesamt 8 Arten von verknüpften Listen zur Auswahl, aber die in der Praxis am häufigsten verwendeten sind

Kopflose einseitige, nichtzyklische verkettete Liste und

Zweikopfige zwei- Weg kreisförmige

verknüpfte Liste. 1. Kopflose einseitige, nichtzyklische verknüpfte Liste: allgemein bekannt als „einfach verknüpfte Liste“. Die Struktur ist einfach und wird im Allgemeinen nicht nur zum Speichern von Daten verwendet. Tatsächlich handelt es sich eher um eine Unterstruktur anderer Datenstrukturen (z. B. Hash-Buckets, Diagramm-Adjazenzlisten, Stapelkettenstrukturen usw.). Wird im Allgemeinen zum separaten Speichern von Daten verwendet. Die meisten der tatsächlich verwendeten verknüpften Listen sind bidirektionale, zirkulär verknüpfte Listen mit Kopf. Obwohl die Struktur die komplexeste ist, bringt diese Struktur viele Vorteile mit sich. 5. Vergleich mit sequentieller Liste

Verknüpfte Liste: Verknüpft diskrete Daten durch Knoteneinfügung und -löschung Zugriff auf Daten.

Sequenztabelle:

Die Sequenztabelle speichert Daten durch Öffnen eines kontinuierlichen Speichers (direkt mithilfe eines Arrays oder Mallocs und anschließender Realloc-Erweiterung).

Aber da realloc

die Erweiterung in In-situ-Erweiterung und Off-Site-Erweiterung unterteilt ist, ist erstere kostengünstiger, während letztere nicht nur das Kopieren von Daten erfordert, sondern auch Freigabe von altem Platz bei der Erweiterung. Darüber hinaus wird es beim Erweitern normalerweise auf das Zweifache der ursprünglichen Kapazität erweitert, was leicht zu einer Platzverschwendung führt. Der Datentyp des Knotens kann ein Standard-C-Typ oder ein benutzerdefinierter Strukturtyp sein.

Vergleichsobjekt

Sequenzliste

Verknüpfte Liste # 🎜🎜#

SpeicherplatzKontinuierlichDiskontinuierlich# 🎜 🎜#Einfügen oder Löschen von DatenEs kann erforderlich sein, die Daten zu verschieben, die Komplexität ist O(n)# 🎜🎜#Es gibt kein Konzept von „Kapazität“, und neue Knoten werden beim Drücken direkt mallociert häufiges Einfügen und Löschen von Daten

Sie müssen nur den Zeiger ändern# 🎜🎜#	push	Dynamische Sequenztabelle: Der Platz reicht nicht aus und muss erweitert werden
#🎜 🎜#

Das obige ist der detaillierte Inhalt vonWas ist das Konzept und die Struktur einer verknüpften Liste in der Java-Datenstruktur?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!