Leer Implementatie Van LinkedList in Java

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 al gedemonstreerd in het vorige hoofdstuk, dus we zullen hier niet lang bij stilstaan.

Vervolgens maken we de klasse SinglyLinkedList, 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 gewone 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 alle CRUD-operaties ondersteunen.

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 voorstelt:

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 zie je de implementatie van de methode om een element aan het einde van de lijst toe te voegen. Laten we analyseren hoe deze methode werkt:

We maken een object van de Node-klasse, newNode, en initialiseren dit via de constructor, waarbij we de data uit de parameters van de append()-methode doorgeven;
Vervolgens controleren we of de lijst leeg is. Als dat zo is, vervangen we het eerste element van de lijst (head) door newNode via toewijzing;
Daarna voegen we een return-statement toe om de methode te verlaten;
Als de lijst niet leeg is, maken we in deze methode een nieuw object, current, dat de Node head in deze context voorstelt;
Met behulp van een while-lus itereren we door de hele lijst totdat current.next null is, wat betekent dat het volgende element in de lijst leeg is;
Zodra we het laatste niet-nul element in de lijst vinden, stellen we zijn koppeling in op newNode, waardoor het element aan onze lijst wordt toegevoegd.

Met andere woorden, het doel van de append-methode was de koppeling van het laatste element instellen op het nieuwe element. Op deze manier voegen we een nieuw element toe aan de lijst.

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 af op het scherm;
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 verder met 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 verdergaan 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 wordt gecontroleerd of deze index zich in onze lijst bevindt met een if-statement. Zo niet, dan wordt het bericht "Invalid index" weergegeven en wordt de methode beëindigd. Dit gebeurt om fouten te voorkomen;
Als de index binnen de grenzen van onze lijst valt, wordt het bekende algoritme gevolgd. Eerst wordt een object van de klasse Node aangemaakt, genaamd current, dat wordt geïnitialiseerd als de head;
In plaats van een while-lus wordt een for-lus gebruikt, die hier geschikter is omdat het exacte aantal iteraties bekend is. Het aantal iteraties is gelijk aan de waarde van de parameter index;
De lus ziet er als volgt uit:
for (int i = 0; i < index; i++). In deze lus wordt het gewenste element gevonden met de bekende bewerking: current = current.next;
Zodra het gewenste element is gevonden, wordt de data-attribuut een nieuwe waarde toegekend met de bewerking
current.data = newData. De waarde van newData wordt uit de parameters van deze methode gehaald.

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 1. Hoofdstuk 7

Vraag AI

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

Sectie 1. Hoofdstuk 7