Wat als objecten met elkaar verbonden waren?

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

Bekijk de syntaxis en het werkingsschema van LinkedList:

Zoals je ziet, 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 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.

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, gebruikt u een generiek type waarin u 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 vervolgens aandacht besteden aan het item-veld E. Dit is de waarde van het object die in deze Node wordt opgeslagen. Als we bijvoorbeeld een lijst maken zoals {0, 1, 2, 3}, zal de eerste node item 0 opslaan, de tweede node item 1, enzovoort.

Vervolgens ziet u 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 kunt u door de lijst itereren. Laten we het itereren door een LinkedList nader bekijken.

Als we naar een dergelijk schema kijken, kunnen we concluderen dat itereren door deze lijst anders werkt.

In ArrayList<>() gebruikt het programma onder de motorkap 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 klinken, maar als programmeur hoef je dit niet allemaal zelf op te zetten.

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

Algoritmische Complexiteit

Binnen het Collection framework bestaan er verschillende datastructuren, en elk daarvan heeft zijn eigen algoritmische complexiteit.

Algoritmische complexiteit wordt aangeduid met big O-notatie (bijv. O(n), O(n^2)), waarbij "O" staat voor "big O" en een bovengrens aangeeft voor de groei van de uitvoeringstijd als functie van de invoergrootte.

Hier zijn de belangrijkste typen algoritmische complexiteit:

O(1) (constante tijd): tijdcomplexiteit hangt niet af van de grootte van de invoergegevens. Bijvoorbeeld, toegang tot een element in een array via index;
O(log n) (logaritmische tijd): tijdcomplexiteit groeit logaritmisch met de grootte van de invoergegevens. Voorbeeld: binaire zoekopdracht in een gesorteerde array;
O(n) (lineaire tijd): tijdcomplexiteit groeit lineair met de grootte van de invoergegevens. Voorbeeld: itereren door alle elementen in een ArrayList;
O(n^2) (kwadratische tijd): tijdcomplexiteit is evenredig met het kwadraat van de grootte van de invoergegevens. Voorbeeld: bubblesort.

Dit zijn basis categorieën, en er zijn veel andere typen algoritmische complexiteit, zoals O(n log n), O(2^n), O(n!) en anderen, die complexere algoritmen karakteriseren. Het kiezen van een efficiënt algoritme, rekening houdend met de complexiteit, is een cruciaal aspect van softwareontwikkeling.

Nu gaan we terug naar datastructuren in Java. Elke datastructuur heeft zijn eigen algoritmische tijdcomplexiteit afhankelijk van de uit te voeren bewerking. Bekijk de tabel:

Je ziet dat zoeken naar een element op index in ArrayList constante complexiteit heeft, omdat we eenvoudig toegang krijgen tot de index in de array.

In LinkedList kost zoeken op index veel meer tijd omdat we alle knooppunten moeten doorlopen om het gewenste object op 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 om het element ertussen te plaatsen. Voor 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.

Bekijk een voorbeeld:

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 is 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 de tijd gemeten die het kost om een element met de waarde 50 toe te voegen op de duizendste index. 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 afgetrokken van de eindtijd, waardoor we bepaalden hoeveel tijd er werd besteed aan het toevoegen van een element in het midden van de lijst.

Je kunt zien dat de LinkedList aanzienlijk sneller presteerde, zoals blijkt uit de tabel. LinkedList heeft een constante algoritmische complexiteit, terwijl ArrayList een lineaire complexiteit heeft.

Dit is de reden waarom we verschillende soorten lijsten nodig hebben. Als je project met een grote hoeveelheid data werkt waarbij optimalisatie cruciaal is, is het de moeite waard om te overwegen welk type lijst in bepaalde gevallen sneller zal presteren. Maar ik zal je een geheim vertellen: ik gebruik bijna altijd ArrayList.

SinglyLinkedList

Er is een andere niet eerder besproken datastructuur genaamd SinglyLinkedList. Zoals de naam al aangeeft, gebruikt deze datastructuur iteratie in slechts één richting. Terwijl de LinkedList van de klasse Node de velden heeft: item, next en prev, heeft de SinglyLinkedList van de 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 5

Vraag AI

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

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?

Veeg om het menu te tonen

Wat als objecten met elkaar verbonden waren?

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

Bekijk de syntaxis en het werkingsschema van LinkedList:

Zoals je ziet, 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 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.

Dit kan worden vergeleken met overloading.

Laten we bekijken hoe dit werkt:

Als we naar een dergelijk schema kijken, kunnen we concluderen dat itereren door deze lijst anders werkt.

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

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

Algoritmische Complexiteit

Binnen het Collection framework bestaan er verschillende datastructuren, en elk daarvan heeft zijn eigen algoritmische complexiteit.

Hier zijn de belangrijkste typen algoritmische complexiteit:

O(1) (constante tijd): tijdcomplexiteit hangt niet af van de grootte van de invoergegevens. Bijvoorbeeld, toegang tot een element in een array via index;
O(log n) (logaritmische tijd): tijdcomplexiteit groeit logaritmisch met de grootte van de invoergegevens. Voorbeeld: binaire zoekopdracht in een gesorteerde array;
O(n) (lineaire tijd): tijdcomplexiteit groeit lineair met de grootte van de invoergegevens. Voorbeeld: itereren door alle elementen in een ArrayList;
O(n^2) (kwadratische tijd): tijdcomplexiteit is evenredig met het kwadraat van de grootte van de invoergegevens. Voorbeeld: bubblesort.

Nu gaan we terug naar datastructuren in Java. Elke datastructuur heeft zijn eigen algoritmische tijdcomplexiteit afhankelijk van de uit te voeren bewerking. Bekijk de tabel:

Je ziet dat zoeken naar een element op index in ArrayList constante complexiteit heeft, omdat we eenvoudig toegang krijgen tot de index in de array.

In LinkedList kost zoeken op index veel meer tijd omdat we alle knooppunten moeten doorlopen om het gewenste object op index te vinden.

Bekijk een voorbeeld:

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

SinglyLinkedList

Main.java


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

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

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 5

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`?

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`?

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?

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`?

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