Entä jos oliot olisivat linkitettyjä toisiinsa?

Siirrytään seuraavaan, varsin mielenkiintoiseen tietorakenteeseen – LinkedList.

Tarkastellaan LinkedList-rakenteen syntaksia ja toimintaperiaatetta:

Kuten huomaat, syntaksi on täysin identtinen ArrayList-määrittelyn kanssa. Yleisesti ottaen mikä tahansa lista voidaan määritellä tällä tavalla.

Mielenkiintoiset asiat alkavat kuitenkin, kun yritämme ymmärtää, miten LinkedList toimii.

Miten LinkedList on rakenteeltaan?

Sisäisesti LinkedList toimii Nodes-olioiden avulla. Node on olio, joka tallennetaan LinkedList-rakenteeseen. Se toteutetaan LinkedList-luokan sisällä seuraavasti:

Main.java


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Käydään läpi, mistä tämä luokka koostuu. Ensimmäiseksi tulee vastata pääkysymykseen: Mitä tarkoittaa <E>? Tämä on geneerinen tyyppi.

Yksinkertaisesti sanottuna tässä jätetään paikkamerkki tietotyypille, joka määritellään alustuksen yhteydessä. Tätä paikkamerkkiä käytetään koodissa, ja käyttäjän määrittelemä tietotyyppi korvaa sen myöhemmin.

Tätä voidaan verrata ylikuormitukseen.

Katsotaan, miten tämä toimii:

Sen sijaan, että ylikuormittaisit tämän metodin jokaiselle tietotyypille, käytät yleistä tyyppiä (generic), johon asetat sen tietotyypin, jonka kanssa metodi toimii. Kirjain E korvataan yksinkertaisesti tarvittavalla tietotyypillä. Tässä tapauksessa se on Integer.

Seuraavaksi kiinnitetään huomiota kenttään E. Tämä on olion arvo, joka tallennetaan Node-solmuun. Jos luomme listan kuten {0, 1, 2, 3}, ensimmäinen solmu tallentaa arvon 0, toinen solmu arvon 1 ja niin edelleen.

Seuraavaksi näet viittaukset muihin Node-olioihin: Node<E> next ja Node<E> prev. Tämä on linkitetyn listan pääominaisuus. Yhdessä Node-solmussa on viittaus seuraavaan Node-solmuun ja edelliseen solmuun. Tämän avulla listaa voidaan käydä läpi. Tarkastellaan, miten LinkedList-rakennetta iteroidaan.

Tarkasteltaessa tällaista kaaviota voidaan päätellä, että iteraatio tämän listan läpi toimii eri tavalla.

ArrayList<>():ssa ohjelma käyttää taustalla taulukkoa, joka kaksinkertaistaa kokonsa, kun alkioiden määrä saavuttaa 3/4 kapasiteetista.

LinkedList<>():ssa taulukkoa ei tarvitse luoda uudelleen, koska LinkedList:ssä ei ole taulukkoa. Sen sijaan, kun uusi alkio lisätään, luodaan uusi Node-olio, joka liitetään viitteillä edelliseen viimeiseen alkioon.

Se saattaa vaikuttaa ja kuulostaa hieman monimutkaiselta, mutta ohjelmoijana sinun ei tarvitse määrittää kaikkea tätä itse.

LinkedList-luokan metodit ovat samat kuin ArrayList-luokalla, koska molemmat perivät List-rajapinnasta, joka määrittelee metodit, jotka kaikkien sen jälkeläisten on toteutettava.

Algoritminen kompleksisuus

Collection framework sisältää useita erilaisia tietorakenteita, joilla jokaisella on oma algoritminen kompleksisuutensa.

Algoritminen kompleksisuus ilmaistaan big O -notaatiolla (esim. O(n), O(n^2)), jossa "O" tarkoittaa "big O" ja osoittaa ylärajan suoritusaikojen kasvulle syötteen koon funktiona.

Tässä ovat tärkeimmät algoritmisen kompleksisuuden tyypit:

O(1) (vakioaika): aikavaativuus ei riipu syötteen koosta. Esimerkiksi taulukon alkion hakeminen indeksin perusteella;
O(log n) (logaritminen aika): aikavaativuus kasvaa logaritmisesti syötteen koon mukaan. Esimerkki: binäärihaku lajitellussa taulukossa;
O(n) (lineaarinen aika): aikavaativuus kasvaa lineaarisesti syötteen koon mukaan. Esimerkki: kaikkien alkioiden läpikäynti ArrayList-rakenteessa;
O(n^2) (neliöllinen aika): aikavaativuus on verrannollinen syötteen koon neliöön. Esimerkki: kuplalajittelu.

Nämä ovat peruskategorioita, ja on olemassa monia muita algoritmisen kompleksisuuden tyyppejä, kuten O(n log n), O(2^n), O(n!) ja muita, jotka kuvaavat monimutkaisempia algoritmeja. Tehokkaan algoritmin valinta sen kompleksisuuden perusteella on olennainen osa ohjelmistokehitystä.

Palataan nyt tietorakenteisiin Javassa. Jokaisella tietorakenteella on oma algoritminen aikavaativuutensa riippuen suoritettavasta operaatiosta. Tarkastellaanpa taulukkoa:

Voit huomata, että alkion hakeminen indeksin perusteella ArrayList-rakenteessa on vakioaikaista, koska pääsemme suoraan taulukon indeksiin.

Sitä vastoin LinkedList-rakenteessa haku indeksin perusteella vie huomattavasti enemmän aikaa, koska meidän täytyy kulkea kaikki solmut läpi ja löytää haluttu objekti indeksin avulla.

Toisaalta, jos tarkastellaan alkion lisäämistä, LinkedList-rakenteessa se on vakioaikaista, kun taas ArrayList-rakenteessa lineaarista. Tämä johtuu siitä, että alkion lisäämiseksi LinkedList-rakenteeseen tarvitsee vain muuttaa solmujen linkityksiä, jolloin alkio lisätään niiden väliin. ArrayList-rakenteessa täytyy luoda uusi taulukko uudella alkiolla, mikä vaatii vanhan taulukon kopioimista ja alkion lisäämistä, mikä vie huomattavasti enemmän aikaa.

Tarkastellaan esimerkkiä:

Main.java


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

Loimme kaksi listaa: toinen on ArrayList ja toinen on LinkedList. Täytimme ne 1 000 000 satunnaisella kokonaisluvulla. Listojen sisältö on sama, kummassakin on miljoona lukua väliltä 1–100.

Seuraavaksi mittasimme ajan, joka kuluu alkion lisäämiseen tuhannenteen indeksiin arvolla 50. Käytimme ajan mittaamiseen System.nanoTime()-menetelmää, joka näyttää nykyisen ajan nanosekunteina. Jokaiselle listalle vähensimme aloitusajan lopetusajasta, jolloin selvitimme, kuinka paljon aikaa kului alkion lisäämiseen listan keskelle.

Voit huomata, että LinkedList suoriutui huomattavasti nopeammin, kuten taulukosta näkyy. LinkedList-rakenteella on vakio algoritminen kompleksisuus, kun taas ArrayList-rakenteella on lineaarinen kompleksisuus.

Tämän vuoksi tarvitsemme erilaisia listatyyppejä. Jos projektissasi käsitellään suuria tietomääriä, joissa optimointi on ratkaisevaa, kannattaa harkita, kummalla listatyypillä ohjelma toimii nopeammin tietyissä tapauksissa. Mutta paljastan sinulle salaisuuden: käytän melkein aina ArrayList-rakennetta.

SinglyLinkedList

On olemassa myös toinen tietorakenne, nimeltään SinglyLinkedList. Kuten nimestä voi päätellä, tämä tietorakenne käyttää iteraatiota vain yhteen suuntaan. Kun LinkedList-luokan Node-oliolla on kentät: item, next ja prev, SinglyLinkedList-luokan Node-oliolla on vain 2 kenttää: item ja next.

Main.java


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

Tätä tietorakennetta käytetään rakenteissa kuten mapit, joissa iteraatiota tarvitaan vain yhteen suuntaan. Opimme mapeista, erityisesti HashMap-rakenteesta, myöhemmissä osioissa.

Seuraavassa luvussa toteutamme SinglyLinkedList-luokan, jotta ymmärrämme paremmin, miten tämä mielenkiintoinen tietorakenne toimii.

1. Mikä tietorakenne toimii nopeammin, jos haluamme löytää alkion indeksin perusteella?

2. Mikä tietorakenne suorittaa poistotoiminnon nopeammin?

3. Miten `Node`-luokka osallistuu `LinkedList`:n toimintaan?

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 1. Luku 5

Kysy tekoälyä

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

Suggested prompts:

What are the main differences between ArrayList and LinkedList?

Can you explain how generics work in Java with more examples?

Why would I choose LinkedList over ArrayList in a real project?

Pyyhkäise näyttääksesi valikon

Entä jos oliot olisivat linkitettyjä toisiinsa?

Siirrytään seuraavaan, varsin mielenkiintoiseen tietorakenteeseen – LinkedList.

Tarkastellaan LinkedList-rakenteen syntaksia ja toimintaperiaatetta:

Kuten huomaat, syntaksi on täysin identtinen ArrayList-määrittelyn kanssa. Yleisesti ottaen mikä tahansa lista voidaan määritellä tällä tavalla.

Mielenkiintoiset asiat alkavat kuitenkin, kun yritämme ymmärtää, miten LinkedList toimii.

Miten LinkedList on rakenteeltaan?

Sisäisesti LinkedList toimii Nodes-olioiden avulla. Node on olio, joka tallennetaan LinkedList-rakenteeseen. Se toteutetaan LinkedList-luokan sisällä seuraavasti:

Main.java


              1234567891011
            
class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Käydään läpi, mistä tämä luokka koostuu. Ensimmäiseksi tulee vastata pääkysymykseen: Mitä tarkoittaa <E>? Tämä on geneerinen tyyppi.

Tätä voidaan verrata ylikuormitukseen.

Katsotaan, miten tämä toimii:

Tarkasteltaessa tällaista kaaviota voidaan päätellä, että iteraatio tämän listan läpi toimii eri tavalla.

ArrayList<>():ssa ohjelma käyttää taustalla taulukkoa, joka kaksinkertaistaa kokonsa, kun alkioiden määrä saavuttaa 3/4 kapasiteetista.

Se saattaa vaikuttaa ja kuulostaa hieman monimutkaiselta, mutta ohjelmoijana sinun ei tarvitse määrittää kaikkea tätä itse.

Algoritminen kompleksisuus

Collection framework sisältää useita erilaisia tietorakenteita, joilla jokaisella on oma algoritminen kompleksisuutensa.

Tässä ovat tärkeimmät algoritmisen kompleksisuuden tyypit:

O(1) (vakioaika): aikavaativuus ei riipu syötteen koosta. Esimerkiksi taulukon alkion hakeminen indeksin perusteella;
O(log n) (logaritminen aika): aikavaativuus kasvaa logaritmisesti syötteen koon mukaan. Esimerkki: binäärihaku lajitellussa taulukossa;
O(n) (lineaarinen aika): aikavaativuus kasvaa lineaarisesti syötteen koon mukaan. Esimerkki: kaikkien alkioiden läpikäynti ArrayList-rakenteessa;
O(n^2) (neliöllinen aika): aikavaativuus on verrannollinen syötteen koon neliöön. Esimerkki: kuplalajittelu.

Palataan nyt tietorakenteisiin Javassa. Jokaisella tietorakenteella on oma algoritminen aikavaativuutensa riippuen suoritettavasta operaatiosta. Tarkastellaanpa taulukkoa:

Voit huomata, että alkion hakeminen indeksin perusteella ArrayList-rakenteessa on vakioaikaista, koska pääsemme suoraan taulukon indeksiin.

Tarkastellaan esimerkkiä:

Main.java


              1234567891011121314151617181920212223242526272829
            
package com.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();

        Random random = new Random();

        for (int i = 0; i < 1000000; i++) {
            int randomValue = random.nextInt(100);
            arrayList.add(randomValue);
            linkedList.add(randomValue);
        }
        long startTimeArrayList = System.nanoTime();
        arrayList.add(1000, 50);
        long endTimeArrayList = System.nanoTime();
        long elapsedTimeArrayList = endTimeArrayList - startTimeArrayList;
        System.out.println("Time taken to put data in ArrayList: " + elapsedTimeArrayList + " nanoseconds");

        long startTimeLinkedList = System.nanoTime();
        linkedList.add(1000, 50);
        long endTimeLinkedList = System.nanoTime();
        long elapsedTimeLinkedList = endTimeLinkedList - startTimeLinkedList;
        System.out.println("Time taken to put data in LinkedList: " + elapsedTimeLinkedList + " nanoseconds");
    }
}

SinglyLinkedList

Main.java


              123456789
            
class Node<E> {
    E item;
    Node<E> next;

    Node(E element, Node<E> next) {
        this.item = element;
        this.next = next;
    }
}

Seuraavassa luvussa toteutamme SinglyLinkedList-luokan, jotta ymmärrämme paremmin, miten tämä mielenkiintoinen tietorakenne toimii.

1. Mikä tietorakenne toimii nopeammin, jos haluamme löytää alkion indeksin perusteella?

2. Mikä tietorakenne suorittaa poistotoiminnon nopeammin?

3. Miten `Node`-luokka osallistuu `LinkedList`:n toimintaan?

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 1. Luku 5

Linkedlist Javassa

Entä jos oliot olisivat linkitettyjä toisiinsa?

Miten LinkedList on rakenteeltaan?

Algoritminen kompleksisuus

SinglyLinkedList

1. Mikä tietorakenne toimii nopeammin, jos haluamme löytää alkion indeksin perusteella?

2. Mikä tietorakenne suorittaa poistotoiminnon nopeammin?

3. Miten `Node`-luokka osallistuu `LinkedList`:n toimintaan?

Linkedlist Javassa

Entä jos oliot olisivat linkitettyjä toisiinsa?

Miten LinkedList on rakenteeltaan?

Algoritminen kompleksisuus

SinglyLinkedList

1. Mikä tietorakenne toimii nopeammin, jos haluamme löytää alkion indeksin perusteella?

2. Mikä tietorakenne suorittaa poistotoiminnon nopeammin?

3. Miten `Node`-luokka osallistuu `LinkedList`:n toimintaan?

Linkedlist Javassa

Entä jos oliot olisivat linkitettyjä toisiinsa?

Miten LinkedList on rakenteeltaan?

Algoritminen kompleksisuus

SinglyLinkedList

1. Mikä tietorakenne toimii nopeammin, jos haluamme löytää alkion indeksin perusteella?

2. Mikä tietorakenne suorittaa poistotoiminnon nopeammin?

3. Miten Node-luokka osallistuu LinkedList:n toimintaan?

Linkedlist Javassa

Entä jos oliot olisivat linkitettyjä toisiinsa?

Miten LinkedList on rakenteeltaan?

Algoritminen kompleksisuus

SinglyLinkedList

1. Mikä tietorakenne toimii nopeammin, jos haluamme löytää alkion indeksin perusteella?

2. Mikä tietorakenne suorittaa poistotoiminnon nopeammin?

3. Miten Node-luokka osallistuu LinkedList:n toimintaan?

3. Miten `Node`-luokka osallistuu `LinkedList`:n toimintaan?

3. Miten `Node`-luokka osallistuu `LinkedList`:n toimintaan?