Lernen Implementierung von LinkedList in Java | Grundlegende Datenstrukturen in Java

Es ist an der Zeit, sich mit einigen wirklich komplexen Aufgaben zu fordern.

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 und 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 festgestellt wird, dass 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 Append-Methode war es, den Verweis des letzten Elements auf das neue Element zu setzen. So wird ein neues Element zur Liste hinzugefügt.

Lesen

Kommen wir zum nächsten Schritt; 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();
    }

Die Leseoperation ist recht einfach. Es ist erforderlich, durch jedes Element der Liste zu iterieren 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 current != null-Schleife auf data gesetzt und das Feld current auf dem Bildschirm ausgegeben;
Für die Iteration durch die Liste wird die Referenz durch erneute Zuweisung von current = current.next; verwendet, was wie folgt aussieht: Node current;
Dies wird solange wiederholt, bis der while leer ist. Danach wird die Schleife verlassen und zur nächsten Zeile übergegangen.

Überlegen Sie übrigens, wie diese while-Schleife durch eine do-while-Schleife ersetzt werden könnte. Ist das überhaupt möglich?

Aktualisieren

Kommen wir nun zur Update-Methode, deren Implementierung besonders interessant 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;
}

Zunächst wird überprüft, ob sich dieser index in unserer Liste befindet, indem eine if-Anweisung verwendet wird. Falls nicht, wird die Meldung "Invalid index" ausgegeben und die Methode beendet. Dies dient zur Fehlervermeidung;
Befindet sich der Index innerhalb der Grenzen unserer Liste, wird mit dem bekannten Algorithmus fortgefahren. Zuerst wird ein Objekt der Klasse Node mit dem Namen current erstellt, das als head initialisiert wird;
Anstelle einer while-Schleife wird eine for-Schleife verwendet, da diese hier besser geeignet ist, weil die exakte Anzahl der Iterationen bekannt ist. Die Anzahl der Iterationen entspricht dem Wert des Parameters index;
Die Schleife sieht folgendermaßen aus:
for (int i = 0; i < index; i++). In dieser Schleife wird das gewünschte Element mit der bekannten Operation gefunden: current = current.next;
Nachdem das gewünschte Element gefunden wurde, wird dessen Attribut data mit einem neuen Wert belegt, indem die Operation
current.data = newData ausgeführt wird. Der Wert newData wird aus den Parametern dieser Methode übernommen.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 1. Kapitel 6

Fragen Sie AI

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

Swipe um das Menü anzuzeigen

Es ist an der Zeit, sich mit einigen wirklich komplexen Aufgaben zu fordern.

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.

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 festgestellt wird, dass 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 Append-Methode war es, den Verweis des letzten Elements auf das neue Element zu setzen. So wird ein neues Element zur Liste hinzugefügt.

Lesen

Kommen wir zum nächsten Schritt; 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();
    }

Die Leseoperation ist recht einfach. Es ist erforderlich, durch jedes Element der Liste zu iterieren 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 current != null-Schleife auf data gesetzt und das Feld current auf dem Bildschirm ausgegeben;
Für die Iteration durch die Liste wird die Referenz durch erneute Zuweisung von current = current.next; verwendet, was wie folgt aussieht: Node current;
Dies wird solange wiederholt, bis der while leer ist. Danach wird die Schleife verlassen und zur nächsten Zeile übergegangen.

Überlegen Sie übrigens, wie diese while-Schleife durch eine do-while-Schleife ersetzt werden könnte. Ist das überhaupt möglich?

Aktualisieren

Kommen wir nun zur Update-Methode, deren Implementierung besonders interessant 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;
}

Zunächst wird überprüft, ob sich dieser index in unserer Liste befindet, indem eine if-Anweisung verwendet wird. Falls nicht, wird die Meldung "Invalid index" ausgegeben und die Methode beendet. Dies dient zur Fehlervermeidung;
Befindet sich der Index innerhalb der Grenzen unserer Liste, wird mit dem bekannten Algorithmus fortgefahren. Zuerst wird ein Objekt der Klasse Node mit dem Namen current erstellt, das als head initialisiert wird;
Anstelle einer while-Schleife wird eine for-Schleife verwendet, da diese hier besser geeignet ist, weil die exakte Anzahl der Iterationen bekannt ist. Die Anzahl der Iterationen entspricht dem Wert des Parameters index;
Die Schleife sieht folgendermaßen aus:
for (int i = 0; i < index; i++). In dieser Schleife wird das gewünschte Element mit der bekannten Operation gefunden: current = current.next;
Nachdem das gewünschte Element gefunden wurde, wird dessen Attribut data mit einem neuen Wert belegt, indem die Operation
current.data = newData ausgeführt wird. Der Wert newData wird aus den Parametern dieser Methode übernommen.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 1. Kapitel 6