Wie kann man in Java am besten eine verknüpfte Liste erstellen?
Die offensichtliche Lösung für Entwickler, die mit Java vertraut sind, ist die Verwendung der LinkedList-Klasse, die bereits in java.util enthalten ist. Nehmen wir jedoch an, Sie möchten aus irgendeinem Grund eine eigene Implementierung erstellen. Hier ist ein schnelles Beispiel für eine verknüpfte Liste, die einen neuen Link am Anfang der Liste einfügt, am Anfang der Liste löscht und die Liste in einer Schleife durchläuft, um die darin enthaltenen Links zu drucken. Zu den Verbesserungen dieser Implementierung gehört, dass man sie zu einer doppelverknüpften Liste macht, Methoden zum Einfügen und Löschen von der Mitte oder vom Ende aus hinzufügt und auch Get- und Sort-Methoden hinzufügt.
Anmerkung: Im Beispiel enthält das Link-Objekt kein weiteres Link-Objekt - nextLink ist eigentlich nur ein Verweis auf einen anderen Link.
class Link {
public int data1;
public double data2;
public Link nextLink;
//Link constructor
public Link(int d1, double d2) {
data1 = d1;
data2 = d2;
}
//Print Link data
public void printLink() {
System.out.print("{" + data1 + ", " + data2 + "} ");
}
}
class LinkList {
private Link first;
//LinkList constructor
public LinkList() {
first = null;
}
//Returns true if list is empty
public boolean isEmpty() {
return first == null;
}
//Inserts a new Link at the first of the list
public void insert(int d1, double d2) {
Link link = new Link(d1, d2);
link.nextLink = first;
first = link;
}
//Deletes the link at the first of the list
public Link delete() {
Link temp = first;
if(first == null){
return null;
//throw new NoSuchElementException(); // this is the better way.
}
first = first.nextLink;
return temp;
}
//Prints list data
public void printList() {
Link currentLink = first;
System.out.print("List: ");
while(currentLink != null) {
currentLink.printLink();
currentLink = currentLink.nextLink;
}
System.out.println("");
}
}
class LinkListTest {
public static void main(String[] args) {
LinkList list = new LinkList();
list.insert(1, 1.01);
list.insert(2, 2.02);
list.insert(3, 3.03);
list.insert(4, 4.04);
list.insert(5, 5.05);
list.printList();
while(!list.isEmpty()) {
Link deletedLink = list.delete();
System.out.print("deleted: ");
deletedLink.printLink();
System.out.println("");
}
list.printList();
}
}
Java hat eine LinkedList-Implementierung, die Sie vielleicht ausprobieren möchten. Sie können das JDK und seine Quellen unter java.sun.com herunterladen.
Verwenden Sie java.util.LinkedList. Zum Beispiel so:
list = new java.util.LinkedList()