Stryg for at vise menuen

Hvad hvis objekter var forbundet sammen?

Lad os gå videre til den næste, ganske 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 initialisering. Du bruger denne pladsholder i koden, som senere erstattes af den datatype, brugeren har angivet.

Dette kan sammenlignes med overloading.

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 bør der lægges mærke til E item-feltet. Dette er objektets værdi, som vil blive gemt i denne Node. Hvis der oprettes en liste som {0, 1, 2, 3}, vil den første node gemme elementet 0, den anden node gemmer elementet 1 osv.

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

Ved at betragte en sådan skitse kan det konkluderes, at gennemløb af denne liste fungerer anderledes.

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

I en LinkedList<>() er det ikke nødvendigt at genskabe et array, fordi der ikke findes et 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 tidligere 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

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 derimod meget længere tid, fordi vi skal gennemløbe alle noderne og finde det ønskede objekt via indekset.

Hvis du derimod 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 forbindelserne i noderne til nye, så elementet indsættes imellem dem. For ArrayList skal vi genskabe 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 med en million tal fra 1 til 100.

Dernæst målte vi tiden det tager at tilføje et element på det tusinde indeks med værdien 50. Vi brugte metoden System.nanoTime() til at måle tiden, som viser aktuel tid i nanosekunder. For hver liste trak vi starttiden fra sluttiden og bestemte dermed, hvor lang tid det tog at tilføje et element midt i listen.

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

Derfor har vi brug for forskellige typer lister. Hvis dit projekt håndterer store datamængder, hvor optimering er afgørende, bør du overveje, hvilken type liste programmet vil køre hurtigst 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, anvender denne datastruktur iteration i kun én retning. Hvor 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 at opnå en bedre forståelse af, hvordan denne interessante datastruktur fungerer.

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

2. Hvilken datastruktur vil udføre hurtigere ved sletningsoperation?

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

Var alt klart?

Tak for dine kommentarer!

Sektion 1. Kapitel 6

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

Sektion 1. Kapitel 6

Linkedlist i Java

Hvad hvis objekter var forbundet sammen?

Hvordan er LinkedList struktureret?

Algoritmisk kompleksitet

SinglyLinkedList

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

2. Hvilken datastruktur vil udføre hurtigere ved sletningsoperation?

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

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