Java-Datenstrukturen
Java bietet eine umfangreiche Sammlung von Datenstrukturen zur Verarbeitung und Organisation von Daten.
Das java.util-Paket von Java stellt Implementierungen vieler dieser Datenstrukturen bereit, und Sie können die geeignete Klasse nach Bedarf auswählen.
Im Folgenden sind einige gängige Java-Datenstrukturen aufgeführt:
Arrays
Arrays sind eine grundlegende Datenstruktur, die eine Sammlung fester Größe von Elementen desselben Typs speichern kann.
int[] array = new int[5];
- Merkmale:Feste Größe, speichert Elemente desselben Typs.
- Vorteile:Effizienter wahlfreier Zugriff auf Elemente.
- Nachteile:Feste Größe, Einfügen und Löschen von Elementen sind relativ langsam.
Listen
Java bietet mehrere Listenimplementierungen, wie ArrayList und LinkedList.
List<String> arrayList = new ArrayList<>(); List<Integer> linkedList = new LinkedList<>();
ArrayList:
- Merkmale:Dynamisches Array, variable Größe.
- Vorteile:Effizienter wahlfreier Zugriff und schnelles Einfügen am Ende.
- Nachteile:Einfügen und Löschen in der Mitte sind relativ langsam.
LinkedList:
- Eigenschaften:Doppelt verkettete Liste, Elemente sind durch Zeiger verbunden.
- Vorteile:Effizientes Einfügen und Löschen von Elementen, gute Iterator-Leistung.
- Nachteile:Der wahlfreie Zugriff ist relativ langsam.
Mengen
Mengen werden verwendet, um duplikatfreie Elemente zu speichern, und gängige Implementierungen umfassen HashSet und TreeSet.
Set<String> hashSet = new HashSet<>(); Set<Integer> treeSet = new TreeSet<>();
HashSet:
- Eigenschaften:Ungeordnete Sammlung, implementiert auf Basis von HashMap.
- Vorteile:Effiziente Such- und Einfügeoperationen.
- Nachteile:Garantiert keine Reihenfolge.
TreeSet:
- Eigenschaften:TreeSet ist eine geordnete Sammlung, implementiert auf Basis eines Rot-Schwarz-Baums auf der untersten Ebene, und erlaubt keine doppelten Elemente.
- Vorteile:Bietet eine automatische Sortierfunktion, geeignet für Szenarien, in denen Elemente in geordneter Reihenfolge gespeichert werden müssen.
- Nachteile:Die Leistung ist relativ schlecht, und das Einfügen von null-Elementen ist nicht erlaubt.
Karten
Maps werden zum Speichern von Schlüssel-Wert-Paaren verwendet, und gängige Implementierungen umfassen HashMap und TreeMap.
Map<String, Integer> hashMap = new HashMap<>(); Map<String, Integer> treeMap = new TreeMap<>();
HashMap:
- Merkmale:Eine auf einer Hash-Tabelle basierende Speicherstruktur für Schlüssel-Wert-Paare.
- Vorteile:Effiziente Such-, Einfüge- und Löschvorgänge.
- Nachteile:Ungeordnet, garantiert keine Reihenfolge.
TreeMap:
- Merkmale:Eine geordnete Speicherstruktur für Schlüssel-Wert-Paare, die auf einem Rot-Schwarz-Baum basiert.
- Vorteile:Geordnet, unterstützt die Traversierung in der Reihenfolge der Schlüssel.
- Nachteile:Einfügen und Löschen sind relativ langsam.
Stapel
Ein Stack ist eine lineare Datenstruktur, die Elemente nach dem Last-In-First-Out-Prinzip (LIFO) verwaltet. In einem Stack werden neue Elemente oben auf dem Stack hinzugefügt, und Elemente können nur oben vom Stack entfernt werden. Das bedeutet, dass das zuletzt hinzugefügte Element zuerst entfernt wird.
Stack<Integer> stack = new Stack<>();
Stack-Klasse:
- Eigenschaften:Repräsentiert einen Stack, der üblicherweise Elemente in einer Last-In-First-Out-(LIFO)-Reihenfolge verarbeitet.
Warteschlange
Queues folgen dem First-In-First-Out-(FIFO)-Prinzip, und gängige Implementierungen umfassen LinkedList und PriorityQueue.
Queue<String> queue = new LinkedList<>();
Queue-Schnittstelle:
- Eigenschaften:Repräsentiert eine Queue, die üblicherweise Elemente in einer First-In-First-Out-(FIFO)-Reihenfolge verarbeitet.
- Implementierungsklassen: LinkedList, PriorityQueue, ArrayDeque.
Heap
Ein Heap ist die Grundlage einer Prioritätswarteschlange und kann Max-Heap und Min-Heap implementieren.
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
Bäume
Java stellt den Typ TreeNode bereit, der zum Aufbau von Datenstrukturen wie Binärbäumen verwendet werden kann.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
Graphen
Die Darstellung von Graphen erfordert üblicherweise benutzerdefinierte Datenstrukturen oder die Verwendung von Graphbibliotheken; Java besitzt keine integrierte Graphklasse.
Das oben Genannte sind nur einige gängige Datenstrukturen in Java. Tatsächlich gibt es viele weitere Datenstrukturen und Algorithmen, die je nach konkreten Problemen ausgewählt und verwendet werden können.
Weitere Hinweise
Die folgenden Klassen sind traditionell veraltet. In Java 2 wurde ein neues Framework, das Collection Framework, eingeführt, das wir später besprechen werden.
Enumeration
Das Enumeration-Interface ist, obwohl es selbst keine Datenstruktur ist, im Umfeld anderer Datenstrukturen weit verbreitet. Das Enumeration-Interface definiert eine Möglichkeit, aufeinanderfolgende Elemente aus einer Datenstruktur abzurufen.
Zum Beispiel definiert Enumeration eine Methode namens nextElement, mit der das nächste Element einer Datenstruktur abgerufen wird, die mehrere Elemente enthält.
Weitere Informationen über das Enumeration-Interface,siehe bitte Enumeration。
BitSet
Die Klasse BitSet implementiert eine Gruppe von Bits oder Flags, die einzeln gesetzt und gelöscht werden können.
Diese Klasse ist sehr nützlich im Umgang mit einer Gruppe von booleschen Werten. Sie müssen jedem Wert nur ein "Bit" zuweisen und dann die Bits entsprechend setzen oder löschen, um mit den booleschen Werten zu arbeiten.
Weitere Informationen über diese Klasse,siehe bitte BitSet。
Vektor
Die Klasse Vector ist einem traditionellen Array sehr ähnlich, aber die Größe von Vector kann sich dynamisch nach Bedarf ändern.
Wie bei Arrays kann auch auf Elemente von Vector-Objekten über den Index zugegriffen werden.
Der Hauptvorteil der Verwendung der Klasse Vector besteht darin, dass Sie beim Erstellen keine Größe für das Objekt angeben müssen; seine Größe ändert sich dynamisch nach Bedarf.
Weitere Informationen über diese Klasse,siehe bitte Vector
Stapel
Die Klasse Stack implementiert eine Last-In-First-Out-Datenstruktur (LIFO).
Man kann einen Stack als einen vertikal verteilten Stapel von Objekten verstehen. Wenn man ein neues Element hinzufügt, legt man es oben auf die anderen Elemente.
Wenn man ein Element aus dem Stack entnimmt, nimmt man es von der Oberseite des Stacks. Mit anderen Worten: Das Element, das zuletzt in den Stack eingefügt wurde, wird zuerst entfernt.
Weitere Informationen zu dieser Klasse finden Sie unterStack。
Wörterbuch
Die Klasse Dictionary ist eine abstrakte Klasse, die eine Datenstruktur definiert, die Schlüssel auf Werte abbildet.
Wenn Sie auf Daten über einen bestimmten Schlüssel statt über einen ganzzahligen Index zugreifen möchten, sollten Sie Dictionary verwenden.
Da die Klasse Dictionary eine abstrakte Klasse ist, bietet sie nur eine Datenstruktur zum Abbilden von Schlüsseln auf Werte, aber keine konkrete Implementierung.
Weitere Informationen zu dieser Klasse finden Sie unterDictionary。
Die Klasse Dictionary ist in neueren Java-Versionen veraltet. Es wird empfohlen, die Map-Schnittstelle und ihre Implementierungsklassen wie HashMap, TreeMap usw. zu verwenden, um Dictionary zu ersetzen.
Für die Map-Schnittstelle und ihre Implementierungsklassen siehe:Java Collections Framework。
Hashtable
Die Klasse Hashtable bietet eine Möglichkeit, Daten basierend auf einer benutzerdefinierten Schlüsselstruktur zu organisieren.
In einer Hashtable einer Adressliste können Sie beispielsweise Daten anhand der Postleitzahl als Schlüssel speichern und sortieren, statt nach dem Namen einer Person.
Die genaue Bedeutung eines Hashtable-Schlüssels hängt vollständig vom Verwendungsszenario der Hashtable und den darin enthaltenen Daten ab.
Weitere Informationen zu dieser Klasse finden Sie bitteunter Hashtable。
Eigenschaften
Properties erbt von Hashtable. Die Klasse Properties repräsentiert eine persistente Menge von Eigenschaften. Jeder Schlüssel und sein entsprechender Wert in der Eigenschaftsliste ist ein String.
Die Klasse Properties wird von vielen Java-Klassen verwendet. Zum Beispiel dient sie als Rückgabewert der Methode System.getProperties(), wenn Umgebungsvariablen abgerufen werden.
Weitere Informationen zu dieser Klasse finden Sieunter Properties。
Weitere Erweiterungen