Java LinkedList

Cześć! Wszystkie ostatnie lekcje były poświęcone ArrayList . Ta struktura danych jest bardzo wygodna i użyteczna. Poradzi sobie z wieloma zadaniami. Ale Java ma wiele innych struktur danych. Dlaczego? Przede wszystkim dlatego, że zakres zadań jest ogromny, a najbardziej wydajne struktury danych są różne dla różnych zadań. Dzisiaj poznamy nową strukturę: Java LinkedList , podwójnie powiązaną listę.

Zobaczmy, jak to jest zorganizowane, dlaczego nazywa się podwójnie połączone, czym różni się od ArrayList . Elementy w Java LinkedList są w rzeczywistości linkami w jednym łańcuchu. Oprócz danych każdy element przechowuje odniesienia do poprzedniego i następnego elementu. Odniesienia te umożliwiają przechodzenie od jednego elementu do drugiego. W ten sposób tworzysz jeden:

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

   }
}

Dane wyjściowe: [Witaj, świecie! Nazywam się Earl, kocham Javę, mieszkam w Kanadzie] Oto jak wygląda nasza lista: Linkowana lista - 2

Zobaczmy, jak dodać nowy element. Odbywa się to za pomocą metody add() .

earlBio.add(str2);

W punkcie kodu nasza lista składa się z jednego elementu: String str1 . Zobaczmy, co dzieje się dalej na obrazku: Linkowana lista - 3

W rezultacie str2 i str1 zostają połączone poprzez następne i poprzednie łącza przechowywane w tych węzłach listy: Linkowana lista - 4

Teraz powinieneś zrozumieć główną ideę listy podwójnie połączonej. Właśnie ten łańcuch linków sprawia, że elementy LinkedList są pojedynczą listą. W przeciwieństwie do ArrayList , LinkedList nie ma tablicy ani niczego podobnego do tablicy w środku. Każda (no, większość) praca z ArrayList sprowadza się do pracy z wewnętrzną tablicą. Dowolna praca z Java LinkedListsprowadza się do zmiany linków. Można to bardzo wyraźnie zobaczyć, dodając element na środku listy:

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

   }
}

Jak widać, przeciążona metoda add() pozwala określić konkretny indeks dla nowego elementu. W tym przypadku chcemy dodać String str2 między str1 i str3 . Oto, co stanie się wewnętrznie: Linkowana lista - 5

Po zmianie linków wewnętrznych str2 został pomyślnie dodany do listy: Linkowana lista - 6

Teraz wszystkie 3 elementy są połączone. Możesz przejść przez następne ogniwo od pierwszego elementu łańcucha do ostatniego iz powrotem. Więc jesteśmy dość zadowoleni z wstawiania, ale co z usuwaniem elementów? Zasada jest dokładnie taka sama. Po prostu aktualizujemy linki w dwóch elementach „po lewej i prawej stronie” usuwanego elementu:

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

Oto co się stanie, jeśli usuniemy element o indeksie 1 (znajdujący się na środku listy): Linkowana lista - 7

Po zaktualizowaniu linków otrzymujemy pożądany rezultat: Linkowana lista - 8

W przeciwieństwie do operacji usuwania w ArrayList , tutaj nie ma potrzeby przesuwania elementów tablicy ani wykonywania cokolwiek w tym rodzaju. Po prostu aktualizujemy linki dla str1 i str3 . Teraz wskazują na siebie nawzajem, a str2 „ wypadł ” z łańcucha linków i nie jest już częścią listy.

Przegląd metod

LinkedList ma wiele metod wspólnych z ArrayList . Na przykład obie klasy mają metody, takie jak add() , remove() , indexOf() , clear() , zawiera() (wskazuje, czy element znajduje się na liście), set() (zastępuje istniejący element) i rozmiar() . Chociaż wiele z nich działa inaczej wewnętrznie (jak odkryliśmy w przypadku add() i remove() ), efekt końcowy jest taki sam. Jednak LinkedList ma osobne metody pracy z początkiem i końcem listy, których ArrayList nie ma:

addFirst() , addLast() : Te metody dodawania elementu na początek/koniec listy

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

Wyjście: [Samochód{model='Ferrari 360 Spider'}, Samochód{model='Bugatti Veyron'}, Samochód{model='Lamborghini Diablo'}] [Samochód{model='Ford Mondeo'}, Samochód{model=' Ferrari 360 Spider'}, Samochód{model='Bugatti Veyron'}, Samochód{model='Lamborghini Diablo'}, Samochód{model='Fiat Ducato'}] Kończymy z "Fordem" na szczycie listy, i "Fiat" na końcu.

peekFirst() , peekLast() : Metody zwracają pierwszy/ostatni element na liście. Zwracają wartość null , jeśli lista jest pusta.

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

Wynik: samochód{model='Ferrari 360 Spider'} samochód{model='Lamborghini Diablo'}

pollFirst() , pollLast() : Te metody zwracają pierwszy/ostatni element na liście i usuwają go z listy. Zwracają wartość null, jeśli lista jest pusta

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

Wyjście: Samochód{model='Ferrari 360 Spider'} Samochód{model='Lamborghini Diablo'} Co zostało z listy? [Samochód{model='Bugatti Veyron'}]

toArray() : Ta metoda zwraca tablicę zawierającą elementy listy

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

Dane wyjściowe: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Teraz wiemy, jak działa LinkedList i czym różni się jej organizacja od ArrayList . Jakie są korzyści z używania LinkedList ? Przede wszystkim zyskujemy pracując w środku listy. Operacje wstawiania i usuwania w środku LinkedList są znacznie prostsze niż w ArrayList . Po prostu aktualizujemy powiązania sąsiednich elementów, a niechciany element „wypada” z łańcucha powiązań. Ale w ArrayList musimy

sprawdź, czy jest wystarczająco dużo miejsca (podczas wkładania)
jeśli nie to tworzymy nową tablicę i tam kopiujemy dane (przy wstawianiu)
usuwamy/wstawiamy element, a wszystkie pozostałe elementy przesuwamy w prawo/lewo (w zależności od typu operacji). A złożoność tego procesu zależy w dużej mierze od rozmiaru listy. Kopiowanie/przenoszenie 10 elementów to jedno, a robienie tego samego z milionem elementów to zupełnie co innego.

Innymi słowy, jeśli operacje wstawiania/usuwania w środku listy są najbardziej powszechne w twoim programie, LinkedList powinien być szybszy niż ArrayList .

W teorii

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

Dane wyjściowe: Czas potrzebny na LinkedList (w milisekundach) = 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));
   }
}

Dane wyjściowe: Czas potrzebny przez ArrayList (w milisekundach) = 181 To było nieoczekiwane! Wykonaliśmy operację, w której LinkedList powinien być znacznie wydajniejszy: wstawienie 100 pozycji na środku listy. A nasza lista jest ogromna: 5 000 000 elementów. ArrayList musiał przesuwać kilka milionów elementów przy każdym wstawieniu! Jak wygrał? Po pierwsze, czas wymagany do uzyskania przez ArrayList dostępu do elementów jest stały (stały). kiedy piszesz

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

wtedy ArrayList [2_000_000] to konkretny adres pamięci (w końcu lista ma wewnętrzną tablicę). Ale LinkedList nie ma tablicy. Wyszuka element o numerze 2_000_000 wzdłuż łańcucha powiązań. W przypadku LinkedList nie jest to adres pamięci, ale łącze, które wciąż musi zostać osiągnięte: 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……… W rezultacie podczas każdego wstawiania (wyciągania) w środku listy , ArrayList zna już dokładny adres pamięci, do którego ma uzyskać dostęp, ale LinkedList nadal musi się tam „dostać”. Po drugie, istnieje struktura ArrayListsamo. Specjalna funkcja wewnętrzna ( System.arrayCopy() ) rozszerza wewnętrzną tablicę oraz kopiuje i przesuwa wszystkie elementy. Jest bardzo szybki, ponieważ jest zoptymalizowany pod kątem tej konkretnej pracy. Ale kiedy nie musisz „docierać” do określonego indeksu, LinkedList jest zwycięzcą. Załóżmy, że wstawiamy na samym początku listy. Spróbujmy wstawić tam milion elementów:

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

}

Wyjście: Wynik w milisekundach: 43448 Wynik w milisekundach: 107 Teraz otrzymujemy zupełnie inny wynik! ArrayList poświęcił ponad 43 sekundy na wstawienie miliona elementów na początku listy, podczas gdy LinkedList zrobił to w 0,1 sekundy! Skorzystał na tym LinkedList , który nie musiał za każdym razem przebiegać przez łańcuch linków do środka listy. Natychmiast znajduje potrzebny indeks na początku listy, więc inny algorytm jest już zaletą. :) W rzeczywistości dyskusja „ ArrayList kontra LinkedList ” jest bardzo powszechna i nie będziemy się w nią zagłębiać na obecnym poziomie. Najważniejszą rzeczą, o której musisz pamiętać, jest to:

Nie wszystkie teoretyczne zalety danej kolekcji zawsze działają w rzeczywistości (widzieliśmy to na przykładzie środka listy)
Nie przyjmuj skrajnej pozycji, jeśli chodzi o wybór kolekcji („ ArrayList jest zawsze szybszy. Użyj go, a nie popełnisz błędu. Nikt nie używa LinkedList od dawna”).

Chociaż nawet autor LinkedList , Joshua Bloch, mówi, że tak jest. :) Jednak ta perspektywa nie jest w 100% poprawna i przekonaliśmy się o tym. W naszym poprzednim przykładzie LinkedList był 400 (!) razy szybszy. Inną rzeczą jest to, że naprawdę niewiele jest sytuacji, w których LinkedList jest najlepszym wyborem. Ale one istnieją i we właściwym momencie LinkedListmoże sowicie wynagrodzić. Nie zapomnij o tym, co powiedzieliśmy na początku lekcji: najbardziej wydajne struktury danych są różne dla różnych zadań. Nie można być w 100% pewnym, która struktura danych będzie najlepsza, dopóki nie poznasz wszystkich warunków swojego zadania. Więcej o tych kolekcjach dowiesz się później, co ułatwi wybór. Ale najprostsza i najskuteczniejsza opcja jest zawsze taka sama: wypróbuj obie metody na rzeczywistych danych używanych w twoim programie. Wtedy będziesz mógł sam przekonać się, jak działają oba typy list i na pewno się nie pomylisz. :) Aby utrwalić to, czego się nauczyłeś, proponujemy obejrzeć lekcję wideo z naszego kursu języka Java

Więcej czytania:
Struktura danych LinkedList Java