Lære Implementering af LinkedList i Java

Stryg for at vise menuen

Det er tid til at udfordre dig selv med nogle virkelig komplekse opgaver.

Vi vil implementere vores forenklede datastruktur—specifikt, SinglyLinkedList.

Lad os begynde med at implementere Node-klassen, som skal gemme en værdi og en reference til den næste Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

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

Implementeringen af Node-klassen i SinglyLinkedList blev allerede demonstreret i det forrige kapitel, så vi vil ikke dvæle længe ved den.

Dernæst opretter vi SinglyLinkedList-klassen, hvor vi definerer al logikken for vores datastruktur:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Vi oprettede feltet Node head, som vil gemme det første element i vores datastruktur.

I en almindelig LinkedList er der også en head og tail, der gemmer henholdsvis det første og sidste element i datastrukturen. Da datastrukturen skal være tom ved initialisering, sætter vi dette felt til null i konstruktøren.

Vores datastruktur skal understøtte alle CRUD-operationer.

Opret

Lad os derfor gå trin for trin og skrive en metode til at tilføje et element til slutningen af listen, hvilket repræsenterer Create-operationen:

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

Ovenfor ses implementeringen af metoden til at tilføje et element til slutningen af listen. Lad os gennemgå, hvordan denne metode fungerer:

Der oprettes et objekt af klassen Node, newNode, og det initialiseres via konstruktøren, hvor data fra parametrene i append()-metoden videregives;
Dernæst kontrolleres det, om listen er tom, og hvis det er tilfældet, erstattes det første element i listen (head) med newNode ved omallokering;
Herefter tilføjes en return-sætning for at afslutte metoden;
Hvis listen ikke er tom, oprettes der i denne metode et nyt objekt, current, som repræsenterer Node head i denne sammenhæng;
Ved hjælp af en while-løkke itereres der gennem hele listen, indtil current.next er null, hvilket betyder, at det næste element i listen er tomt;
Når det sidste ikke-null element i listen er fundet, sættes dets reference til newNode, hvorved elementet tilføjes til listen.

Med andre ord var målet med append-metoden at sætte referencen for det sidste element til det nye element. På denne måde tilføjes et nyt element til listen.

Læs

Lad os fortsætte; nu skal vi implementere Read-operationen.

SinglyLinkedList.java


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

Read-operationen er ret enkel. Det er nødvendigt at iterere gennem hvert element i listen og udskrive dem på skærmen. I dette tilfælde anvendes også pladsholderen current, som initialiseres med Node head;
Dernæst angives betingelsen for while-løkken til current != null og feltet data udskrives på skærmen;
Til iteration gennem listen anvendes referencen ved at genindstille current, hvilket ser sådan ud: current = current.next;;
Dette gentages, indtil Node current bliver tom. Herefter afsluttes løkken, og der fortsættes til næste linje.

Overvej i øvrigt hvordan denne while-løkke kan erstattes med en do-while-løkke. Er det overhovedet muligt?

Opdatering

Lad os nu gå videre til opdateringsmetoden, som er mere interessant i sin implementering:

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

Først kontrolleres det med en index-sætning, om denne if findes i vores liste. Hvis ikke, udskrives beskeden "Invalid index", og metoden afsluttes. Dette gøres for at undgå fejl;
Hvis indekset er inden for grænserne af vores liste, fortsættes med den velkendte algoritme. Først oprettes et objekt af klassen Node kaldet current, som initialiseres som head;
I stedet for at bruge en while-løkke anvendes en for-løkke, som er mere velegnet her, da det præcise antal iterationer er kendt. Antallet af iterationer er lig med værdien af parameteren index;
Løkken ser således ud:
for (int i = 0; i < index; i++). I denne løkke findes det ønskede element ved hjælp af den velkendte operation: current = current.next;
Når det ønskede element er fundet, tildeles dets data-attribut en ny værdi ved at udføre operationen
current.data = newData. Værdien newData modtages fra parametrene til denne metode.

Var alt klart?

Tak for dine kommentarer!

Sektion 1. Kapitel 7

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Sektion 1. Kapitel 7