Hva om objekter var lenket sammen?

La oss gå videre til neste, ganske interessante datastruktur – LinkedList.

La oss se på syntaksen og operasjonsskjemaet til LinkedList:

Som du ser, er syntaksen helt identisk med deklarasjonen av en ArrayList. Generelt kan enhver liste deklareres på denne måten.

Men det interessante begynner når vi prøver å forstå hvordan LinkedList fungerer.

Hvordan er LinkedList strukturert?

Inni fungerer LinkedList med Nodes. En Node er et objekt som lagres i LinkedList. Det er implementert i LinkedList slik:

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

La oss se nærmere på hva denne klassen består av. Først må vi svare på hovedspørsmålet som oppstår: Hva betyr <E>? Dette er en generisk type.

Enkelt forklart, her setter du inn en plassholder for datatypen som skal spesifiseres under initialisering. Du bruker denne plassholderen i koden, som senere blir erstattet av datatypen brukeren angir.

Dette kan sammenlignes med overlasting.

La oss se hvordan det fungerer:

I stedet for å overbelaste denne metoden for hver datatype, bruker du en generisk der du setter inn datatypen metoden skal arbeide med. Bokstaven E vil rett og slett bli erstattet med ønsket datatype. I vårt tilfelle er det Integer.

La oss deretter se nærmere på E-item-feltet. Dette er objektets verdi som vil bli lagret i denne Node-en. Hvis vi for eksempel oppretter en liste som {0, 1, 2, 3}, vil den første noden lagre elementet 0, den andre noden lagrer elementet 1, og så videre.

Videre ser du referanser til andre Node-objekter: Node<E> next og Node<E> prev. Dette er hovedfunksjonen til en lenket liste. I én Node finnes det en referanse til neste Node og til den forrige. Slik itererer du gjennom listen. La oss se nærmere på iterasjon gjennom en LinkedList.

Når vi ser på et slikt skjema, kan vi konkludere med at iterasjon gjennom denne listen fungerer annerledes.

I ArrayList<>() bruker programmet under panseret et array som dobler størrelsen når antall elementer når 3/4 av kapasiteten.

I en LinkedList<>() trenger vi ikke å gjenskape et array fordi det ikke finnes noe array i en LinkedList. I stedet, når du legger til et nytt element, blir et nytt Node-objekt opprettet og koblet sammen med referanser til forrige siste element.

Det kan virke og høres litt komplisert ut, men som programmerer trenger du ikke å sette opp alt dette selv.

Metodene for LinkedList er de samme som for ArrayList fordi begge arver fra List-grensesnittet, som definerer metodene som alle dets etterkommere må implementere.

Algoritmisk kompleksitet

I Collection framework finnes det mange ulike datastrukturer, og hver av dem har sin egen algoritmiske kompleksitet.

Algoritmisk kompleksitet angis med big O-notasjon (f.eks. O(n), O(n^2)), hvor "O" står for "big O" og indikerer en øvre grense for veksten i kjøretid som en funksjon av inputstørrelsen.

Her er hovedtypene av algoritmisk kompleksitet:

O(1) (konstant tid): tidskompleksitet avhenger ikke av størrelsen på inndataene. For eksempel, tilgang til et element i en tabell ved indeks;
O(log n) (logaritmisk tid): tidskompleksitet vokser logaritmisk med størrelsen på inndataene. Eksempel: binærsøk i en sortert tabell;
O(n) (lineær tid): tidskompleksitet vokser lineært med størrelsen på inndataene. Eksempel: iterering gjennom alle elementene i en ArrayList;
O(n^2) (kvadratisk tid): tidskompleksitet er proporsjonal med kvadratet av størrelsen på inndataene. Eksempel: boblesortering.

Dette er grunnleggende kategorier, og det finnes mange andre typer algoritmisk kompleksitet, som O(n log n), O(2^n), O(n!) og andre, som kjennetegner mer komplekse algoritmer. Valg av en effektiv algoritme, med hensyn til kompleksitet, er et avgjørende aspekt ved programvareutvikling.

Nå skal vi gå tilbake til datastrukturer i Java. Hver datastruktur har sin algoritmiske tidskompleksitet avhengig av operasjonen som skal utføres. La oss se på tabellen:

Du kan se at søk etter et element ved indeks i ArrayList har konstant kompleksitet siden vi ganske enkelt tilgår indeksen i tabellen.

I LinkedList derimot, tar søk etter indeks mye lengre tid fordi vi må gå gjennom alle nodene og finne objektet vi trenger ved indeks.

På den annen side, hvis du ser på innsetting av et element, har LinkedList konstant kompleksitet, mens ArrayList har lineær kompleksitet. Dette skjer fordi for å sette inn et element i en LinkedList, trenger vi bare å endre koblingene i nodene til nye, og sette inn elementet mellom dem. For ArrayList må vi rekonstruere tabellen med det nye elementet, noe som innebærer å kopiere den gamle tabellen og sette inn elementet, noe som tar mye mer tid.

La oss se på et eksempel:

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

Vi opprettet to lister: én er en ArrayList, og den andre er en LinkedList. Deretter fylte vi dem med 1 000 000 tilfeldige heltall. Listene har samme innhold, hver inneholder en million tall fra 1 til 100.

Deretter målte vi tiden det tar å legge til et element på tusende indeks med verdien 50. Vi brukte metoden System.nanoTime() for å måle tid, som viser nåværende tid i nanosekunder. For hver liste trakk vi starttidspunktet fra sluttidspunktet, og dermed fastslo vi hvor mye tid som ble brukt på å legge til et element midt i listen.

Du kan se at LinkedList utførte betydelig raskere, noe som fremgår av tabellen. LinkedList har konstant algoritmisk kompleksitet, mens ArrayList har lineær kompleksitet.

Dette er grunnen til at vi trenger ulike typer lister. Hvis prosjektet ditt håndterer store datamengder hvor optimalisering er avgjørende, kan det være verdt å vurdere hvilken type liste programmet vil utføre raskest i visse tilfeller. Men jeg skal fortelle deg en hemmelighet: Jeg bruker nesten alltid ArrayList.

SinglyLinkedList

Det finnes en annen ikke-offentlig datastruktur kalt SinglyLinkedList. Som navnet antyder, bruker denne datastrukturen iterasjon i kun én retning. Mens LinkedList-klassens Node har feltene: item, next og prev, har SinglyLinkedList-klassens Node kun 2 felt: item og next.

Main.java


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

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

Denne datastrukturen brukes i strukturer som kart, hvor iterasjon kun er nødvendig i én retning. Vi vil lære om kart, spesielt HashMap, i senere seksjoner.

I neste kapittel skal vi skrive en implementasjon av SinglyLinkedList for å forstå bedre hvordan denne interessante datastrukturen fungerer.

1. Hvilken datastruktur vil være raskest dersom vi ønsker å finne et element ved indeks?

2. Hvilken datastruktur vil utføre en slettingsoperasjon raskest?

3. Hvordan deltar `Node`-klassen i operasjonen til `LinkedList`?

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 1. Kapittel 5

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

Hva om objekter var lenket sammen?

La oss gå videre til neste, ganske interessante datastruktur – LinkedList.

La oss se på syntaksen og operasjonsskjemaet til LinkedList:

Som du ser, er syntaksen helt identisk med deklarasjonen av en ArrayList. Generelt kan enhver liste deklareres på denne måten.

Men det interessante begynner når vi prøver å forstå hvordan LinkedList fungerer.

Hvordan er LinkedList strukturert?

Inni fungerer LinkedList med Nodes. En Node er et objekt som lagres i LinkedList. Det er implementert i LinkedList slik:

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

La oss se nærmere på hva denne klassen består av. Først må vi svare på hovedspørsmålet som oppstår: Hva betyr <E>? Dette er en generisk type.

Dette kan sammenlignes med overlasting.

La oss se hvordan det fungerer:

Når vi ser på et slikt skjema, kan vi konkludere med at iterasjon gjennom denne listen fungerer annerledes.

I ArrayList<>() bruker programmet under panseret et array som dobler størrelsen når antall elementer når 3/4 av kapasiteten.

Det kan virke og høres litt komplisert ut, men som programmerer trenger du ikke å sette opp alt dette selv.

Metodene for LinkedList er de samme som for ArrayList fordi begge arver fra List-grensesnittet, som definerer metodene som alle dets etterkommere må implementere.

Algoritmisk kompleksitet

I Collection framework finnes det mange ulike datastrukturer, og hver av dem har sin egen algoritmiske kompleksitet.

Her er hovedtypene av algoritmisk kompleksitet:

O(1) (konstant tid): tidskompleksitet avhenger ikke av størrelsen på inndataene. For eksempel, tilgang til et element i en tabell ved indeks;
O(log n) (logaritmisk tid): tidskompleksitet vokser logaritmisk med størrelsen på inndataene. Eksempel: binærsøk i en sortert tabell;
O(n) (lineær tid): tidskompleksitet vokser lineært med størrelsen på inndataene. Eksempel: iterering gjennom alle elementene i en ArrayList;
O(n^2) (kvadratisk tid): tidskompleksitet er proporsjonal med kvadratet av størrelsen på inndataene. Eksempel: boblesortering.

Nå skal vi gå tilbake til datastrukturer i Java. Hver datastruktur har sin algoritmiske tidskompleksitet avhengig av operasjonen som skal utføres. La oss se på tabellen:

Du kan se at søk etter et element ved indeks i ArrayList har konstant kompleksitet siden vi ganske enkelt tilgår indeksen i tabellen.

I LinkedList derimot, tar søk etter indeks mye lengre tid fordi vi må gå gjennom alle nodene og finne objektet vi trenger ved indeks.

La oss se på et eksempel:

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

Du kan se at LinkedList utførte betydelig raskere, noe som fremgår av tabellen. LinkedList har konstant algoritmisk kompleksitet, mens ArrayList har lineær kompleksitet.

SinglyLinkedList

Main.java


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

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

Denne datastrukturen brukes i strukturer som kart, hvor iterasjon kun er nødvendig i én retning. Vi vil lære om kart, spesielt HashMap, i senere seksjoner.

I neste kapittel skal vi skrive en implementasjon av SinglyLinkedList for å forstå bedre hvordan denne interessante datastrukturen fungerer.

1. Hvilken datastruktur vil være raskest dersom vi ønsker å finne et element ved indeks?

2. Hvilken datastruktur vil utføre en slettingsoperasjon raskest?

3. Hvordan deltar `Node`-klassen i operasjonen til `LinkedList`?

Alt var klart?

Takk for tilbakemeldingene dine!

Seksjon 1. Kapittel 5

LinkedList i Java

Hva om objekter var lenket sammen?

Hvordan er LinkedList strukturert?

Algoritmisk kompleksitet

SinglyLinkedList

1. Hvilken datastruktur vil være raskest dersom vi ønsker å finne et element ved indeks?

2. Hvilken datastruktur vil utføre en slettingsoperasjon raskest?

3. Hvordan deltar `Node`-klassen i operasjonen til `LinkedList`?

LinkedList i Java

Hva om objekter var lenket sammen?

Hvordan er LinkedList strukturert?

Algoritmisk kompleksitet

SinglyLinkedList

1. Hvilken datastruktur vil være raskest dersom vi ønsker å finne et element ved indeks?

2. Hvilken datastruktur vil utføre en slettingsoperasjon raskest?

3. Hvordan deltar `Node`-klassen i operasjonen til `LinkedList`?

LinkedList i Java

Hva om objekter var lenket sammen?

Hvordan er LinkedList strukturert?

Algoritmisk kompleksitet

SinglyLinkedList

1. Hvilken datastruktur vil være raskest dersom vi ønsker å finne et element ved indeks?

2. Hvilken datastruktur vil utføre en slettingsoperasjon raskest?

3. Hvordan deltar Node-klassen i operasjonen til LinkedList?

LinkedList i Java

Hva om objekter var lenket sammen?

Hvordan er LinkedList strukturert?

Algoritmisk kompleksitet

SinglyLinkedList

1. Hvilken datastruktur vil være raskest dersom vi ønsker å finne et element ved indeks?

2. Hvilken datastruktur vil utføre en slettingsoperasjon raskest?

3. Hvordan deltar Node-klassen i operasjonen til LinkedList?

3. Hvordan deltar `Node`-klassen i operasjonen til `LinkedList`?

3. Hvordan deltar `Node`-klassen i operasjonen til `LinkedList`?