Java Linked List

Hej! Alle de seneste lektioner er blevet afsat til ArrayList . Denne datastruktur er meget praktisk og nyttig. Den kan klare mange opgaver. Men Java har masser af andre datastrukturer. Hvorfor? Frem for alt fordi rækken af ​​opgaver er enorm, og de mest effektive datastrukturer er forskellige til forskellige opgaver. I dag møder vi en ny struktur: Java LinkedList , en dobbelt-linket liste. Lad os se, hvordan det er organiseret, hvorfor det kaldes dobbeltlinket, hvordan det adskiller sig fra ArrayList . Elementerne i en Java LinkedList er faktisk links i en enkelt kæde. Ud over data gemmer hvert element referencer til de forrige og næste elementer. Disse referencer lader dig flytte fra et element til et andet. Sådan opretter du en:

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

   }
}

Output: [Hej verden! Mit navn er Earl, jeg elsker Java, jeg bor i Canada] Sådan ser vores liste ud: Lad os se, hvordan du tilføjer et nyt element. Dette gøres ved hjælp af add() metoden.

earlBio.add(str2);

På punktet i koden består vores liste af ét element: String str1 . Lad os se, hvad der derefter sker på billedet: Som et resultat bliver str2 og str1 forbundet via de næste og forrige links, der er gemt i denne noder på listen: Nu skulle du forstå hovedideen med en dobbelt-linket liste. Denne kæde af links er netop det, der gør LinkedList- elementer til en enkelt liste. I modsætning til ArrayList har LinkedList ikke et array eller noget array-lignende indeni. Ethvert (vel, de fleste) arbejde med ArrayList bunder i at arbejde med det interne array. Alt arbejde med Java LinkedListkoges ned til at skifte links. Dette kan ses meget tydeligt ved at tilføje et element til midten af ​​listen:

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

   }
}

Som du kan se, lader metoden overloaded add() dig angive et specifikt indeks for et nyt element. I dette tilfælde vil vi tilføje String str2 mellem str1 og str3 . Dette er, hvad der vil ske internt: Efter at have ændret de interne links, er str2 blevet tilføjet til listen: Nu er alle 3 elementer forbundet. Du kan flytte via det næste led fra det første element på kæden til det sidste og tilbage igen. Så vi er ret komfortable med indsættelse, men hvad med at fjerne elementer? Princippet er nøjagtigt det samme. Vi opdaterer blot linkene i de to elementer "til venstre og højre" for det element, der fjernes:

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

Her er, hvad der sker, hvis vi sletter elementet med indeks 1 (det er midt på listen): Efter opdatering af linkene får vi det ønskede resultat: I modsætning til fjernelsesoperationen i ArrayList er der her ingen grund til at flytte array-elementer eller gøre noget af den slags. Vi opdaterer blot linkene til str1 og str3 . De peger nu på hinanden, og str2 er " faldet ud " af kæden af ​​led og er ikke længere en del af listen.

Oversigt over metoder

LinkedList har mange metoder til fælles med ArrayList . For eksempel har begge klasser metoder som add() , remove() , indexOf() , clear() , contains() (angiver om et element er på listen), set() (erstatter et eksisterende element) og størrelse() . Selvom mange af dem fungerer forskelligt internt (som vi fandt med add() og remove() ), er slutresultatet det samme. LinkedList har dog separate metoder til at arbejde med begyndelsen og slutningen af ​​listen, som ArrayList ikke har:

• addFirst() , addLast() : Disse metoder til at tilføje et element til begyndelsen/slutningen af ​​listen

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 + '\'' +
               '}';
   }
}

Output: [Bil{model='Ferrari 360 Spider'}, bil{model='Bugatti Veyron'}, bil{model='Lamborghini Diablo'}] [Bil{model='Ford Mondeo'}, bil{model=' Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] Vi ender med "Ford" øverst på listen , og "Fiat" til sidst.

• peekFirst() , peekLast() : Metoderne returnerer det første/sidste element på listen. De returnerer null , hvis listen er tom.

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

Output: bil{model='Ferrari 360 Spider'} bil{model='Lamborghini Diablo'}

• pollFirst() , pollLast() : Disse metoder returnerer det første/sidste element på listen og fjerner det fra listen. De returnerer null, hvis listen er tom

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

Output: Bil{model='Ferrari 360 Spider'} Bil{model='Lamborghini Diablo'} Hvad er der tilbage på listen? [Bil{model='Bugatti Veyron'}]

• toArray() : Denne metode returnerer et array, der indeholder listeelementerne

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

Output: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Nu ved vi, hvordan LinkedList fungerer, og hvordan dens organisation adskiller sig fra ArrayList . Hvad er fordelene ved at bruge LinkedList ? Frem for alt har vi gavn af, når vi arbejder midt på listen. Indsættelse og fjernelse i midten af ​​en LinkedList er meget enklere end i en ArrayList . Vi opdaterer simpelthen linkene til naboelementer, og det uønskede element "falder ud" af kæden af ​​led. Men i en ArrayList skal vi

• kontrollere, om der er plads nok (ved indsættelse)
• hvis ikke, så opretter vi et nyt array og kopierer dataene der (ved indsættelse)
• vi fjerner/indsætter elementet, og flytter alle de andre elementer til højre/venstre (afhængig af operationstype). Og kompleksiteten af ​​denne proces afhænger meget af listens størrelse. En ting er at kopiere/flytte 10 elementer, og noget andet er at gøre det samme med en million elementer.

Med andre ord, hvis indsættelses-/fjernelseshandlinger i midten af ​​listen er mest almindelige i dit program, bør LinkedList være hurtigere end ArrayList .

I teorien

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

Output: Tid taget af LinkedList (i millisekunder) = 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));
   }
}

Output: Tid taget af ArrayList (i millisekunder) = 181 Det var uventet! Vi udførte en operation, hvor LinkedList skulle være meget mere effektiv: at indsætte 100 elementer i midten af ​​en liste. Og vores liste er enorm: 5.000.000 elementer. ArrayList var nødt til at flytte et par millioner elementer med hver indsættelse! Hvordan vandt den? For det første er den tid, det tager for ArrayList at få adgang til elementer, fast (konstant). Når du skriver

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

så er ArrayList [2_000_000] en specifik hukommelsesadresse (listen har trods alt et internt array). Men en LinkedList har ikke et array. Den vil søge efter element nummer 2_000_000 langs kæden af ​​led. For LinkedList er dette ikke en hukommelsesadresse, men et link, der stadig skal nås: 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……… Som et resultat, under hver indsættelse (fjernelse) i midten af ​​listen , ArrayList kender allerede den nøjagtige hukommelsesadresse, der skal tilgås, men LinkedList skal stadig "komme dertil". For det andet er der strukturen af ​​ArrayListsig selv. En speciel intern funktion ( System.arrayCopy() ) udvider det interne array og kopierer og flytter alle elementerne. Det er meget hurtigt, fordi det er optimeret til netop dette arbejde. Men når du ikke behøver at "komme til" et bestemt indeks, er LinkedList vinderen. Antag, at vi indsætter i begyndelsen af ​​listen. Lad os prøve at indsætte en million elementer der:

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

}

Output: Resultatet i millisekunder: 43448 Resultatet i millisekunder: 107 Nu får vi et helt andet resultat! ArrayList brugte mere end 43 sekunder på at indsætte en million elementer foran på listen, mens LinkedList formåede at gøre det på 0,1 sekunder! LinkedList gavnede her, fordi den ikke behøvede at løbe gennem kæden af ​​links til midten af ​​listen hver gang. Den finder straks det nødvendige indeks i begyndelsen af ​​listen, så den forskellige algoritme er allerede en fordel. :) Faktisk er " ArrayList versus LinkedList " diskussionen meget udbredt, og vi vil ikke dykke dybt ned i det på det nuværende niveau. Det vigtigste du skal huske er dette:

• Ikke alle de teoretiske fordele ved en bestemt samling fungerer altid i virkeligheden (vi så dette med eksemplet, der involverer midten af ​​listen)
• Indtag ikke en ekstrem holdning, når det kommer til at vælge en samling (" ArrayList er altid hurtigere. Brug den, og du kan ikke gå galt. Ingen har brugt LinkedList i lang tid").

Selvom selv LinkedLists forfatter, Joshua Bloch, siger, at dette er tilfældet. :) Alligevel er dette perspektiv langt fra 100% korrekt, og det har vi overbevist os selv om. I vores tidligere eksempel var LinkedList 400 (!) gange hurtigere. En anden ting er, at der virkelig er få situationer, hvor LinkedList er det bedste valg. Men de findes, og på det rigtige tidspunkt LinkedListkan belønne dig flot. Glem ikke, hvad vi sagde i begyndelsen af ​​lektionen: De mest effektive datastrukturer er forskellige til forskellige opgaver. Det er umuligt at være 100 % sikker på, hvilken datastruktur der vil være bedst, før du kender alle betingelserne for din opgave. Du vil vide mere om disse samlinger senere, hvilket vil gøre valget lettere. Men den enkleste og mest effektive mulighed er altid den samme: prøv begge dele på de faktiske data, der bruges i dit program. Så vil du selv kunne se, hvordan begge typer lister klarer sig, og du vil bestemt ikke gå galt. :) For at styrke det, du har lært, foreslår vi, at du ser en videolektion fra vores Java-kursus