Svep för att visa menyn

Vad händer om objekt länkas samman?

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?

Inuti fungerar 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 analysera vad denna klass består av. Först behöver 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 specificeras vid initiering. Du använder denna platshållare i koden, vilken sedan ersätts av användarens angivna datatyp.

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 ersätts helt enkelt med önskad datatyp. I vårt fall är det Integer.

Låt oss nu uppmärksamma fältet item 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 objektet 0, den andra noden objektet 1 och så vidare.

Därefter ser du referenser till andra Node-objekt: Node<E> next och Node<E> prev. Detta är den huvudsakliga egenskapen hos en länkad lista. I en Node finns en referens till nästa Node och till föregående. Det är så man 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 en 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 det tidigare sista elementet.

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

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 betydligt längre tid att söka via index eftersom vi måste traversera alla noder och hitta objektet 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 betydligt 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. Sedan 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.

Därefter 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, som visar aktuell tid i nanosekunder. Sedan, för varje lista, subtraherade vi starttiden från sluttiden, och på så sätt fastställde vi hur mycket tid som spenderades på att lägga till ett element i mitten av listan.

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

Det är därför 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 avslöjad 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 presterar 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 6

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

Avsnitt 1. Kapitel 6

Linkedlist i Java

Vad händer om objekt länkas samman?

Hur är LinkedList strukturerad?

Algoritmisk komplexitet

SinglyLinkedList

1. Vilken datastruktur presterar 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`?