Wprowadzenie do kolekcji LinkedList

1. HistoriaLinkedList

Java ma inną klasę kolekcji, którą Java odziedziczyła z języka C++. Jest to klasa LinkedList, która tłumaczy się jako „lista połączona”.

Zewnętrznie LinkedListjest to ta sama lista co ArrayList. Klasa LinkedListma wszystkie te same metody co klasa ArrayList. I w zasadzie zawsze możesz użyć LinkedListzamiast ArrayList, i wszystko będzie działać.

Dlaczego więc potrzebujemy kolejnej klasy listy?

Chodzi o elementy wewnętrzne klasy LinkedList. Używa listy podwójnie połączonej zamiast tablicy . Co to jest, powiemy trochę później.

Ale ze względu na inną strukturę wewnętrzną klasa LinkedListma najszybszą operację wstawiania elementów na środek listy.

W internecie często można znaleźć takie porównanie klas ArrayListoraz LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Wszystko wydaje się jasne: jeśli musisz często wstawiać elementy do listy, użyj LinkedList, jeśli rzadko, to ArrayList. Jednak rzeczywistość jest trochę inna.

2. Nikt nie używaLinkedList

Nikt nie używa LinkedList.

Ostatnio nawet sam autor kodu klasy LinkedListzamieścił na Twitterze post: „Chłopaki, czy ktoś w ogóle używa LinkedList? Nie użyłem go ani razu od 20 lat!”

Więc o co chodzi?

Najpierw klasa ArrayListzaczęła bardzo szybko wstawiać elementy na środek listy. Dodając element na środku listy, musisz przesunąć wszystkie elementy po żądanym o 1 w kierunku końca listy. Kiedyś to wymagało czasu.

Ale teraz wszystko się zmieniło. Wszystkie elementy tablicy znajdują się obok siebie w tym samym bloku pamięci, więc operacja przesunięcia elementów tablicy jest wykonywana za pomocą bardzo szybkiego polecenia niskiego poziomu .System.arraycopy()

Ponadto teraz procesory mają dużą pamięć podręczną i zwykle cała tablica mieści się w takiej pamięci podręcznej, więc elementy tablicy są przesuwane nawet nie w pamięci, ale w pamięci podręcznej procesora. Milion elementów można łatwo przesunąć w ciągu jednej milisekundy.

Po drugie, klasa LinkedListszybko wstawia elementy, jeśli wstawiasz je za pomocą iteratora. Jeśli używasz iteratora do iteracji po liście LinkedListi ciągłego dodawania nowych elementów (lub usuwania istniejących), jest to naprawdę superszybka operacja.

Jeśli po prostu dodasz elementy wewnątrz klasy w pętli LinkedList, powolna operacja „pobierz element” zostanie dodana do każdej szybkiej operacji wstawienia.

Rzeczywistość jest znacznie bliższa tej sytuacji:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Dlaczego operacja pobierania elementu jest LinkedListtak powolna?

Odpowiedź na to pytanie poznasz, jeśli trochę zapoznasz się z urządzeniem.LinkedList

3. UrządzenieLinkedList

LinkedListma alternatywną strukturę wewnętrzną w porównaniu do ArrayList. Nie ma tablicy do przechowywania elementów w środku. Zamiast tego wykorzystuje strukturę danych zwaną podwójnie połączoną listą.

Każdy element listy podwójnie połączonej przechowuje łącza do poprzedniego i następnego elementu. Przypomina to nieco kolejkę, w której każdy pamięta tego, kto stoi przed nim, i tego, który stoi za nim.

Oto jak taka lista wygląda w pamięci:

Po bokach (szare tło) znajdują się zmienne firsti last, które przechowują referencje do obiektów typu Node.

W środku widać łańcuch obiektów (obiektów, nie zmiennych) typu Node. Każdy z nich składa się z trzech pól:

• prev- przechowuje link do poprzedniego obiektu typu Node(żółte tło).
• value- przechowuje wartość - element listy (zielone tło).
• next- przechowuje link do następnego obiektu typu Node(niebieskie tło)

Drugi obiekt (adres == F24) jest następny ( next) dla pierwszego i poprzedni ( prev) dla trzeciego. Żółte pole trzeciego obiektu zawiera łącze F24, a niebieskie pole pierwszego obiektu zawiera łącze F24.

Strzałki z pierwszego i trzeciego obiektu wskazują na ten sam drugi obiekt. Dlatego bardziej poprawne byłoby narysowanie takich strzałek.

4. Wstawianie elementu do połączonej listy

Aby dodać osobę do takiej kolejki wystarczy zgoda dwóch sąsiadujących ze sobą osób. Pierwsza z nich pamięta przybysza jako nowego: „ta osoba jest za mną”, a druga pamięta przybysza jako nowego „ta osoba jest przede mną”.

Wszystko, co musisz zrobić, to zmienić odniesienia dwóch sąsiednich obiektów:

Dodaliśmy nowy element do naszej listy i zmieniliśmy referencje drugiego i trzeciego obiektu. Teraz początkujący, następny na drugim i poprzedni na trzecim. Cóż, sam obiekt początkujący musi mieć poprawne linki: poprzedni obiekt jest drugi, następny obiekt jest trzeci.

Usunięcie jest jeszcze łatwiejsze. Jeśli chcemy usunąć, powiedzmy, 100. obiekt z listy, wystarczy zmienić następny z 99. obiektu, aby wskazywał na 101. obiekt, i zmienić następny ze 101. obiektu, aby wskazywał na 99. I to wszystko prev.

Ale zdobycie setnego obiektu nie jest takie proste.

5. Pobierz element listy

Aby uzyskać setny element połączonej listy, musisz:

Pobierz pierwszy obiekt: odwołuje się do niego zmienna firstobiektu LinkedList. Pierwszy obiekt ma link (pole next) do drugiego obiektu. Z jego pomocą otrzymujemy drugi obiekt. Drugi obiekt ma link do trzeciego i tak dalej.

Jeśli chcemy uzyskać odniesienie do 100. obiektu, musimy kolejno przejść przez wszystkie obiekty od 1. do 100. A jeśli potrzebujemy milionowego elementu listy, musimy powtórzyć po kolei ponad milion obiektów!

Ale jeśli te obiekty zostały dodane do listy w różnym czasie, znajdują się w różnych częściach pamięci i jest mało prawdopodobne, aby dostały się do pamięci podręcznej procesora w tym samym czasie. A to oznacza, że ​​sekwencyjne wyliczanie elementów połączonej listy jest nie tylko powolne, ale bardzo powolne.

Tak to idzie.

Dlaczego więc uczymy tutaj, jak działa ten wolny LinkedList?

Rzecz w tym, że na rozmowie kwalifikacyjnej na pewno zostaniesz zapytany, czym LinkedListróżni się od ArrayList. Koniecznie.