Lære Implementering af LinkedList i Java | Fundamentale Datastrukturer i Java

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 ved den længe.

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 findes der også en head og tail, som 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 kan du se implementeringen af metoden til at tilføje et element til slutningen af listen. Lad os gennemgå, hvordan denne metode fungerer:

Vi opretter et objekt af klassen Node, newNode, og initialiserer det gennem konstruktøren, hvor vi videregiver data fra parametrene i append()-metoden;
Dernæst tjekker vi om listen er tom, og hvis den er, erstatter vi det første element i listen (head) med newNode ved omfordeling;
Derefter tilføjer vi en return-sætning for at afslutte metoden;
Hvis listen ikke er tom, opretter vi i denne metode et nyt objekt, current, som repræsenterer Node head i denne sammenhæng;
Ved hjælp af en while-løkke gennemløber vi hele listen, indtil current.next er null, hvilket betyder, at vi har fastslået, at det næste element i listen er tomt;
Når vi finder det sidste ikke-null element i listen, sætter vi dets link til newNode og tilføjer dermed elementet til vores liste.

Med andre ord var målet med append-metoden at sætte linket for det sidste element til det nye element. På denne måde tilføjer vi 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 tildele current på ny, hvilket ser således ud: current = current.next;;
Dette gentages, indtil Node current bliver tom. Herefter afsluttes løkken, og næste linje udføres.

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 kontrollerer vi, om denne index findes i vores liste ved hjælp af en if-sætning. 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ætter vi med den velkendte algoritme. Først opretter vi et objekt af klassen Node kaldet current, som vi initialiserer som head;
I stedet for at bruge en while-løkke, anvender vi en for-løkke, som er mere velegnet her, da vi kender det præcise antal iterationer, vi har brug for. Antallet af iterationer er lig med værdien af parameteren index;
Vores løkke ser således ud:
for (int i = 0; i < index; i++). I denne løkke finder vi det ønskede element ved hjælp af den velkendte operation: current = current.next;
Når vi har fundet det ønskede element, tildeler vi dets data-attribut en ny værdi ved at udføre operationen
current.data = newData. Vi henter newData fra parametrene til denne metode.

Var alt klart?

Tak for dine kommentarer!

Sektion 1. Kapitel 6

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

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 ved den længe.

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.

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 kan du se implementeringen af metoden til at tilføje et element til slutningen af listen. Lad os gennemgå, hvordan denne metode fungerer:

Vi opretter et objekt af klassen Node, newNode, og initialiserer det gennem konstruktøren, hvor vi videregiver data fra parametrene i append()-metoden;
Dernæst tjekker vi om listen er tom, og hvis den er, erstatter vi det første element i listen (head) med newNode ved omfordeling;
Derefter tilføjer vi en return-sætning for at afslutte metoden;
Hvis listen ikke er tom, opretter vi i denne metode et nyt objekt, current, som repræsenterer Node head i denne sammenhæng;
Ved hjælp af en while-løkke gennemløber vi hele listen, indtil current.next er null, hvilket betyder, at vi har fastslået, at det næste element i listen er tomt;
Når vi finder det sidste ikke-null element i listen, sætter vi dets link til newNode og tilføjer dermed elementet til vores liste.

Med andre ord var målet med append-metoden at sætte linket for det sidste element til det nye element. På denne måde tilføjer vi 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 tildele current på ny, hvilket ser således ud: current = current.next;;
Dette gentages, indtil Node current bliver tom. Herefter afsluttes løkken, og næste linje udføres.

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 kontrollerer vi, om denne index findes i vores liste ved hjælp af en if-sætning. 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ætter vi med den velkendte algoritme. Først opretter vi et objekt af klassen Node kaldet current, som vi initialiserer som head;
I stedet for at bruge en while-løkke, anvender vi en for-løkke, som er mere velegnet her, da vi kender det præcise antal iterationer, vi har brug for. Antallet af iterationer er lig med værdien af parameteren index;
Vores løkke ser således ud:
for (int i = 0; i < index; i++). I denne løkke finder vi det ønskede element ved hjælp af den velkendte operation: current = current.next;
Når vi har fundet det ønskede element, tildeler vi dets data-attribut en ny værdi ved at udføre operationen
current.data = newData. Vi henter newData fra parametrene til denne metode.

Var alt klart?

Tak for dine kommentarer!

Sektion 1. Kapitel 6