Połączona lista w Javie

Cześć! Wszystkie ostatnie wykłady poświęcone były badaniu listy ArrayList . Taka struktura danych jest bardzo wygodna i pozwala rozwiązać wiele problemów. Jednak Java ma wiele innych struktur danych. Dlaczego? Przede wszystkim dlatego, że zakres istniejących zadań jest bardzo szeroki, a dla różnych zadań najskuteczniejsze są różne struktury danych . Dziś poznamy nową strukturę - podwójnie połączoną listę LinkedList . Zastanówmy się, jak to działa, dlaczego nazywa się to podwójnie połączonym i czym różni się od ArrayList . W LinkedList elementy są w rzeczywistości łączami w łańcuchu. Każdy element oprócz przechowywanych w nim danych posiada odnośnik do poprzedniego i kolejnego elementu . Linki te umożliwiają przechodzenie z jednego elementu do drugiego. Tworzy się go w ten sposób:

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Wniosek:

[Hello World! My name is Earl, I love Java, I live in Moscow]

Tak będzie wyglądać struktura naszej listy: Zobaczmy jak zostanie dodany nowy element. Odbywa się to za pomocą add().

earlBio.add(str2);

W chwili pisania tego wiersza kodu nasza lista składa się z jednego elementu – ciągu znaków str1. Zobaczmy, co stanie się dalej na obrazku: W rezultacie połączymy str2się str1poprzez zapisane w nich linki nextoraz previous: Teraz powinieneś zrozumieć główną ideę podwójnie połączonej listy. Elementy LinkedListstanowią jedną listę właśnie dzięki temu łańcuchowi linków. Wewnątrz nie ma tablicy LinkedList, takiej jak in ArrayListani niczego podobnego. Cała praca z ArrayList (w zasadzie) sprowadza się do pracy z wewnętrzną tablicą. Cała praca LinkedListsprowadza się do zmiany linków. Widać to bardzo wyraźnie po dodaniu elementu na środku listy:

public class Main {

   public static void main(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 Moscow");

       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ć linię str2pomiędzy str1i str3. Oto, co stanie się wewnątrz: W wyniku zmiany linków wewnętrznych element str2zostanie pomyślnie dodany do listy: Teraz wszystkie 3 elementy są połączone. Od pierwszego elementu łańcucha nextmożesz przejść do ostatniego i z powrotem. Już mniej więcej opracowaliśmy sposób wstawiania, ale co z usuwaniem elementów? Zasada działania jest taka sama. Po prostu na nowo definiujemy połączenia dwóch elementów „po bokach” usuwanego:

public class Main {

   public static void main(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 Moscow");

       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 (znajduje się na środku listy): Po ponownym zdefiniowaniu linków otrzymamy pożądany efekt: W przeciwieństwie do usuwania, ArrayListnie ma tu żadnych przesunięć elementów tablicy i tym podobnych. Po prostu na nowo definiujemy odniesienia do elementów str1i str3. Teraz wskazują na siebie, a obiekt str2„wypadł” z tego łańcucha powiązań i nie znajduje się już na liście.

Przegląd metod

Ma LinkedListwiele podobieństw z ArrayListmetodami. Przykładowo metody takie jak add(), remove(), indexOf(), clear(), contains()(jest elementem zawartym w liście), set()(wstawienie elementu z zamianą) size()występują w obu klasach. Chociaż (jak przekonaliśmy się na przykładzie add()i remove()) wiele z nich działa wewnętrznie inaczej, ale ostatecznie robią to samo. Ma jednak LinkedListosobne metody pracy z początkiem i końcem listy, których nie ma w ArrayList:

• addFirst(), addLast(): 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 + '\'' +
               '}';
   }
}

Wniosek:

[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'}]

W rezultacie Ford znalazł się na szczycie listy, a Fiat na końcu.

• peekFirst(), peekLast(): zwraca pierwszy/ostatni element listy. Wróć, nulljeś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());
}

Wniosek:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): zwraca pierwszy/ostatni element listy i usuwa go z listy . Wróć, nulljeś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(„Co zostało na liście?”);
   System.out.println(cars);
}

Wniosek:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
Co осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): zwraca tablicę elementów 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));
}

Wniosek:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

Teraz wiemy, jak to działa LinkedListi czym różni się od ArrayList. Jakie są korzyści ze stosowania LinkedList? Przede wszystkim w pracy ze środkiem listy . Wstawianie i usuwanie w środku LinkedListjest znacznie prostsze niż w ArrayList. Po prostu na nowo definiujemy połączenia sąsiadujących ze sobą elementów, a z łańcucha ogniw „wypada” niepotrzebny element. Będąc u ArrayListnas:

• sprawdź, czy jest wystarczająco dużo miejsca (podczas wstawiania)
• jeśli to nie wystarczy utwórz nową tablicę i skopiuj tam dane (przy wklejaniu)
• usuń/wstaw element i przesuń wszystkie pozostałe elementy w prawo/lewo (w zależności od rodzaju operacji). Co więcej, złożoność tego procesu w dużym stopniu zależy od wielkości listy. Kopiowanie/przenoszenie 10 elementów to jedno, ale zrobienie tego samego z milionem elementów to zupełnie inna sprawa.

Oznacza to, że jeśli w Twoim programie operacje wstawiania/usuwania występują częściej w środku listy, LinkedListpowinny być szybsze 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(„Czas uruchomienia dla LinkedList (w milisekundach) =” + (System.currentTimeMillis()-start));
   }
}

Wniosek:

Время работы для LinkedList (в мLubсекундах) = 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(„Czas uruchomienia dla ArrayList (w milisekundach) =” + (System.currentTimeMillis()-start));
   }
}

Wniosek:

Время работы для ArrayList (в миллисекундах) = 181

Nagle! Wydawać by się mogło, że wykonywaliśmy operację, która LinkedListpowinna być znacznie wydajniejsza – wstawienie 100 elementów na środek listy. A nasza lista jest ogromna — 5 000 000 elementów: ArrayListza każdym razem, gdy je wstawialiśmy, musieliśmy przesuwać kilka milionów elementów! Jaki jest powód jego zwycięstwa? Po pierwsze, dostęp do elementu jest uzyskiwany w ArrayListustalonym czasie. Kiedy wskażesz:

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

to w przypadku ArrayList[2_000_000] jest to konkretny adres w pamięci, ponieważ zawiera wewnątrz tablicę. Podczas gdy LinkedListtablica nie. Będzie szukać elementu o numerze 2_000_000 wzdłuż łańcucha ogniw. Dla niego nie jest to adres w pamięci, ale link, do którego wciąż trzeba dotrzeć:

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 przy każdym wstawieniu (usunięciu) na środku listy ArrayListzna już dokładny adres w pamięci, do którego ma uzyskać dostęp, ale LinkedListwciąż musi się „odnajdywać” we właściwym miejscu. Po drugie , materia tkwi w strukturze ArrayList„a samego”. Rozbudowa wewnętrznej tablicy, kopiowanie wszystkich elementów i przesuwanie elementów odbywa się za pomocą specjalnej funkcji wewnętrznej - System.arrayCopy(). Działa bardzo szybko, ponieważ jest specjalnie zoptymalizowany do tego zadania. Ale w sytuacjach, w których nie ma potrzeby „tupać” do pożądanego indeksu, LinkedListnaprawdę pokazuje się lepiej. Na przykład, jeśli wstawienie następuje na 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) {
       //wpisz tutaj swój kod
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); //oblicz różnicę
       System.out.println("Wynik w milisekundach: " + msDelay);
       return msDelay;

   }

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

}

Wniosek:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

Zupełnie inny wynik! Wstawienie miliona elementów na początek listy zajęło ponad 43 sekundy ArrayList, podczas gdy LinkedListtrwało to 0,1 sekundy! Właśnie o to, że w tej sytuacji LinkedListnie musieliśmy za każdym razem „biegać” przez łańcuch linków do środka listy. Od razu znalazł wymagany indeks na początku listy i tam różnica w zasadach działania była już po jego stronie :) Tak naprawdę dyskusja „ ArrayListkontra LinkedList” jest bardzo powszechna i nie będziemy się w nią zagłębiać na obecnym etapie poziom. Najważniejszą rzeczą, o której musisz pamiętać:

• Nie wszystkie zalety danej kolekcji „na papierze” sprawdzą się w rzeczywistości (sprawdzaliśmy to na przykładzie ze środka zestawienia)
• Nie należy popadać w skrajności przy wyborze kolekcji („ ArrayListzawsze jest szybciej, używaj, a się nie pomylisz. LinkedListNikt tego dawno nie używał”).

Chociaż nawet twórca LinkedListJoshua Bloch tak twierdzi :) Jednak ten punkt widzenia nie jest w 100% poprawny i jesteśmy o tym przekonani. W naszym poprzednim przykładzie LinkedListdziałało to 400 (!) razy szybciej. LinkedListInna sprawa, że ​​sytuacji, w których byłby to najlepszy wybór, jest naprawdę niewiele . Ale istnieją i we właściwym czasie LinkedListmogą ci poważnie pomóc. Nie zapomnij o tym, o czym mówiliśmy na początku wykładu: różne struktury danych są najskuteczniejsze w przypadku różnych zadań. Nie można ze 100% pewnością stwierdzić, która struktura danych będzie lepsza, dopóki nie zostaną poznane wszystkie warunki problemu. Później dowiesz się więcej o tych kolekcjach i łatwiej będzie dokonać wyboru. Ale najprostsza i najskuteczniejsza opcja jest zawsze taka sama: przetestuj obie na rzeczywistych danych ze swojego programu. Wtedy zobaczysz na własne oczy wyniki obu list i na pewno się nie pomylisz :)