Oppiskele Linkedlist-Toteutus Javassa | Perusrakenteet Javassa

On aika haastaa itsesi todella monimutkaisilla tehtävillä.

Toteutamme oman yksinkertaistetun tietorakenteemme—tarkemmin sanottuna SinglyLinkedList-rakenteen.

Aloitetaan toteuttamalla Node-luokka, joka tallentaa arvon ja viitteen seuraavaan Node-olioon.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

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

Node-luokan toteutus SinglyLinkedList-rakenteessa esiteltiin jo edellisessä luvussa, joten emme käsittele sitä tässä tarkemmin.

Seuraavaksi luodaan SinglyLinkedList-luokka, jossa määritellään kaikki tietorakenteen logiikka:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Luoimme kentän Node head, joka tallentaa ensimmäisen alkion tietorakenteessa.

Tavallisessa LinkedList-rakenteessa on myös head ja tail, jotka tallentavat tietorakenteen ensimmäisen ja viimeisen alkion. Koska tietorakenteen tulee olla tyhjä alustettaessa, asetamme tämän kentän arvoksi null konstruktorissa.

Tietorakenteen tulee tukea kaikkia CRUD-operaatioita.

Luo

Käydään vaihe vaiheelta läpi, kuinka kirjoitetaan menetelmä, joka lisää alkion listan loppuun, eli toteuttaa Create-toiminnon:

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

Yllä on esitetty menetelmän toteutus, jolla lisätään alkio listan loppuun. Tarkastellaan, miten tämä menetelmä toimii:

Luodaan Node-luokan olio, newNode, ja alustetaan se konstruktorin avulla, välittäen data append()-menetelmän parametreista;
Seuraavaksi tarkistetaan, onko lista tyhjä, ja jos on, korvataan listan ensimmäinen alkio (head) newNode:lla uudelleenosoituksella;
Lisätään return-lauseke menetelmästä poistumista varten;
Jos lista ei ole tyhjä, tässä menetelmässä luodaan uusi olio, current, joka edustaa tässä yhteydessä Node head -alkiota;
while-silmukkaa käyttäen iteraatio käydään koko listan läpi kunnes current.next on null, eli kunnes havaitaan, että seuraava alkio listassa on tyhjä;
Kun löydetään viimeinen ei-null-alkio listasta, asetetaan sen linkki osoittamaan newNode:iin, jolloin alkio lisätään listaan.

Toisin sanoen, append-menetelmän tavoitteena oli asettaa viimeisen alkion linkki osoittamaan uuteen alkioon. Näin uusi alkio lisätään listaan.

Luku

Jatketaan eteenpäin; nyt meidän täytyy toteuttaa lukuoperaatio.

SinglyLinkedList.java


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

Lukuoperaatio on varsin yksinkertainen. Meidän täytyy iteraoida jokainen listan alkio ja tulostaa ne näytölle. Tässä tapauksessa käytämme myös väliaikaista muuttujaa current, joka alustetaan arvolla Node head;
Seuraavaksi asetamme ehdon while-silmukalle: current != null ja tulostamme data-kentän näytölle;
Listan läpikäyntiin käytämme viitteen uudelleenasetusta current, joka näyttää tältä: current = current.next;;
Toistamme tämän, kunnes Node current on tyhjä. Tämän jälkeen poistutaan silmukasta ja siirrytään seuraavalle riville.

Muuten, pohdi miten tämän while-silmukan voisi korvata do-while-silmukalla. Onko se ylipäätään mahdollista?

Päivittäminen

Seuraavaksi siirrytään päivitysmetodiin, jonka toteutus on mielenkiintoisempi:

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

Ensin tarkistetaan, onko tämä index listassamme käyttämällä if-lausetta. Jos ei ole, tulostetaan viesti "Invalid index" ja lopetetaan metodi. Tämä tehdään virheiden välttämiseksi;
Jos indeksi on listan rajojen sisällä, jatketaan tutulla algoritmilla. Ensin luodaan Node-luokan olio nimeltä current, joka alustetaan arvolla head;
while-silmukan sijaan käytetään for-silmukkaa, joka on tässä sopivampi, koska tiedetään tarkka toistojen määrä. Toistojen määrä on yhtä suuri kuin index-parametrin arvo;
Silmukka näyttää tältä:
for (int i = 0; i < index; i++). Tässä silmukassa etsitään haluttu alkio käyttämällä tuttua operaatiota: current = current.next;
Kun haluttu alkio on löydetty, sen data-attribuutille annetaan uusi arvo suorittamalla operaatio
current.data = newData. newData otetaan tämän metodin parametreista.

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 1. Luku 6

Kysy tekoälyä

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

Pyyhkäise näyttääksesi valikon

On aika haastaa itsesi todella monimutkaisilla tehtävillä.

Toteutamme oman yksinkertaistetun tietorakenteemme—tarkemmin sanottuna SinglyLinkedList-rakenteen.

Aloitetaan toteuttamalla Node-luokka, joka tallentaa arvon ja viitteen seuraavaan Node-olioon.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

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

Node-luokan toteutus SinglyLinkedList-rakenteessa esiteltiin jo edellisessä luvussa, joten emme käsittele sitä tässä tarkemmin.

Seuraavaksi luodaan SinglyLinkedList-luokka, jossa määritellään kaikki tietorakenteen logiikka:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Luoimme kentän Node head, joka tallentaa ensimmäisen alkion tietorakenteessa.

Tietorakenteen tulee tukea kaikkia CRUD-operaatioita.

Luo

Käydään vaihe vaiheelta läpi, kuinka kirjoitetaan menetelmä, joka lisää alkion listan loppuun, eli toteuttaa Create-toiminnon:

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

Yllä on esitetty menetelmän toteutus, jolla lisätään alkio listan loppuun. Tarkastellaan, miten tämä menetelmä toimii:

Luodaan Node-luokan olio, newNode, ja alustetaan se konstruktorin avulla, välittäen data append()-menetelmän parametreista;
Seuraavaksi tarkistetaan, onko lista tyhjä, ja jos on, korvataan listan ensimmäinen alkio (head) newNode:lla uudelleenosoituksella;
Lisätään return-lauseke menetelmästä poistumista varten;
Jos lista ei ole tyhjä, tässä menetelmässä luodaan uusi olio, current, joka edustaa tässä yhteydessä Node head -alkiota;
while-silmukkaa käyttäen iteraatio käydään koko listan läpi kunnes current.next on null, eli kunnes havaitaan, että seuraava alkio listassa on tyhjä;
Kun löydetään viimeinen ei-null-alkio listasta, asetetaan sen linkki osoittamaan newNode:iin, jolloin alkio lisätään listaan.

Toisin sanoen, append-menetelmän tavoitteena oli asettaa viimeisen alkion linkki osoittamaan uuteen alkioon. Näin uusi alkio lisätään listaan.

Luku

Jatketaan eteenpäin; nyt meidän täytyy toteuttaa lukuoperaatio.

SinglyLinkedList.java


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

Lukuoperaatio on varsin yksinkertainen. Meidän täytyy iteraoida jokainen listan alkio ja tulostaa ne näytölle. Tässä tapauksessa käytämme myös väliaikaista muuttujaa current, joka alustetaan arvolla Node head;
Seuraavaksi asetamme ehdon while-silmukalle: current != null ja tulostamme data-kentän näytölle;
Listan läpikäyntiin käytämme viitteen uudelleenasetusta current, joka näyttää tältä: current = current.next;;
Toistamme tämän, kunnes Node current on tyhjä. Tämän jälkeen poistutaan silmukasta ja siirrytään seuraavalle riville.

Muuten, pohdi miten tämän while-silmukan voisi korvata do-while-silmukalla. Onko se ylipäätään mahdollista?

Päivittäminen

Seuraavaksi siirrytään päivitysmetodiin, jonka toteutus on mielenkiintoisempi:

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

Ensin tarkistetaan, onko tämä index listassamme käyttämällä if-lausetta. Jos ei ole, tulostetaan viesti "Invalid index" ja lopetetaan metodi. Tämä tehdään virheiden välttämiseksi;
Jos indeksi on listan rajojen sisällä, jatketaan tutulla algoritmilla. Ensin luodaan Node-luokan olio nimeltä current, joka alustetaan arvolla head;
while-silmukan sijaan käytetään for-silmukkaa, joka on tässä sopivampi, koska tiedetään tarkka toistojen määrä. Toistojen määrä on yhtä suuri kuin index-parametrin arvo;
Silmukka näyttää tältä:
for (int i = 0; i < index; i++). Tässä silmukassa etsitään haluttu alkio käyttämällä tuttua operaatiota: current = current.next;
Kun haluttu alkio on löydetty, sen data-attribuutille annetaan uusi arvo suorittamalla operaatio
current.data = newData. newData otetaan tämän metodin parametreista.

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 1. Luku 6