Pyyhkäise näyttääksesi valikon

Entä jos oliot olisivat linkitetty 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, 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 täytyy vastata pääkysymykseen: Mitä <E> tarkoittaa? 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äärittämä tietotyyppi korvaa sen myöhemmin.

Tätä voi 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 E item -kenttään. Tämä on olion arvo, joka tallennetaan tähän 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 ja edelliseen Node-solmuun. Tämän avulla voidaan käydä listaa läpi. Tarkastellaan tarkemmin, miten LinkedList-rakenteessa iteroidaan.

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

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

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

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

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

Algoritminen monimutkaisuus

Voit huomata, että alkion etsiminen indeksin perusteella ArrayList-rakenteessa on vakioajan operaatio, koska pääsemme suoraan käsiksi taulukon indeksiin.

Sen sijaan LinkedList-rakenteessa etsiminen 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 operaatio on vakioajan, kun taas ArrayList-rakenteessa lineaarinen. Tämä johtuu siitä, että kun lisätään alkio LinkedList-rakenteeseen, tarvitsee vain muuttaa solmujen linkityksiä uusiin, 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.

Tarkastellaanpa 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 LinkedList. Tämän jälkeen täytimme ne 1 000 000 satunnaisella kokonaisluvulla. Listoissa on samat sisällöt, kummassakin miljoona lukua väliltä 1–100.

Seuraavaksi mittasimme ajan, joka kuluu alkion lisäämiseen tuhannenteen indeksiin arvolla 50. Käytimme ajan mittaamiseen System.nanoTime()-metodia, joka näyttää nykyisen ajan nanosekunteina. Sitten kummankin listan kohdalla vähensimme aloitusajan lopetusajasta, jolloin selvisi, 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 tärkeää, kannattaa harkita, millä listatyypillä ohjelma toimii nopeammin tietyissä tapauksissa. Mutta paljastan sinulle salaisuuden: käytän melkein aina ArrayList-rakennetta.

SinglyLinkedList

On olemassa toinen piilotettu tietorakenne nimeltä SinglyLinkedList. Kuten nimi kertoo, tämä tietorakenne käyttää iteraatiota vain yhteen suuntaan. Kun LinkedList-luokan Node-oliolla on kentät: item, next ja prev, on SinglyLinkedList-luokan Node-oliolla 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 suorittaa nopeammin, jos haluamme löytää alkion indeksin perusteella?

2. Mikä tietorakenne suorittaa nopeammin poistotoiminnon yhteydessä?

3. Miten `Node`-luokka osallistuu `LinkedList`-tietorakenteen toimintaan?

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 1. Luku 6

Kysy tekoälyä

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

Osio 1. Luku 6

LinkedList Javassa

Entä jos oliot olisivat linkitetty toisiinsa?

Miten LinkedList on rakenteeltaan?

Algoritminen monimutkaisuus

SinglyLinkedList

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

2. Mikä tietorakenne suorittaa nopeammin poistotoiminnon yhteydessä?

3. Miten Node-luokka osallistuu LinkedList-tietorakenteen toimintaan?

3. Miten `Node`-luokka osallistuu `LinkedList`-tietorakenteen toimintaan?