Java Linked List

Hei! Alle de siste leksjonene har blitt viet til ArrayList . Denne datastrukturen er veldig praktisk og nyttig. Den kan håndtere mange oppgaver. Men Java har mange andre datastrukturer. Hvorfor? Fremfor alt fordi utvalget av oppgaver er enormt, og de mest effektive datastrukturene er forskjellige for ulike oppgaver. I dag møter vi en ny struktur: Java LinkedList , en dobbeltlenket liste.

La oss se hvordan det er organisert, hvorfor det kalles dobbeltlenket, hvordan det skiller seg fra ArrayList . Elementene i en Java LinkedList er faktisk lenker i en enkelt kjede. I tillegg til data, lagrer hvert element referanser til forrige og neste elementer. Disse referansene lar deg flytte fra ett element til et annet. Slik lager 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);

   }
}

Utgang: [Hei verden! Mitt navn er Earl, jeg elsker Java, jeg bor i Canada] Slik ser listen vår ut: LinkedList - 2

La oss se hvordan du legger til et nytt element. Dette gjøres ved å bruke add() metoden.

earlBio.add(str2);

På punktet i koden består listen vår av ett element: String str1 . La oss se hva som skjer videre i bildet: LinkedList - 3

Som et resultat blir str2 og str1 koblet sammen via de neste og forrige lenkene som er lagret i denne nodene på listen: LinkedList - 4

Nå bør du forstå hovedideen til en dobbeltlenket liste. Denne lenkekjeden er nettopp det som gjør LinkedList- elementer til en enkelt liste. I motsetning til ArrayList har ikke LinkedList en array eller noe array-lignende inni. Alt (vel, de fleste) arbeid med ArrayList koker ned til å jobbe med den interne matrisen. Alt arbeid med Java LinkedListkoker ned til å endre lenker. Dette kan sees veldig tydelig ved å legge til et element i midten av 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, lar den overlastede add()- metoden deg spesifisere en spesifikk indeks for et nytt element. I dette tilfellet ønsker vi å legge til String str2 mellom str1 og str3 . Dette er hva som vil skje internt: LinkedList - 5

Etter å ha endret de interne lenkene, har str2 blitt lagt til listen: LinkedList - 6

Nå er alle 3 elementene koblet sammen. Du kan flytte via neste ledd fra det første elementet på kjeden til det siste og tilbake igjen. Så vi er ganske komfortable med innsetting, men hva med å fjerne elementer? Prinsippet er nøyaktig det samme. Vi oppdaterer bare koblingene i de to elementene "til venstre og høyre" for elementet som 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 hva som skjer hvis vi sletter elementet med indeks 1 (det er midt på listen): LinkedList - 7

Etter å ha oppdatert lenkene får vi ønsket resultat: LinkedList - 8

I motsetning til fjerningsoperasjonen i ArrayList , er det ikke nødvendig å skifte array-elementer eller gjøre noe av det slaget. Vi oppdaterer bare lenkene for str1 og str3 . De peker nå på hverandre, og str2 har " falt ut " av lenkekjeden og er ikke lenger en del av listen.

Oversikt over metoder

LinkedList har mange metoder til felles med ArrayList . For eksempel har begge klassene metoder som add() , remove() , indexOf() , clear() , contains() (indikerer om et element er på listen), set() (erstatter et eksisterende element) og størrelse() . Selv om mange av dem fungerer annerledes internt (som vi fant med add() og remove() ), er sluttresultatet det samme. LinkedList har imidlertid separate metoder for å jobbe med begynnelsen og slutten av listen, som ArrayList ikke har:

addFirst() , addLast() : Disse metodene for å legge til et element i begynnelsen/slutten av 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 + '\'' +
               '}';
   }
}

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

peekFirst() , peekLast() : Metodene returnerer det første/siste elementet i 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());
}

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

pollFirst() , pollLast() : Disse metodene returnerer det første/siste elementet i 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);
}

Utgang: Bil{model='Ferrari 360 Spider'} Bil{model='Lamborghini Diablo'} Hva er igjen på listen? [Bil{model='Bugatti Veyron'}]

toArray() : Denne metoden returnerer en matrise som inneholder listeelementene

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

Utgang: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Nå vet vi hvordan LinkedList fungerer og hvordan organiseringen skiller seg fra ArrayList . Hva er fordelene med å bruke LinkedList ? Fremfor alt har vi nytte av å jobbe midt på listen. Innsetting og fjerning midt i en LinkedList er mye enklere enn i en ArrayList . Vi oppdaterer ganske enkelt lenkene til naboelementer, og det uønskede elementet "faller ut" av lenkekjeden. Men i en ArrayList må vi

sjekk om det er nok plass (ved innsetting)
hvis ikke, oppretter vi en ny matrise og kopierer dataene der (når vi setter inn)
vi fjerner/setter inn elementet, og flytter alle de andre elementene til høyre/venstre (avhengig av type operasjon). Og kompleksiteten til denne prosessen avhenger sterkt av størrelsen på listen. En ting er å kopiere/flytte 10 elementer, og noe helt annet er å gjøre det samme med en million elementer.

Med andre ord, hvis innsettings-/fjerningsoperasjoner i midten av listen er mest vanlig i programmet ditt, bør LinkedList være raskere enn 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));
   }
}

Utdata: Tid tatt av 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));
   }
}

Utdata: Tid tatt av ArrayList (i millisekunder) = 181 Det var uventet! Vi utførte en operasjon der LinkedList skulle være mye mer effektivt: å sette inn 100 elementer i midten av en liste. Og listen vår er enorm: 5 000 000 elementer. ArrayList måtte flytte et par millioner elementer for hver innsetting! Hvordan vant den? For det første er tiden som kreves for at ArrayList skal få tilgang 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 spesifikk minneadresse (listen har tross alt en intern matrise). Men en LinkedList har ikke en matrise. Den vil søke etter element nummer 2_000_000 langs lenkekjeden. For LinkedList er dette ikke en minneadresse, men en lenke som fortsatt må nås: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. neste.neste.neste.neste.neste.neste.neste.neste.neste.neste.neste.neste.neste.neste.neste.neste……… Som et resultat, under hver innsetting (fjerning) i midten av listen , ArrayList vet allerede den nøyaktige minneadressen for tilgang, men LinkedList må fortsatt "komme dit". For det andre er det strukturen til ArrayListseg selv. En spesiell intern funksjon ( System.arrayCopy() ) utvider den interne matrisen, og kopierer og forskyver alle elementene. Det er veldig raskt, fordi det er optimalisert for dette spesifikke arbeidet. Men når du ikke trenger å "komme til" en bestemt indeks, er LinkedList vinneren. Anta at vi setter inn helt i begynnelsen av listen. La oss prøve å sette inn 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());
       }
   }

}

Utdata: Resultatet i millisekunder: 43448 Resultatet i millisekunder: 107 Nå får vi et helt annet resultat! ArrayList brukte mer enn 43 sekunder på å sette inn en million elementer foran på listen, mens LinkedList klarte å gjøre det på 0,1 sekunder! LinkedList hadde fordel her, fordi den ikke trengte å gå gjennom lenkekjeden til midten av listen hver gang. Den finner umiddelbart den nødvendige indeksen i begynnelsen av listen, så den forskjellige algoritmen er allerede en fordel. :) Faktisk er diskusjonen " ArrayList versus LinkedList " veldig utbredt, og vi vil ikke dykke dypt ned i den på det nåværende nivået. Det viktigste du må huske er dette:

Ikke alle de teoretiske fordelene med en bestemt samling fungerer alltid i virkeligheten (vi så dette med eksemplet som involverer midten av listen)
Ikke innta en ekstrem posisjon når det gjelder å velge en samling (" ArrayList er alltid raskere. Bruk den og du kan ikke gå galt. Ingen har brukt LinkedList på lenge").

Selv om til og med LinkedLists forfatter, Joshua Bloch, sier at dette er tilfelle. :) Likevel er dette perspektivet langt fra 100% riktig, og vi har overbevist oss selv om dette. I vårt forrige eksempel var LinkedList 400 (!) ganger raskere. En annen ting er at det virkelig er få situasjoner der LinkedList er det beste valget. Men de eksisterer, og i rett øyeblikk LinkedListkan belønne deg pent. Ikke glem det vi sa i begynnelsen av leksjonen: De mest effektive datastrukturene er forskjellige for forskjellige oppgaver. Det er umulig å være 100 % sikker på hvilken datastruktur som vil være best før du kjenner alle betingelsene for oppgaven din. Du får vite mer om disse samlingene senere, noe som vil gjøre valget enklere. Men det enkleste og mest effektive alternativet er alltid det samme: prøv begge på de faktiske dataene som brukes i programmet ditt. Da vil du selv kunne se hvordan begge typer lister presterer og du vil definitivt ikke gå galt. :) For å forsterke det du lærte, foreslår vi at du ser en videoleksjon fra Java-kurset vårt

Mer lesing:
LinkedList Java-datastruktur