Leer Implementatie van LinkedList in Java | Fundamentele Datastructuren in Java

Het is tijd om jezelf uit te dagen met enkele echt complexe taken.

We gaan onze vereenvoudigde datastructuur implementeren—specifiek de SinglyLinkedList.

Laten we beginnen met het implementeren van de Node-klasse, die een waarde en een referentie naar de volgende Node zal opslaan.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

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

De implementatie van de Node-klasse in SinglyLinkedList is reeds gedemonstreerd in het vorige hoofdstuk, dus we zullen hier niet lang bij stilstaan.

Vervolgens maken we de SinglyLinkedList-klasse aan, waarin we alle logica voor onze datastructuur zullen definiëren:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

We hebben het veld Node head aangemaakt, dat het eerste element van onze datastructuur zal opslaan.

In een reguliere LinkedList zijn er ook een head en tail die respectievelijk het eerste en laatste element van de datastructuur opslaan. Omdat de datastructuur bij de initialisatie leeg moet zijn, stellen we dit veld in de constructor in op null.

Onze datastructuur moet ondersteuning bieden voor alle CRUD-operaties.

Aanmaken

Laten we stap voor stap een methode schrijven om een element aan het einde van de lijst toe te voegen, wat de Create-operatie vertegenwoordigt:

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;
    }
}

Hierboven is de implementatie te zien van de methode om een element aan het einde van de lijst toe te voegen. Laten we uiteenzetten hoe deze methode werkt:

Er wordt een object van de klasse Node, newNode, aangemaakt en geïnitialiseerd via de constructor, waarbij de data uit de parameters van de append()-methode wordt doorgegeven;
Vervolgens wordt gecontroleerd of de lijst leeg is. Als dat zo is, wordt het eerste element van de lijst (head) vervangen door newNode via toewijzing;
Daarna wordt een return-statement toegevoegd om de methode te verlaten;
Als de lijst niet leeg is, wordt in deze methode een nieuw object, current, aangemaakt, dat in deze context de Node head voorstelt;
Met behulp van een while-lus wordt door de hele lijst gelopen totdat current.next null is, oftewel totdat het volgende element in de lijst leeg is;
Zodra het laatste niet-lege element in de lijst is gevonden, wordt de koppeling ervan ingesteld op newNode, waardoor het element aan de lijst wordt toegevoegd.

Met andere woorden, het doel van de append-methode was de koppeling van het laatste element instellen naar het nieuwe element. Op deze manier wordt een nieuw element aan de lijst toegevoegd.

Lezen

Laten we verder gaan; nu moeten we de leesoperatie implementeren.

SinglyLinkedList.java


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

Leesoperatie is vrij eenvoudig. We moeten door elk element van de lijst itereren en deze op het scherm afdrukken. In ons geval gebruiken we ook de tijdelijke variabele current, die we initialiseren met de Node head;
Vervolgens stellen we de conditie voor de while-lus in op current != null en drukken we het data-veld op het scherm af;
Voor het itereren door de lijst gebruiken we de referentie door current opnieuw toe te wijzen, wat eruitziet als current = current.next;;
Dit doen we totdat de Node current leeg wordt. Daarna verlaten we de lus en gaan we naar de volgende regel.

Denk trouwens eens na over hoe je deze while-lus kunt vervangen door een do-while-lus. Is dat überhaupt mogelijk?

Bijwerken

Laten we nu doorgaan met de update-methode, die interessanter is in de implementatie:

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;
}

Eerst controleren we of deze index zich in onze lijst bevindt met behulp van een if-statement. Zo niet, dan tonen we het bericht "Invalid index" en beëindigen we de methode. Dit wordt gedaan om fouten te voorkomen;
Als de index binnen de grenzen van onze lijst ligt, gaan we verder met het bekende algoritme. Eerst maken we een object van de klasse Node genaamd current, dat we initialiseren als de head;
In plaats van een while-lus gebruiken we een for-lus, die hier geschikter is omdat we het exacte aantal iteraties kennen dat nodig is. Het aantal iteraties is gelijk aan de waarde van de parameter index;
Onze lus ziet er als volgt uit:
for (int i = 0; i < index; i++). In deze lus vinden we het gewenste element met de bekende bewerking: current = current.next;
Zodra we het gewenste element hebben gevonden, wijzen we een nieuwe waarde toe aan het data-attribuut, door de bewerking uit te voeren
current.data = newData. We halen newData uit de parameters van deze methode.

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 1. Hoofdstuk 6

Vraag AI

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

Veeg om het menu te tonen

Het is tijd om jezelf uit te dagen met enkele echt complexe taken.

We gaan onze vereenvoudigde datastructuur implementeren—specifiek de SinglyLinkedList.

Laten we beginnen met het implementeren van de Node-klasse, die een waarde en een referentie naar de volgende Node zal opslaan.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

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

De implementatie van de Node-klasse in SinglyLinkedList is reeds gedemonstreerd in het vorige hoofdstuk, dus we zullen hier niet lang bij stilstaan.

Vervolgens maken we de SinglyLinkedList-klasse aan, waarin we alle logica voor onze datastructuur zullen definiëren:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

We hebben het veld Node head aangemaakt, dat het eerste element van onze datastructuur zal opslaan.

Onze datastructuur moet ondersteuning bieden voor alle CRUD-operaties.

Aanmaken

Laten we stap voor stap een methode schrijven om een element aan het einde van de lijst toe te voegen, wat de Create-operatie vertegenwoordigt:

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;
    }
}

Hierboven is de implementatie te zien van de methode om een element aan het einde van de lijst toe te voegen. Laten we uiteenzetten hoe deze methode werkt:

Er wordt een object van de klasse Node, newNode, aangemaakt en geïnitialiseerd via de constructor, waarbij de data uit de parameters van de append()-methode wordt doorgegeven;
Vervolgens wordt gecontroleerd of de lijst leeg is. Als dat zo is, wordt het eerste element van de lijst (head) vervangen door newNode via toewijzing;
Daarna wordt een return-statement toegevoegd om de methode te verlaten;
Als de lijst niet leeg is, wordt in deze methode een nieuw object, current, aangemaakt, dat in deze context de Node head voorstelt;
Met behulp van een while-lus wordt door de hele lijst gelopen totdat current.next null is, oftewel totdat het volgende element in de lijst leeg is;
Zodra het laatste niet-lege element in de lijst is gevonden, wordt de koppeling ervan ingesteld op newNode, waardoor het element aan de lijst wordt toegevoegd.

Met andere woorden, het doel van de append-methode was de koppeling van het laatste element instellen naar het nieuwe element. Op deze manier wordt een nieuw element aan de lijst toegevoegd.

Lezen

Laten we verder gaan; nu moeten we de leesoperatie implementeren.

SinglyLinkedList.java


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

Leesoperatie is vrij eenvoudig. We moeten door elk element van de lijst itereren en deze op het scherm afdrukken. In ons geval gebruiken we ook de tijdelijke variabele current, die we initialiseren met de Node head;
Vervolgens stellen we de conditie voor de while-lus in op current != null en drukken we het data-veld op het scherm af;
Voor het itereren door de lijst gebruiken we de referentie door current opnieuw toe te wijzen, wat eruitziet als current = current.next;;
Dit doen we totdat de Node current leeg wordt. Daarna verlaten we de lus en gaan we naar de volgende regel.

Denk trouwens eens na over hoe je deze while-lus kunt vervangen door een do-while-lus. Is dat überhaupt mogelijk?

Bijwerken

Laten we nu doorgaan met de update-methode, die interessanter is in de implementatie:

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;
}

Eerst controleren we of deze index zich in onze lijst bevindt met behulp van een if-statement. Zo niet, dan tonen we het bericht "Invalid index" en beëindigen we de methode. Dit wordt gedaan om fouten te voorkomen;
Als de index binnen de grenzen van onze lijst ligt, gaan we verder met het bekende algoritme. Eerst maken we een object van de klasse Node genaamd current, dat we initialiseren als de head;
In plaats van een while-lus gebruiken we een for-lus, die hier geschikter is omdat we het exacte aantal iteraties kennen dat nodig is. Het aantal iteraties is gelijk aan de waarde van de parameter index;
Onze lus ziet er als volgt uit:
for (int i = 0; i < index; i++). In deze lus vinden we het gewenste element met de bekende bewerking: current = current.next;
Zodra we het gewenste element hebben gevonden, wijzen we een nieuwe waarde toe aan het data-attribuut, door de bewerking uit te voeren
current.data = newData. We halen newData uit de parameters van deze methode.

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 1. Hoofdstuk 6