Java LinkedList

Hoi! Alle laatste lessen zijn gewijd aan ArrayList . Deze gegevensstructuur is erg handig en nuttig. Het kan tal van taken aan. Maar Java heeft veel andere datastructuren. Waarom? Vooral omdat het scala aan taken enorm is en de meest efficiënte datastructuren voor verschillende taken verschillend zijn. Vandaag maken we kennis met een nieuwe structuur: Java LinkedList , een dubbel gelinkte lijst. Laten we eens kijken hoe het is georganiseerd, waarom het dubbel gekoppeld wordt genoemd, hoe het verschilt van ArrayList . De elementen in een Java LinkedList zijn eigenlijk schakels in een enkele keten. Naast gegevens slaat elk element verwijzingen op naar de vorige en volgende elementen. Met deze verwijzingen kunt u van het ene element naar het andere gaan. Zo maak je er een aan:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Uitvoer: [Hallo wereld! Mijn naam is Earl, ik hou van Java, ik woon in Canada] Zo ziet onze lijst eruit: Laten we eens kijken hoe we een nieuw element kunnen toevoegen. Dit wordt gedaan met behulp van de add() methode.

earlBio.add(str2);

Op het punt in de code bestaat onze lijst uit één element: de String str1 . Laten we eens kijken wat er daarna gebeurt in de afbeelding: Als resultaat worden str2 en str1 gekoppeld via de volgende en vorige links die zijn opgeslagen in deze knooppunten van de lijst: Nu zou u het hoofdidee van een dubbel gekoppelde lijst moeten begrijpen. Deze ketting van links is precies wat LinkedList- elementen tot een enkele lijst maakt. In tegenstelling tot ArrayList heeft LinkedList geen array of iets dergelijks binnenin. Elk (nou ja, de meeste) werk met ArrayList komt neer op het werken met de interne array. Elk werk met Java LinkedListkomt neer op het veranderen van links. Dit is heel duidelijk te zien door een element toe te voegen aan het midden van de lijst:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Zoals u kunt zien, kunt u met de overbelaste methode add() een specifieke index voor een nieuw item specificeren. In dit geval willen we String str2 toevoegen tussen str1 en str3 . Dit is wat er intern zal gebeuren: Na het wijzigen van de interne links is str2 met succes toegevoegd aan de lijst: Nu zijn alle 3 de elementen verbonden. U kunt via de volgende schakel van het eerste element in de keten naar het laatste gaan en weer terug. Dus we zijn redelijk comfortabel met invoegen, maar hoe zit het met het verwijderen van elementen? Het principe is precies hetzelfde. We werken alleen de links bij in de twee elementen "links en rechts" van het element dat wordt verwijderd:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

Dit is wat er gebeurt als we het item met index 1 verwijderen (het staat in het midden van de lijst): Na het bijwerken van de links krijgen we het gewenste resultaat: In tegenstelling tot de verwijderingsbewerking in ArrayList , is het hier niet nodig om array-elementen te verschuiven of iets dergelijks. We hebben zojuist de links voor str1 en str3 bijgewerkt . Ze wijzen nu naar elkaar, en str2 is " uitgevallen " uit de keten van schakels en maakt geen deel meer uit van de lijst.

Overzicht methoden

LinkedList heeft veel methoden gemeen met ArrayList . Beide klassen hebben bijvoorbeeld methoden zoals add() , remove() , indexOf() , clear() , contain() (geeft aan of een item in de lijst staat), set() (vervangt een bestaand element) en maat() . Hoewel velen van hen intern anders werken (zoals we ontdekten met add() en remove() ), is het eindresultaat hetzelfde. LinkedList heeft echter aparte methoden om met het begin en einde van de lijst te werken, die ArrayList niet heeft:

• addFirst() , addLast() : Deze methoden voor het toevoegen van een element aan het begin/einde van de lijst

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Uitvoer: [Auto{model='Ferrari 360 Spider'}, Auto{model='Bugatti Veyron'}, Auto{model='Lamborghini Diablo'}] [Auto{model='Ford Mondeo'}, Auto{model=' Ferrari 360 Spider'}, Auto{model='Bugatti Veyron'}, Auto{model='Lamborghini Diablo'}, Auto{model='Fiat Ducato'}] We eindigen met "Ford" bovenaan de lijst, en "Fiat" aan het einde.

• peekFirst() , peekLast() : De methoden retourneren het eerste/laatste element in de lijst. Ze retourneren null als de lijst leeg is.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Uitvoer: Auto{model='Ferrari 360 Spider'} Auto{model='Lamborghini Diablo'}

• pollFirst() , pollLast() : Deze methoden retourneren het eerste/laatste element in de lijst en verwijderen het uit de lijst. Ze retourneren null als de lijst leeg is

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

Uitvoer: Auto{model='Ferrari 360 Spider'} Auto{model='Lamborghini Diablo'} Wat staat er nog op de lijst? [Auto{model='Bugatti Veyron'}]

• toArray() : Deze methode retourneert een array met de lijstitems

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Uitvoer: [Auto{model='Ferrari 360 Spider'}, Auto{model='Bugatti Veyron'}, Auto{model='Lamborghini Diablo'}] Nu weten we hoe LinkedList werkt en hoe de organisatie ervan verschilt van ArrayList . Wat zijn de voordelen van het gebruik van LinkedList ? Bovenal hebben we er baat bij als we in het midden van de lijst werken. Invoegen en verwijderen in het midden van een LinkedList is veel eenvoudiger dan in een ArrayList . We werken eenvoudigweg de schakels van aangrenzende elementen bij en het ongewenste element "valt" uit de keten van schakels. Maar in een ArrayList moeten we

• controleer of er voldoende ruimte is (bij insteken)
• zo niet, dan maken we een nieuwe array en kopiëren we de gegevens daarheen (bij het invoegen)
• we verwijderen/voegen het element in en verplaatsen alle andere elementen naar rechts/links (afhankelijk van het type bewerking). En de complexiteit van dit proces hangt sterk af van de grootte van de lijst. Het is één ding om 10 elementen te kopiëren/verplaatsen, en iets heel anders om hetzelfde te doen met een miljoen elementen.

Met andere woorden, als invoeg-/verwijderingsbewerkingen in het midden van de lijst het meest voorkomen in uw programma, zou LinkedList sneller moeten zijn dan ArrayList .

In theorie

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Uitvoer: tijd genomen door LinkedList (in milliseconden) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Uitvoer: tijd genomen door ArrayList (in milliseconden) = 181 Dat was onverwacht! We hebben een bewerking uitgevoerd waarbij LinkedList veel efficiënter zou moeten zijn: 100 items invoegen in het midden van een lijst. En onze lijst is enorm: 5.000.000 elementen. ArrayList moest bij elke toevoeging een paar miljoen items verschuiven! Hoe heeft het gewonnen? Ten eerste is de tijd die ArrayList nodig heeft om toegang te krijgen tot elementen vast (constant). Wanneer je schrijft

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

dan is ArrayList [2_000_000] een specifiek geheugenadres (de lijst heeft tenslotte een interne array). Maar een LinkedList heeft geen array. Het zoekt naar element nummer 2_000_000 langs de ketting van schakels. Voor LinkedList is dit geen geheugenadres, maar een link die nog bereikt moet worden: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next………… Met als resultaat dat bij elke invoeging (verwijdering) in het midden van de lijst , weet ArrayList al het exacte geheugenadres om toegang te krijgen, maar LinkedList moet er nog "komen". Ten tweede is er de structuur van de ArrayListzelf. Een speciale interne functie ( System.arrayCopy() ) breidt de interne array uit en kopieert en verschuift alle elementen. Het is erg snel, omdat het is geoptimaliseerd voor dit specifieke werk. Maar als u niet naar een bepaalde index hoeft te "gaan", is LinkedList de winnaar. Stel dat we helemaal aan het begin van de lijst invoegen. Laten we proberen daar een miljoen elementen in te voegen:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Uitvoer: Het resultaat in milliseconden: 43448 Het resultaat in milliseconden: 107 Nu krijgen we een heel ander resultaat! ArrayList besteedde meer dan 43 seconden aan het invoegen van een miljoen items aan de voorkant van de lijst, terwijl LinkedList erin slaagde om het in 0,1 seconde te doen! LinkedList profiteerde hier van, omdat het niet elke keer door de keten van links naar het midden van de lijst hoefde te lopen. Het vindt onmiddellijk de benodigde index aan het begin van de lijst, dus het andere algoritme is al een voordeel. :) In feite is de discussie " ArrayList versus LinkedList " erg wijdverbreid en we zullen er op dit moment niet diep op ingaan. Het belangrijkste dat u moet onthouden, is dit:

• Niet alle theoretische voordelen van een bepaalde collectie werken altijd in de praktijk (we zagen dit bij het voorbeeld met het midden van de lijst)
• Neem geen extreme positie in als het gaat om het kiezen van een verzameling (" ArrayList is altijd sneller. Gebruik het en je kunt niet fout gaan. Niemand gebruikt LinkedList al lang").

Hoewel zelfs de auteur van LinkedList , Joshua Bloch, zegt dat dit het geval is. :) Toch is dit perspectief verre van 100% correct, en daar hebben we onszelf van overtuigd. In ons vorige voorbeeld was LinkedList 400 (!) keer sneller. Een ander ding is dat er echt maar weinig situaties zijn waarin LinkedList de beste keuze is. Maar ze bestaan ​​wel, en op het juiste moment LinkedListkan je rijkelijk belonen. Vergeet niet wat we aan het begin van de les zeiden: de meest efficiënte datastructuren zijn verschillend voor verschillende taken. Het is onmogelijk om 100% zeker te zijn welke datastructuur het beste is totdat u alle voorwaarden van uw taak kent. Over deze collecties hoor je later meer, wat de keuze makkelijker maakt. Maar de eenvoudigste en meest effectieve optie is altijd hetzelfde: probeer beide uit op de daadwerkelijke gegevens die in uw programma worden gebruikt. Dan kun je zelf zien hoe beide soorten lijsten presteren en ga je zeker niet fout. :) Om te versterken wat je hebt geleerd, raden we je aan een videoles van onze Java-cursus te bekijken