Veeg om het menu te tonen

Wat als objecten met elkaar verbonden waren?

Laten we verder gaan met de volgende, vrij interessante datastructuur - LinkedList.

Bekijk de syntaxis en het werkingsschema van LinkedList:

Zoals te zien is, is de syntaxis volledig identiek aan het declareren van een ArrayList. In het algemeen kan elke lijst op deze manier worden gedeclareerd.

Het interessante deel begint echter wanneer we proberen te begrijpen hoe LinkedList werkt.

Hoe is LinkedList gestructureerd?

Intern werkt LinkedList met Nodes. Een Node is een object dat wordt opgeslagen in de LinkedList. Het is als volgt geïmplementeerd binnen LinkedList:

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

Laten we uiteenzetten waaruit deze klasse bestaat. Eerst moeten we de belangrijkste vraag beantwoorden die opkomt: Wat betekent <E>? Dit is een generiek type.

Eenvoudig gezegd laat je hier een tijdelijke aanduiding achter voor het gegevenstype dat tijdens de initialisatie wordt gespecificeerd. Je gebruikt deze aanduiding in de code, die later wordt vervangen door het door de gebruiker opgegeven gegevenstype.

Dit kan worden vergeleken met overloading.

Laten we bekijken hoe dit werkt:

In plaats van deze methode voor elk gegevenstype te overbelasten, gebruik je een generiek waarin je het gegevenstype invoegt waarmee de methode zal werken. De letter E wordt eenvoudigweg vervangen door het vereiste gegevenstype. In ons geval is dat Integer.

Laten we nu aandacht besteden aan het E item veld. Dit is de waarde van het object die in deze Node wordt opgeslagen. Dus, als we een lijst maken zoals {0, 1, 2, 3}, zal de eerste node item 0 opslaan, de tweede node item 1, enzovoort.

Vervolgens zie je verwijzingen naar andere Node objecten: Node<E> next en Node<E> prev. Dit is het belangrijkste kenmerk van een gekoppelde lijst. In één Node bevindt zich een verwijzing naar de volgende Node en naar de vorige. Hierdoor kun je door de lijst itereren. Laten we het itereren door een LinkedList nader bekijken.

Wanneer we naar een dergelijke schematische voorstelling kijken, kunnen we concluderen dat itereren door deze lijst anders werkt.

In ArrayList<>() gebruikt het programma onderliggend een array die verdubbelt in grootte wanneer het aantal elementen 3/4 van de capaciteit bereikt.

In een LinkedList<>() hoeven we geen array opnieuw te maken omdat er geen array is in een LinkedList. In plaats daarvan wordt bij het toevoegen van een nieuw element een nieuw Node object gecreëerd en via verwijzingen gekoppeld aan het vorige laatste element.

Het kan er ingewikkeld uitzien en zo klinken, maar als programmeur hoef je dit niet allemaal zelf op te zetten.

De methoden voor LinkedList zijn hetzelfde als die voor ArrayList, omdat ze beide erven van de List-interface, die de methoden definieert die al haar afstammelingen moeten implementeren.

Algoritmische complexiteit

Je ziet dat zoeken naar een element op index in een ArrayList constante complexiteit heeft, omdat we eenvoudigweg de index in de array benaderen.

Daarentegen kost zoeken op index in een LinkedList veel meer tijd, omdat we alle knooppunten moeten doorlopen om het gewenste object op de juiste index te vinden.

Aan de andere kant, als je kijkt naar het invoegen van een element, heeft LinkedList constante complexiteit, terwijl ArrayList lineaire complexiteit heeft. Dit komt doordat bij het invoegen van een element in een LinkedList alleen de verwijzingen in de knooppunten aangepast hoeven te worden, zodat het element ertussen geplaatst wordt. Voor een ArrayList moet de array opnieuw worden opgebouwd met het nieuwe element, wat inhoudt dat de oude array gekopieerd wordt en het element wordt ingevoegd, wat veel meer tijd kost.

Laten we naar een voorbeeld kijken:

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

We hebben twee lijsten aangemaakt: één is een ArrayList en de andere een LinkedList. Vervolgens hebben we ze gevuld met 1.000.000 willekeurige gehele getallen. De lijsten bevatten dezelfde inhoud, elk met een miljoen getallen van 1 tot 100.

Daarna hebben we gemeten hoeveel tijd het kost om een element met de waarde 50 op de duizendste index toe te voegen. We gebruikten de methode System.nanoTime() om de tijd te meten, die de huidige tijd in nanoseconden weergeeft. Vervolgens hebben we voor elke lijst de begintijd van de eindtijd afgetrokken, zodat we konden bepalen hoeveel tijd het kostte om een element in het midden van de lijst toe te voegen.

Je ziet dat de LinkedList aanzienlijk sneller was, zoals blijkt uit de tabel. LinkedList heeft constante algoritmische complexiteit, terwijl ArrayList lineaire complexiteit heeft.

Daarom hebben we verschillende typen lijsten nodig. Als je project met grote hoeveelheden data werkt waarbij optimalisatie cruciaal is, is het de moeite waard om te overwegen welk type lijst in bepaalde gevallen sneller zal zijn. Maar ik zal je een geheim verklappen: ik gebruik bijna altijd ArrayList.

SinglyLinkedList

Er is een andere niet eerder besproken datastructuur genaamd SinglyLinkedList. Zoals de naam aangeeft, gebruikt deze datastructuur iteratie in slechts één richting. Terwijl de LinkedList-klasse Node de velden: item, next en prev heeft, heeft de SinglyLinkedList-klasse Node slechts 2 velden: item en next.

Main.java


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

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

Deze datastructuur wordt gebruikt in structuren zoals maps, waar iteratie slechts in één richting nodig is. We zullen meer leren over maps, met name HashMap, in toekomstige secties.

In het volgende hoofdstuk schrijven we een implementatie van SinglyLinkedList om beter te begrijpen hoe deze interessante datastructuur werkt.

1. Welke datastructuur presteert sneller als we een element op index willen vinden?

2. Welke datastructuur presteert sneller bij het uitvoeren van een verwijderingsoperatie?

3. Hoe neemt de klasse `Node` deel aan de werking van `LinkedList`?

Was alles duidelijk?

Bedankt voor je feedback!

Sectie 1. Hoofdstuk 6

Vraag AI

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

Sectie 1. Hoofdstuk 6

Linkedlist in Java

Wat als objecten met elkaar verbonden waren?

Hoe is LinkedList gestructureerd?

Algoritmische complexiteit

SinglyLinkedList

1. Welke datastructuur presteert sneller als we een element op index willen vinden?

2. Welke datastructuur presteert sneller bij het uitvoeren van een verwijderingsoperatie?

3. Hoe neemt de klasse Node deel aan de werking van LinkedList?

3. Hoe neemt de klasse `Node` deel aan de werking van `LinkedList`?