Java länkad lista

Hej! Alla de senaste lektionerna har ägnats åt ArrayList . Denna datastruktur är mycket bekväm och användbar. Den kan hantera många uppgifter. Men Java har många andra datastrukturer. Varför? Framför allt eftersom utbudet av uppgifter är enormt, och de mest effektiva datastrukturerna är olika för olika uppgifter. Idag möter vi en ny struktur: Java LinkedList , en dubbellänkad lista.

Låt oss se hur det är organiserat, varför det kallas dubbellänkat, hur det skiljer sig från ArrayList . Elementen i en Java LinkedList är faktiskt länkar i en enda kedja. Förutom data lagrar varje element referenser till föregående och nästa element. Dessa referenser låter dig flytta från ett element till ett annat. Så här skapar 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);

   }
}

Utdata: [Hej världen! Jag heter Earl, jag älskar Java, jag bor i Kanada] Så här ser vår lista ut: Länkad lista - 2

Låt oss se hur man lägger till ett nytt element. Detta görs med metoden add() .

earlBio.add(str2);

Vid punkten i koden består vår lista av ett element: String str1 . Låt oss se vad som händer härnäst i bilden: Länkad lista - 3

Som ett resultat blir str2 och str1 länkade via nästa och föregående länkar lagrade i denna noder i listan: Länkad lista - 4

Nu bör du förstå huvudidén med en dubbellänkad lista. Denna länkkedja är precis vad som gör LinkedList- element till en enda lista. Till skillnad från ArrayList har LinkedList inte en array eller något array-liknande inuti . Allt (nåja, de flesta) arbete med ArrayList handlar om att arbeta med den interna arrayen. Allt arbete med Java LinkedListhandlar om att byta länkar. Detta kan ses mycket tydligt genom att lägga till ett element i mitten av listan:

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 låter metoden overloaded add() dig ange ett specifikt index för ett nytt objekt. I det här fallet vill vi lägga till String str2 mellan str1 och str3 . Detta är vad som kommer att hända internt: Länkad lista - 5

Efter att ha ändrat de interna länkarna har str2 framgångsrikt lagts till i listan: Länkad lista - 6

Nu är alla 3 elementen anslutna. Du kan flytta via nästa länk från det första elementet på kedjan till det sista och tillbaka igen. Så vi är ganska bekväma med att infoga, men hur är det med att ta bort element? Principen är exakt densamma. Vi uppdaterar bara länkarna i de två elementen "till vänster och höger" om elementet som tas bort:

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

Så här händer om vi tar bort objektet med index 1 (det är i mitten av listan): Länkad lista - 7

Efter att ha uppdaterat länkarna får vi det önskade resultatet: Länkad lista - 8

Till skillnad från borttagningsoperationen i ArrayList finns det inget behov av att flytta arrayelement eller göra något sådant. Vi uppdaterar bara länkarna för str1 och str3 . De pekar nu på varandra och str2 har " fallit ut " ur länkkedjan och är inte längre en del av listan.

Översikt över metoder

LinkedList har många metoder gemensamma med ArrayList . Till exempel har båda klasserna metoder som add() , remove() , indexOf() , clear() , contains() (anger om ett objekt finns i listan), set() (ersätter ett befintligt element) och storlek() . Även om många av dem fungerar annorlunda internt (som vi hittade med add() och remove() ), är slutresultatet detsamma. Men LinkedList har separata metoder för att arbeta med början och slutet av listan, vilket ArrayList inte har:

addFirst() , addLast() : Dessa metoder för att lägga till ett element i början/slutet av listan

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

Utdata: [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 hamnar på "Ford" överst på listan , och "Fiat" på slutet.

peekFirst() , peekLast() : Metoderna returnerar det första/sista elementet i listan. De returnerar null om listan är 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());
}

Utgång: bil{model='Ferrari 360 Spider'} bil{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Dessa metoder returnerar det första/sista elementet i listan och tar bort det från listan. De returnerar null om listan är 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);
}

Utgång: Bil{model='Ferrari 360 Spider'} Bil{model='Lamborghini Diablo'} Vad finns kvar på listan? [Bil{model='Bugatti Veyron'}]

toArray() : Denna metod returnerar en array som innehåller listobjekten

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

Utdata: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Nu vet vi hur LinkedList fungerar och hur dess organisation skiljer sig från ArrayList . Vilka är fördelarna med att använda LinkedList ? Framför allt tjänar vi på när vi jobbar mitt på listan. Insättning och borttagning i mitten av en LinkedList är mycket enklare än i en ArrayList . Vi uppdaterar helt enkelt länkarna till angränsande element, och det oönskade elementet "faller ut" ur länkkedjan. Men i en ArrayList måste vi

kontrollera om det finns tillräckligt med utrymme (vid insättning)
om inte, skapar vi en ny array och kopierar data dit (när vi infogar)
vi tar bort/sätter in elementet och flyttar alla andra element till höger/vänster (beroende på typ av operation). Och komplexiteten i denna process beror mycket på storleken på listan. Det är en sak att kopiera/flytta 10 element, och en helt annan att göra samma sak med en miljon element.

Med andra ord, om insättning/borttagning i mitten av listan är vanligast i ditt program, bör LinkedList vara snabbare än ArrayList .

I teorin

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 som LinkedList tar (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 som tas av ArrayList (i millisekunder) = 181 Det var oväntat! Vi utförde en operation där LinkedList borde vara mycket effektivare: att infoga 100 objekt i mitten av en lista. Och vår lista är enorm: 5 000 000 element. ArrayList var tvungen att flytta ett par miljoner objekt med varje infogning! Hur vann den? Först är tiden som krävs för att ArrayList ska komma åt element fast (konstant). När du skriver

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

då är ArrayList [2_000_000] en specifik minnesadress (listan har trots allt en intern array). Men en LinkedList har ingen array. Det kommer att söka efter element nummer 2_000_000 längs kedjan av länkar. För LinkedList är detta inte en minnesadress, utan en länk som fortfarande måste 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 ett resultat, under varje insättning (borttagning) i mitten av listan , ArrayList känner redan till den exakta minnesadressen att komma åt, men LinkedList måste fortfarande "komma dit". För det andra finns det strukturen för ArrayListsig. En speciell intern funktion ( System.arrayCopy() ) expanderar den interna arrayen och kopierar och skiftar alla element. Det är väldigt snabbt, eftersom det är optimerat för detta specifika arbete. Men när du inte behöver "komma till" ett visst index, är LinkedList vinnaren. Anta att vi infogar i början av listan. Låt oss försöka infoga en miljon element där:

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 Nu får vi ett helt annat resultat! ArrayList ägnade mer än 43 sekunder åt att infoga en miljon objekt längst fram på listan, medan LinkedList lyckades göra det på 0,1 sekunder! LinkedList gynnades här, eftersom den inte behövde gå igenom länkkedjan till mitten av listan varje gång. Den hittar omedelbart det nödvändiga indexet i början av listan, så den olika algoritmen är redan en fördel. :) Faktum är att diskussionen " ArrayList versus LinkedList " är väldigt utbredd, och vi kommer inte att fördjupa oss i den på nuvarande nivå. Det viktigaste du behöver komma ihåg är detta:

Inte alla teoretiska fördelar med en viss samling fungerar alltid i verkligheten (vi såg detta med exemplet som involverade mitten av listan)
Inta inte en extrem position när det gäller att välja en samling (" ArrayList är alltid snabbare. Använd den och du kan inte gå fel. Ingen har använt LinkedList på länge").

Även om LinkedLists författare, Joshua Bloch, säger att så är fallet. :) Ändå är detta perspektiv långt ifrån 100% korrekt, och vi har övertygat oss själva om detta. I vårt tidigare exempel var LinkedList 400 (!) gånger snabbare. En annan sak är att det verkligen finns få situationer där LinkedList är det bästa valet. Men de finns, och i rätt ögonblick LinkedListkan belöna dig rejält. Glöm inte vad vi sa i början av lektionen: de mest effektiva datastrukturerna är olika för olika uppgifter. Det är omöjligt att vara 100 % säker på vilken datastruktur som är bäst förrän du känner till alla förutsättningar för din uppgift. Du får veta mer om dessa samlingar senare, vilket kommer att göra valet lättare. Men det enklaste och mest effektiva alternativet är alltid detsamma: prova båda på de faktiska data som används i ditt program. Då kommer du att kunna se själv hur båda typerna av listor presterar och du kommer definitivt inte att gå fel. :) För att förstärka det du lärde dig föreslår vi att du tittar på en videolektion från vår Java-kurs

Mer läsning:
LinkedList Java-datastruktur