Hvad hvis objekter var forbundet sammen?

Lad os gå videre til den næste, ret interessante datastruktur - LinkedList.

Lad os se på syntaksen og operationsskemaet for LinkedList:

Som du kan se, er syntaksen fuldstændig identisk med deklarationen af en ArrayList. Generelt kan enhver liste deklareres på denne måde.

Men det interessante begynder, når vi forsøger at forstå, hvordan LinkedList fungerer.

Hvordan er LinkedList struktureret?

Indeni fungerer LinkedList med Nodes. En Node er et objekt, der gemmes i LinkedList. Det implementeres i LinkedList på denne måde:

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

Lad os gennemgå, hvad denne klasse består af. Først skal vi besvare det centrale spørgsmål, der opstår: Hvad betyder <E>? Dette er en generisk type.

Kort sagt efterlader du her en pladsholder for den datatype, der angives under initialiseringen. Du bruger denne pladsholder i koden, som senere erstattes af den datatype, brugeren angiver.

Dette kan sammenlignes med overload.

Lad os se, hvordan det fungerer:

I stedet for at overbelaste denne metode for hver datatype, anvendes en generisk type, hvor du indsætter den datatype, metoden skal arbejde med. Bogstavet E vil blot blive erstattet med den ønskede datatype. I dette tilfælde er det Integer.

Dernæst skal vi være opmærksomme på E item-feltet. Dette er objektets værdi, som vil blive gemt i denne Node. Hvis vi opretter en liste som {0, 1, 2, 3}, vil den første node gemme elementet 0, den anden node gemme elementet 1 osv.

Dernæst ses referencer til andre Node-objekter: Node<E> next og Node<E> prev. Dette er hovedfunktionen ved en linked list. I én Node findes der en reference til den næste Node og til den forrige. Dette er måden, man gennemløber listen på. Lad os se nærmere på iterationen gennem en LinkedList.

Når man ser på en sådan skitse, kan man konkludere, at gennemløb af denne liste fungerer anderledes.

I ArrayList<>() anvender programmet under overfladen et array, der fordobles i størrelse, når antallet af elementer når 3/4 af dets kapacitet.

I en LinkedList<>() behøver vi ikke at genskabe et array, fordi der ikke er noget array i en LinkedList. I stedet, når der tilføjes et nyt element, oprettes et nyt Node-objekt, som forbindes via referencer til det forrige sidste element.

Det kan virke og lyde en smule kompliceret, men som programmør behøver du ikke selv at opsætte alt dette.

Metoderne for LinkedList er de samme som for ArrayList, da begge arver fra List-interfacet, som definerer de metoder, som alle dets efterkommere skal implementere.

Algoritmisk kompleksitet

I Collection frameworket findes der mange forskellige datastrukturer, og hver af dem har sin egen algoritmiske kompleksitet.

Algoritmisk kompleksitet angives ved hjælp af big O-notation (f.eks. O(n), O(n^2)), hvor "O" står for "big O" og angiver en øvre grænse for væksten i kørselstiden som en funktion af inputstørrelsen.

Her er de vigtigste typer af algoritmisk kompleksitet:

O(1) (konstant tid): tidskompleksitet afhænger ikke af størrelsen på inputdataene. For eksempel, adgang til et element i et array via indeks;
O(log n) (logaritmisk tid): tidskompleksitet vokser logaritmisk med størrelsen på inputdataene. Eksempel: binær søgning i et sorteret array;
O(n) (lineær tid): tidskompleksitet vokser lineært med størrelsen på inputdataene. Eksempel: gennemløb af alle elementer i en ArrayList;
O(n^2) (kvadratisk tid): tidskompleksitet er proportional med kvadratet af størrelsen på inputdataene. Eksempel: boblesortering.

Dette er grundlæggende kategorier, og der findes mange andre typer af algoritmisk kompleksitet, såsom O(n log n), O(2^n), O(n!) og andre, som karakteriserer mere komplekse algoritmer. Valg af en effektiv algoritme, med hensyn til dens kompleksitet, er et centralt aspekt af softwareudvikling.

Nu vender vi tilbage til datastrukturer i Java. Hver datastruktur har sin algoritmiske tidskompleksitet afhængigt af den operation, der skal udføres. Lad os se på tabellen:

Du kan se, at søgning efter et element via indeks i ArrayList har konstant kompleksitet, da vi blot tilgår indekset i arrayet.

I LinkedList tager søgning via indeks meget længere tid, fordi vi skal gennemløbe alle noderne og finde det ønskede objekt via indeks.

Omvendt, hvis du ser på indsættelse af et element, har LinkedList konstant kompleksitet, mens ArrayList har lineær kompleksitet. Dette skyldes, at for at indsætte et element i en LinkedList, skal vi blot ændre referencerne i noderne til nye, så elementet indsættes imellem dem. For ArrayList skal vi gengenskabe arrayet med det nye element, hvilket indebærer at kopiere det gamle array og indsætte elementet, hvilket tager meget længere tid.

Lad os 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 oprettede to lister: den ene er en ArrayList, og den anden er en LinkedList. Derefter fyldte vi dem med 1.000.000 tilfældige heltal. Listerne har det samme indhold, hver indeholder en million tal fra 1 til 100.

Dernæst målte vi tiden det tager at indsætte et element på den tusinde indeks med værdien 50. Vi brugte metoden System.nanoTime() til at måle tiden, som viser det aktuelle tidspunkt i nanosekunder. For hver liste trak vi starttiden fra sluttiden, og dermed bestemte vi hvor meget tid der blev brugt på at tilføje et element i midten af listen.

Du kan se, at LinkedList udførte væsentligt hurtigere, hvilket fremgår af tabellen. LinkedList har konstant algoritmisk kompleksitet, mens ArrayList har lineær kompleksitet.

Dette er grunden til, at vi har brug for forskellige typer lister. Hvis dit projekt håndterer store datamængder, hvor optimering er afgørende, kan det være værd at overveje, hvilken type liste programmet vil køre hurtigere med i visse tilfælde. Men jeg vil fortælle dig en hemmelighed: Jeg bruger næsten altid ArrayList.

SinglyLinkedList

Der findes en anden ikke-offentliggjort datastruktur kaldet SinglyLinkedList. Som navnet antyder, bruger denne datastruktur iteration i kun én retning. Mens LinkedList-klassens Node har felterne: item, next og prev, har SinglyLinkedList-klassens Node kun 2 felter: 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 datastruktur anvendes i strukturer såsom maps, hvor iteration kun er nødvendig i én retning. Vi vil lære om maps, især HashMap, i kommende afsnit.

I næste kapitel vil vi skrive en implementering af SinglyLinkedList for bedre at forstå, hvordan denne interessante datastruktur fungerer.

1. Hvilken datastruktur vil være hurtigere, hvis vi ønsker at finde et element via dets indeks?

2. Hvilken datastruktur vil have hurtigere ydeevne ved udførelse af en sletningsoperation?

3. Hvordan deltager `Node`-klassen i driften af `LinkedList`?

Var alt klart?

Tak for dine kommentarer!

Sektion 1. Kapitel 5

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Stryg for at vise menuen

Hvad hvis objekter var forbundet sammen?

Lad os gå videre til den næste, ret interessante datastruktur - LinkedList.

Lad os se på syntaksen og operationsskemaet for LinkedList:

Som du kan se, er syntaksen fuldstændig identisk med deklarationen af en ArrayList. Generelt kan enhver liste deklareres på denne måde.

Men det interessante begynder, når vi forsøger at forstå, hvordan LinkedList fungerer.

Hvordan er LinkedList struktureret?

Indeni fungerer LinkedList med Nodes. En Node er et objekt, der gemmes i LinkedList. Det implementeres i LinkedList på denne måde:

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

Lad os gennemgå, hvad denne klasse består af. Først skal vi besvare det centrale spørgsmål, der opstår: Hvad betyder <E>? Dette er en generisk type.

Kort sagt efterlader du her en pladsholder for den datatype, der angives under initialiseringen. Du bruger denne pladsholder i koden, som senere erstattes af den datatype, brugeren angiver.

Dette kan sammenlignes med overload.

Lad os se, hvordan det fungerer:

Når man ser på en sådan skitse, kan man konkludere, at gennemløb af denne liste fungerer anderledes.

I ArrayList<>() anvender programmet under overfladen et array, der fordobles i størrelse, når antallet af elementer når 3/4 af dets kapacitet.

Det kan virke og lyde en smule kompliceret, men som programmør behøver du ikke selv at opsætte alt dette.

Metoderne for LinkedList er de samme som for ArrayList, da begge arver fra List-interfacet, som definerer de metoder, som alle dets efterkommere skal implementere.

Algoritmisk kompleksitet

I Collection frameworket findes der mange forskellige datastrukturer, og hver af dem har sin egen algoritmiske kompleksitet.

Her er de vigtigste typer af algoritmisk kompleksitet:

O(1) (konstant tid): tidskompleksitet afhænger ikke af størrelsen på inputdataene. For eksempel, adgang til et element i et array via indeks;
O(log n) (logaritmisk tid): tidskompleksitet vokser logaritmisk med størrelsen på inputdataene. Eksempel: binær søgning i et sorteret array;
O(n) (lineær tid): tidskompleksitet vokser lineært med størrelsen på inputdataene. Eksempel: gennemløb af alle elementer i en ArrayList;
O(n^2) (kvadratisk tid): tidskompleksitet er proportional med kvadratet af størrelsen på inputdataene. Eksempel: boblesortering.

Nu vender vi tilbage til datastrukturer i Java. Hver datastruktur har sin algoritmiske tidskompleksitet afhængigt af den operation, der skal udføres. Lad os se på tabellen:

Du kan se, at søgning efter et element via indeks i ArrayList har konstant kompleksitet, da vi blot tilgår indekset i arrayet.

I LinkedList tager søgning via indeks meget længere tid, fordi vi skal gennemløbe alle noderne og finde det ønskede objekt via indeks.

Lad os 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 udførte væsentligt hurtigere, hvilket fremgår af 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 datastruktur anvendes i strukturer såsom maps, hvor iteration kun er nødvendig i én retning. Vi vil lære om maps, især HashMap, i kommende afsnit.

I næste kapitel vil vi skrive en implementering af SinglyLinkedList for bedre at forstå, hvordan denne interessante datastruktur fungerer.

1. Hvilken datastruktur vil være hurtigere, hvis vi ønsker at finde et element via dets indeks?

2. Hvilken datastruktur vil have hurtigere ydeevne ved udførelse af en sletningsoperation?

3. Hvordan deltager `Node`-klassen i driften af `LinkedList`?

Var alt klart?

Tak for dine kommentarer!

Sektion 1. Kapitel 5

Linkedlist i Java

Hvad hvis objekter var forbundet sammen?

Hvordan er LinkedList struktureret?

Algoritmisk kompleksitet

SinglyLinkedList

1. Hvilken datastruktur vil være hurtigere, hvis vi ønsker at finde et element via dets indeks?

2. Hvilken datastruktur vil have hurtigere ydeevne ved udførelse af en sletningsoperation?

3. Hvordan deltager `Node`-klassen i driften af `LinkedList`?

Linkedlist i Java

Hvad hvis objekter var forbundet sammen?

Hvordan er LinkedList struktureret?

Algoritmisk kompleksitet

SinglyLinkedList

1. Hvilken datastruktur vil være hurtigere, hvis vi ønsker at finde et element via dets indeks?

2. Hvilken datastruktur vil have hurtigere ydeevne ved udførelse af en sletningsoperation?

3. Hvordan deltager `Node`-klassen i driften af `LinkedList`?

Linkedlist i Java

Hvad hvis objekter var forbundet sammen?

Hvordan er LinkedList struktureret?

Algoritmisk kompleksitet

SinglyLinkedList

1. Hvilken datastruktur vil være hurtigere, hvis vi ønsker at finde et element via dets indeks?

2. Hvilken datastruktur vil have hurtigere ydeevne ved udførelse af en sletningsoperation?

3. Hvordan deltager Node-klassen i driften af LinkedList?

Linkedlist i Java

Hvad hvis objekter var forbundet sammen?

Hvordan er LinkedList struktureret?

Algoritmisk kompleksitet

SinglyLinkedList

1. Hvilken datastruktur vil være hurtigere, hvis vi ønsker at finde et element via dets indeks?

2. Hvilken datastruktur vil have hurtigere ydeevne ved udførelse af en sletningsoperation?

3. Hvordan deltager Node-klassen i driften af LinkedList?

3. Hvordan deltager `Node`-klassen i driften af `LinkedList`?

3. Hvordan deltager `Node`-klassen i driften af `LinkedList`?