Tänk om objekt var länkade tillsammans?

Låt oss gå vidare till nästa, ganska intressanta datastruktur – LinkedList.

Låt oss titta på syntaxen och operationsschemat för LinkedList:

Som du kan se är syntaxen helt identisk med deklarationen av en ArrayList. Generellt kan vilken lista som helst deklareras på detta sätt.

Men det intressanta börjar när vi försöker förstå hur LinkedList fungerar.

Hur är LinkedList strukturerad?

Internt arbetar LinkedList med Nodes. En Node är ett objekt som lagras i LinkedList. Det implementeras i LinkedList på följande sätt:

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

Låt oss gå igenom vad denna klass består av. Först måste vi besvara huvudfrågan som uppstår: Vad betyder <E>? Detta är en generisk typ.

Enkelt uttryckt lämnar du här en platshållare för datatypen som kommer att anges vid initiering. Du använder denna platshållare i koden, och den kommer senare att ersättas av den datatyp som användaren anger.

Detta kan jämföras med överladdning.

Låt oss se hur det fungerar:

Istället för att överbelasta denna metod för varje datatyp används en generisk där du anger vilken datatyp metoden ska arbeta med. Bokstaven E kommer helt enkelt att ersättas med den önskade datatypen. I vårt fall är det Integer.

Låt oss nu uppmärksamma fältet item av typen E. Detta är objektets värde som kommer att lagras i denna Node. Om vi skapar en lista som {0, 1, 2, 3} kommer den första noden att lagra värdet 0, den andra noden värdet 1 och så vidare.

Därefter ser du referenser till andra Node-objekt: Node<E> next och Node<E> prev. Detta är huvudegenskapen hos en länkad lista. I en Node finns en referens till nästa Node och till den föregående. Det är så du itererar genom listan. Låt oss titta närmare på iterationen genom en LinkedList.

Genom att titta på ett sådant schema kan vi dra slutsatsen att iterering genom denna lista fungerar annorlunda.

I ArrayList<>() används under huven ett array som fördubblas i storlek när antalet element når 3/4 av dess kapacitet.

I en LinkedList<>() behöver vi inte återskapa en array eftersom det inte finns någon array i en LinkedList. Istället, när ett nytt element läggs till, skapas ett nytt Node-objekt och länkas med referenser till föregående sista element.

Det kan verka och låta lite komplicerat, men som programmerare behöver du inte konfigurera allt detta själv.

Metoderna för LinkedList är desamma som för ArrayList eftersom båda ärver från List-gränssnittet, vilket definierar de metoder som alla dess efterföljare måste implementera.

Algoritmisk komplexitet

I Collection framework finns det många olika datastrukturer, och var och en har sin algoritmiska komplexitet.

Algoritmisk komplexitet anges med big O-notation (t.ex. O(n), O(n^2)), där "O" står för "big O" och anger en övre gräns för tillväxten av körtiden som en funktion av indata-storleken.

Här är de huvudsakliga typerna av algoritmisk komplexitet:

O(1) (konstant tid): tidskomplexitet beror inte på storleken av indata. Till exempel, åtkomst till ett element i en array via index;
O(log n) (logaritmisk tid): tidskomplexitet växer logaritmiskt med storleken av indata. Exempel: binärsökning i en sorterad array;
O(n) (linjär tid): tidskomplexitet växer linjärt med storleken av indata. Exempel: iterera genom alla element i en ArrayList;
O(n^2) (kvadratisk tid): tidskomplexitet är proportionell mot kvadraten av storleken av indata. Exempel: bubblessortering.

Detta är grundläggande kategorier, och det finns många andra typer av algoritmisk komplexitet, såsom O(n log n), O(2^n), O(n!) och andra, som kännetecknar mer komplexa algoritmer. Att välja en effektiv algoritm, med hänsyn till dess komplexitet, är en avgörande aspekt av mjukvaruutveckling.

Nu återgår vi till datastrukturer i Java. Varje datastruktur har sin algoritmiska tidskomplexitet beroende på vilken operation som ska utföras. Låt oss titta på tabellen:

Du kan se att sökning efter ett element via index i ArrayList har konstant komplexitet eftersom vi helt enkelt kommer åt indexet i arrayen.

Samtidigt tar det i LinkedList mycket längre tid att söka via index eftersom vi måste traversera alla noder och hitta det objekt vi behöver via index.

Å andra sidan, om du tittar på infogning av ett element, har LinkedList konstant komplexitet, medan ArrayList har linjär komplexitet. Detta beror på att för att infoga ett element i en LinkedList behöver vi bara ändra länkarna i noderna till nya, och infoga elementet mellan dem. För ArrayList måste vi återskapa arrayen med det nya elementet, vilket innebär att kopiera den gamla arrayen och infoga elementet, vilket tar mycket mer tid.

Låt oss titta på ett exempel:

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 skapade två listor: en är en ArrayList och den andra är en LinkedList. Därefter fyllde vi dem med 1 000 000 slumpmässiga heltal. Listorna har samma innehåll, där varje innehåller en miljon tal från 1 till 100.

Sedan mätte vi tiden det tar att lägga till ett element på det tusende indexet med värdet 50. Vi använde metoden System.nanoTime() för att mäta tiden, vilket visar aktuell tid i nanosekunder. För varje lista subtraherades starttiden från sluttiden, vilket avgjorde hur mycket tid som spenderades på att lägga till ett element i mitten av listan.

Du kan se att LinkedList presterade avsevärt snabbare, vilket framgår av tabellen. LinkedList har konstant algoritmisk komplexitet, medan ArrayList har linjär komplexitet.

Detta är anledningen till att vi behöver olika typer av listor. Om ditt projekt hanterar stora datamängder där optimering är avgörande, är det värt att överväga vilken typ av lista som programmet kommer att prestera snabbare med i vissa fall. Men jag ska avslöja en hemlighet: Jag använder nästan alltid ArrayList.

SinglyLinkedList

Det finns en annan icke offentlig datastruktur som kallas SinglyLinkedList. Som namnet antyder använder denna datastruktur iteration i endast en riktning. Medan LinkedList-klassens Node har fälten: item, next och prev, har SinglyLinkedList-klassens Node endast 2 fält: item och next.

Main.java


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

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

Denna datastruktur används i strukturer såsom mappar, där iteration endast behövs i en riktning. Vi kommer att lära oss om mappar, särskilt HashMap, i kommande avsnitt.

I nästa kapitel kommer vi att skriva en implementation av SinglyLinkedList för att bättre förstå hur denna intressanta datastruktur fungerar.

1. Vilken datastruktur kommer att prestera snabbare om vi vill hitta ett element via index?

2. Vilken datastruktur presterar snabbare vid borttagningsoperationer?

3. Hur deltar klassen `Node` i funktionen hos `LinkedList`?

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 5

Fråga AI

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

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?

Svep för att visa menyn

Tänk om objekt var länkade tillsammans?

Låt oss gå vidare till nästa, ganska intressanta datastruktur – LinkedList.

Låt oss titta på syntaxen och operationsschemat för LinkedList:

Som du kan se är syntaxen helt identisk med deklarationen av en ArrayList. Generellt kan vilken lista som helst deklareras på detta sätt.

Men det intressanta börjar när vi försöker förstå hur LinkedList fungerar.

Hur är LinkedList strukturerad?

Internt arbetar LinkedList med Nodes. En Node är ett objekt som lagras i LinkedList. Det implementeras i LinkedList på följande sätt:

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

Låt oss gå igenom vad denna klass består av. Först måste vi besvara huvudfrågan som uppstår: Vad betyder <E>? Detta är en generisk typ.

Detta kan jämföras med överladdning.

Låt oss se hur det fungerar:

Genom att titta på ett sådant schema kan vi dra slutsatsen att iterering genom denna lista fungerar annorlunda.

I ArrayList<>() används under huven ett array som fördubblas i storlek när antalet element når 3/4 av dess kapacitet.

Det kan verka och låta lite komplicerat, men som programmerare behöver du inte konfigurera allt detta själv.

Algoritmisk komplexitet

I Collection framework finns det många olika datastrukturer, och var och en har sin algoritmiska komplexitet.

Här är de huvudsakliga typerna av algoritmisk komplexitet:

O(1) (konstant tid): tidskomplexitet beror inte på storleken av indata. Till exempel, åtkomst till ett element i en array via index;
O(log n) (logaritmisk tid): tidskomplexitet växer logaritmiskt med storleken av indata. Exempel: binärsökning i en sorterad array;
O(n) (linjär tid): tidskomplexitet växer linjärt med storleken av indata. Exempel: iterera genom alla element i en ArrayList;
O(n^2) (kvadratisk tid): tidskomplexitet är proportionell mot kvadraten av storleken av indata. Exempel: bubblessortering.

Nu återgår vi till datastrukturer i Java. Varje datastruktur har sin algoritmiska tidskomplexitet beroende på vilken operation som ska utföras. Låt oss titta på tabellen:

Du kan se att sökning efter ett element via index i ArrayList har konstant komplexitet eftersom vi helt enkelt kommer åt indexet i arrayen.

Samtidigt tar det i LinkedList mycket längre tid att söka via index eftersom vi måste traversera alla noder och hitta det objekt vi behöver via index.

Låt oss titta på ett exempel:

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 att LinkedList presterade avsevärt snabbare, vilket framgår av tabellen. LinkedList har konstant algoritmisk komplexitet, medan ArrayList har linjär komplexitet.

SinglyLinkedList

Main.java


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

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

Denna datastruktur används i strukturer såsom mappar, där iteration endast behövs i en riktning. Vi kommer att lära oss om mappar, särskilt HashMap, i kommande avsnitt.

I nästa kapitel kommer vi att skriva en implementation av SinglyLinkedList för att bättre förstå hur denna intressanta datastruktur fungerar.

1. Vilken datastruktur kommer att prestera snabbare om vi vill hitta ett element via index?

2. Vilken datastruktur presterar snabbare vid borttagningsoperationer?

3. Hur deltar klassen `Node` i funktionen hos `LinkedList`?

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 5

Linkedlist i Java

Tänk om objekt var länkade tillsammans?

Hur är LinkedList strukturerad?

Algoritmisk komplexitet

SinglyLinkedList

1. Vilken datastruktur kommer att prestera snabbare om vi vill hitta ett element via index?

2. Vilken datastruktur presterar snabbare vid borttagningsoperationer?

3. Hur deltar klassen `Node` i funktionen hos `LinkedList`?

Linkedlist i Java

Tänk om objekt var länkade tillsammans?

Hur är LinkedList strukturerad?

Algoritmisk komplexitet

SinglyLinkedList

1. Vilken datastruktur kommer att prestera snabbare om vi vill hitta ett element via index?

2. Vilken datastruktur presterar snabbare vid borttagningsoperationer?

3. Hur deltar klassen `Node` i funktionen hos `LinkedList`?

Linkedlist i Java

Tänk om objekt var länkade tillsammans?

Hur är LinkedList strukturerad?

Algoritmisk komplexitet

SinglyLinkedList

1. Vilken datastruktur kommer att prestera snabbare om vi vill hitta ett element via index?

2. Vilken datastruktur presterar snabbare vid borttagningsoperationer?

3. Hur deltar klassen Node i funktionen hos LinkedList?

Linkedlist i Java

Tänk om objekt var länkade tillsammans?

Hur är LinkedList strukturerad?

Algoritmisk komplexitet

SinglyLinkedList

1. Vilken datastruktur kommer att prestera snabbare om vi vill hitta ett element via index?

2. Vilken datastruktur presterar snabbare vid borttagningsoperationer?

3. Hur deltar klassen Node i funktionen hos LinkedList?

3. Hur deltar klassen `Node` i funktionen hos `LinkedList`?

3. Hur deltar klassen `Node` i funktionen hos `LinkedList`?