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

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