Lernen Implementierung von LinkedList in Java

Swipe um das Menü anzuzeigen

Es ist an der Zeit, sich mit einigen wirklich komplexen Aufgaben zu beschäftigen.

Wir werden unsere vereinfachte Datenstruktur implementieren – genauer gesagt, die SinglyLinkedList.

Beginnen wir mit der Implementierung der Node-Klasse, die einen Wert und eine Referenz auf den nächsten Node speichert.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Die Implementierung der Node-Klasse in SinglyLinkedList wurde bereits im vorherigen Kapitel gezeigt, daher werden wir hier nicht weiter darauf eingehen.

Als Nächstes erstellen wir die Klasse SinglyLinkedList, in der wir die gesamte Logik für unsere Datenstruktur definieren:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Wir haben das Feld Node head erstellt, das das erste Element unserer Datenstruktur speichert.

In einer gewöhnlichen LinkedList gibt es ebenfalls ein head und ein tail, die das erste bzw. das letzte Element der Datenstruktur speichern. Da die Datenstruktur bei der Initialisierung leer sein sollte, setzen wir dieses Feld im Konstruktor auf null.

Unsere Datenstruktur muss alle CRUD-Operationen unterstützen.

Erstellen

Gehen wir Schritt für Schritt vor und schreiben eine Methode, um ein Element am Ende der Liste hinzuzufügen, was die Create-Operation darstellt:

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

Oben ist die Implementierung der Methode zu sehen, mit der ein Element am Ende der Liste hinzugefügt wird. Im Folgenden wird erläutert, wie diese Methode funktioniert:

Es wird ein Objekt der Klasse Node, newNode, erstellt und über den Konstruktor initialisiert, wobei die data aus den Parametern der Methode append() übergeben werden;
Anschließend wird geprüft, ob die Liste leer ist. Falls ja, wird das erste Element der Liste (head) durch newNode ersetzt;
Danach wird eine return-Anweisung hinzugefügt, um die Methode zu beenden;
Falls die Liste nicht leer ist, wird in dieser Methode ein neues Objekt current erstellt, das in diesem Kontext den Node head repräsentiert;
Mit einer while-Schleife wird die gesamte Liste durchlaufen, bis current.next null ist, also bis das nächste Element in der Liste leer ist;
Sobald das letzte nicht-leere Element in der Liste gefunden wurde, wird dessen Verweis auf newNode gesetzt, wodurch das Element zur Liste hinzugefügt wird.

Mit anderen Worten: Das Ziel der Methode append war es, den Verweis des letzten Elements auf das neue Element zu setzen. So wird ein neues Element zur Liste hinzugefügt.

Lesen

Fahren wir fort; nun müssen wir die Leseoperation implementieren.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

Leseoperation ist recht einfach. Es ist erforderlich, jedes Element der Liste zu durchlaufen und diese auf dem Bildschirm auszugeben. In diesem Fall wird auch der Platzhalter current verwendet, der mit dem Node head initialisiert wird;
Anschließend wird die Bedingung für die while-Schleife auf current != null gesetzt und das Feld data auf dem Bildschirm ausgegeben;
Für das Durchlaufen der Liste wird die Referenz durch erneute Zuweisung von current verwendet, was wie folgt aussieht: current = current.next;;
Dies wird solange wiederholt, bis der Node current leer ist. Danach wird die Schleife verlassen und zur nächsten Zeile übergegangen.

Überlege außerdem, wie diese while-Schleife durch eine do-while-Schleife ersetzt werden könnte. Ist das überhaupt möglich?

Aktualisieren

Nun gehen wir zur Update-Methode über, deren Implementierung interessanter ist:

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Zuerst prüfen wir mit einer index-Anweisung, ob sich dieser if in unserer Liste befindet. Falls nicht, wird die Meldung "Invalid index" ausgegeben und die Methode beendet. Dies geschieht zur Fehlervermeidung;
Befindet sich der Index innerhalb der Grenzen unserer Liste, fahren wir mit dem bekannten Algorithmus fort. Zunächst erstellen wir ein Objekt der Klasse Node namens current, das wir als head initialisieren;
Anstelle einer while-Schleife verwenden wir eine for-Schleife, die hier besser geeignet ist, da wir die exakte Anzahl der Iterationen kennen. Die Anzahl der Iterationen entspricht dem Wert des Parameters index;
Unsere Schleife sieht folgendermaßen aus:
for (int i = 0; i < index; i++). In dieser Schleife finden wir das gewünschte Element mit der bekannten Operation: current = current.next;
Sobald wir das gewünschte Element gefunden haben, weisen wir seinem Attribut data einen neuen Wert zu, indem wir die Operation
current.data = newData ausführen. newData wird aus den Parametern dieser Methode übernommen.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 1. Kapitel 7

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Abschnitt 1. Kapitel 7