Lære Implementering av LinkedList i Java | Grunnleggende Datastrukturer i Java

Det er på tide å utfordre deg selv med noen virkelig komplekse oppgaver.

Vi skal implementere vår forenklede datastruktur—spesifikt, SinglyLinkedList.

La oss starte med å implementere Node-klassen, som skal lagre en verdi og en referanse til neste Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

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

Implementasjonen av Node-klassen i SinglyLinkedList ble allerede demonstrert i forrige kapittel, så vi vil ikke bruke mye tid på dette.

Deretter lager vi klassen SinglyLinkedList, hvor vi definerer all logikken for vår datastruktur:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Vi opprettet feltet Node head, som skal lagre det første elementet i vår datastruktur.

I en vanlig LinkedList finnes det også en head og tail som lagrer henholdsvis det første og siste elementet i datastrukturen. Siden datastrukturen skal være tom ved initialisering, setter vi dette feltet til null i konstruktøren.

Vår datastruktur må støtte alle CRUD-operasjoner.

Opprett

La oss gå gjennom dette steg for steg og skrive en metode for å legge til et element på slutten av listen, som representerer Create-operasjonen:

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 ser du implementasjonen av metoden for å legge til et element på slutten av listen. La oss se nærmere på hvordan denne metoden fungerer:

Vi oppretter et objekt av Node-klassen, newNode, og initialiserer det gjennom konstruktøren, hvor vi sender inn data fra parameterne til append()-metoden;
Deretter sjekker vi om listen er tom, og hvis den er det, erstatter vi det første elementet i listen (head) med newNode ved omtilordning;
Så legger vi til en return-setning for å avslutte metoden;
Hvis listen ikke er tom, oppretter vi i denne metoden et nytt objekt, current, som representerer Node head i denne sammenhengen;
Ved å bruke en while-løkke itererer vi gjennom hele listen til current.next er null, altså til vi har funnet ut at neste element i listen er tomt;
Når vi finner det siste ikke-null-elementet i listen, setter vi lenken til dette elementet til newNode, og legger dermed til elementet i listen vår.

Med andre ord var målet med append-metoden å sette lenken til det siste elementet til det nye elementet. På denne måten legger vi til et nytt element i listen.

Les

La oss gå videre; nå må vi implementere leseoperasjonen.

SinglyLinkedList.java


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

Leseoperasjonen er ganske enkel. Vi må iterere gjennom hvert element i listen og skrive dem ut på skjermen. I vårt tilfelle bruker vi også plassholderen current, som vi initialiserer med Node head;
Deretter setter vi betingelsen for while-løkken til current != null og skriver ut data-feltet på skjermen;
For å iterere gjennom listen bruker vi referansen ved å tilordne på nytt current, som ser slik ut: current = current.next;;
Dette gjør vi til Node current blir tom. Etter dette går vi ut av løkken og fortsetter til neste linje.

Forresten, tenk på hvordan du kan erstatte denne while-løkken med en do-while-løkke. Er det mulig i det hele tatt?

Oppdatering

Nå går vi videre til oppdateringsmetoden, som er mer interessant i sin implementasjon:

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 sjekker vi om denne index finnes i listen vår ved hjelp av en if-setning. Hvis ikke, skriver vi ut meldingen "Invalid index" og avslutter metoden. Dette gjøres for å unngå feil;
Hvis indeksen er innenfor grensene til listen vår, fortsetter vi med den kjente algoritmen. Først oppretter vi et objekt av klassen Node kalt current, som vi initialiserer som head;
I stedet for å bruke en while-løkke, bruker vi en for-løkke, som er mer egnet her siden vi vet det eksakte antallet iterasjoner vi trenger. Antallet iterasjoner er lik verdien til parameteren index;
Løkken vår ser slik ut:
for (int i = 0; i < index; i++). I denne løkken finner vi det ønskede elementet ved hjelp av den kjente operasjonen: current = current.next;
Når vi har funnet det ønskede elementet, tildeler vi dets data-attributt en ny verdi, og utfører operasjonen
current.data = newData. Vi henter newData fra parameterne til denne metoden.

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 1. Kapittel 6

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Suggested prompts:

Can you show me the code for the append method?

How would you implement the read operation in code?

Can you explain how the update method works with an example?

Sveip for å vise menyen

Det er på tide å utfordre deg selv med noen virkelig komplekse oppgaver.

Vi skal implementere vår forenklede datastruktur—spesifikt, SinglyLinkedList.

La oss starte med å implementere Node-klassen, som skal lagre en verdi og en referanse til neste Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

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

Implementasjonen av Node-klassen i SinglyLinkedList ble allerede demonstrert i forrige kapittel, så vi vil ikke bruke mye tid på dette.

Deretter lager vi klassen SinglyLinkedList, hvor vi definerer all logikken for vår datastruktur:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Vi opprettet feltet Node head, som skal lagre det første elementet i vår datastruktur.

Vår datastruktur må støtte alle CRUD-operasjoner.

Opprett

La oss gå gjennom dette steg for steg og skrive en metode for å legge til et element på slutten av listen, som representerer Create-operasjonen:

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 ser du implementasjonen av metoden for å legge til et element på slutten av listen. La oss se nærmere på hvordan denne metoden fungerer:

Vi oppretter et objekt av Node-klassen, newNode, og initialiserer det gjennom konstruktøren, hvor vi sender inn data fra parameterne til append()-metoden;
Deretter sjekker vi om listen er tom, og hvis den er det, erstatter vi det første elementet i listen (head) med newNode ved omtilordning;
Så legger vi til en return-setning for å avslutte metoden;
Hvis listen ikke er tom, oppretter vi i denne metoden et nytt objekt, current, som representerer Node head i denne sammenhengen;
Ved å bruke en while-løkke itererer vi gjennom hele listen til current.next er null, altså til vi har funnet ut at neste element i listen er tomt;
Når vi finner det siste ikke-null-elementet i listen, setter vi lenken til dette elementet til newNode, og legger dermed til elementet i listen vår.

Med andre ord var målet med append-metoden å sette lenken til det siste elementet til det nye elementet. På denne måten legger vi til et nytt element i listen.

Les

La oss gå videre; nå må vi implementere leseoperasjonen.

SinglyLinkedList.java


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

Leseoperasjonen er ganske enkel. Vi må iterere gjennom hvert element i listen og skrive dem ut på skjermen. I vårt tilfelle bruker vi også plassholderen current, som vi initialiserer med Node head;
Deretter setter vi betingelsen for while-løkken til current != null og skriver ut data-feltet på skjermen;
For å iterere gjennom listen bruker vi referansen ved å tilordne på nytt current, som ser slik ut: current = current.next;;
Dette gjør vi til Node current blir tom. Etter dette går vi ut av løkken og fortsetter til neste linje.

Forresten, tenk på hvordan du kan erstatte denne while-løkken med en do-while-løkke. Er det mulig i det hele tatt?

Oppdatering

Nå går vi videre til oppdateringsmetoden, som er mer interessant i sin implementasjon:

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 sjekker vi om denne index finnes i listen vår ved hjelp av en if-setning. Hvis ikke, skriver vi ut meldingen "Invalid index" og avslutter metoden. Dette gjøres for å unngå feil;
Hvis indeksen er innenfor grensene til listen vår, fortsetter vi med den kjente algoritmen. Først oppretter vi et objekt av klassen Node kalt current, som vi initialiserer som head;
I stedet for å bruke en while-løkke, bruker vi en for-løkke, som er mer egnet her siden vi vet det eksakte antallet iterasjoner vi trenger. Antallet iterasjoner er lik verdien til parameteren index;
Løkken vår ser slik ut:
for (int i = 0; i < index; i++). I denne løkken finner vi det ønskede elementet ved hjelp av den kjente operasjonen: current = current.next;
Når vi har funnet det ønskede elementet, tildeler vi dets data-attributt en ny verdi, og utfører operasjonen
current.data = newData. Vi henter newData fra parameterne til denne metoden.

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 1. Kapittel 6