W jednym z naszych wpisów poznaliśmy bliskiego krewnego tablic, a mianowicie klasę ArrayList. Jej budowę, sposób działania oraz metody, które pozwalają na praktyczne korzystanie z niej. Implementacja klasy ArrayList daje świetne efekty jeśli chodzi o wyszukiwanie elementów(wszystkie są obok siebie) oraz zamortyzowany koszt dodawania elementów (pojemność kolekcji jest nieco większa niż liczba elementów). Jednak problemem jest dodawanie wielu elementów oraz usuwanie ze środka listy. Wpis jest częścią artykułów o kolekcjach w Javie.

Powyższe problemy rozwiązuje inna implementacja interfejsów List oraz Iterable czyli klasa LinkedList – są to listy dwukierunkowe.

Klasa LinkedList

Obiekty, które są przechowywane w kolekcjach listy mogą znajdować się w dowolnym miejscu w pamięci – to kompilator decyduje, gdzie dokładnie zostanie ono przydzielone. W związku z tym kolekcja nie znajduje się w całości obok siebie (jest na to niezwykle mała szansa), a każdy węzeł zna położenie swojego poprzednika i następnika. Dokładniej zasadę działania list dwukierunkowych wyjaśniliśmy w jednym z poprzednich wpisów.
Każdy korzystający z kolekcji chce wiedzieć, którą należy wybrać do poszczególnych zastosowań zatem akapit będzie w dużej mierze polegał na porównaniu klas LinkedList oraz ArrayList.

Zaczniemy od dodawania elementów i usuwania. Zmiana rozmiaru tej kolekcji polega na zmianie połączeń między poszczególnymi węzłami. Nie ma potrzeby tak jak w przypadku dynamicznych tablic zmiany położenia wszystkich elementów o wyższym indeksie w kierunku korzenia co wiąże się z dużą ilością kopiowania obiektów w pamięci. Wszystkie elementy pozostają dokładnie tam, gdzie znajdowały się pierwotnie. Jedyne co ulega zmianie to referencje wskazujące poprzednie i następne ogniwa.

LinkedList jest kolekcją uporządkowaną, co oznacza, że kolejność, którą podajemy zostaje zapamiętana.

Jednak nie ma nic za darmo. W zamian za dobry czas wstawiania elementów w środku kolekcji otrzymujemy gorsze wyniki w odczycie danych niż w przypadku klasy ArrayList. Jeśli potrzebujemy operować na indeksach (jak w przypadku tablic) wybierzmy poprzednio opisywaną kolekcję ArrayList.

LinkedList – jak używać, metody, konstruktory

• LinkedList() – tworzy pustą listę
• LinkedList(Collection<? extends E> collection) – tworzy listę, a następnie dodaje podaną w argumencie kolekcję. Musi implementować interfejs Collection.

Aby utworzyć pustą listę tablicową można użyć następującego kodu.

Ze względu na implementację interfejsu List, klasa LinkedList zawiera te same metody co ArrayList. Jednakże należy uważać przy korzystaniu z nich część z nich nie jest tak naprawdę dostosowana do specyfiki tych list. Wypiszemy jednak te najważniejsze.

Metody dostarczone przez klasę LinkedList

• boolean add(E element) – Dodaje na końcu listy element.
• void add(int index, E element) – dodaje element  na pozycji index (licząc od 0). Element znajdujący się dotychczas na tej pozycji oraz wszystkie o indeksie większym zostają przesunięte w prawo.
• E remove(int index) – usuwa z listy element o wskazanym indeksie. Pozostałe elementy za nim przesuwa w lewo.
• void clear() – usuwa wszystkie elementy z listy.
• E set(int index, E element) – zamienia element we wskazanym indeksie na ten podany w argumencie.
• <T> T[] toArray(T[] array) – zwraca listę w postaci tablicowej.
• void trimToSize() – zmniejsza pojemność wewnętrznej tablicy listy do rozmiaru kolekcji.
• E get(int index)– zwraca element o podanym indeksie.
• ListIterator<E> listIterator(int index) – zwraca iterator umieszczony na obiekcie o podanym indeksie.
• void sort(Comparator<? super E> collection) – sortuje listę wg. podanego komparatora. Aby było to możliwe musimy zaimplementować interfejs Comparable oraz metodę compareTo() w obiektach klas, które są elementami kolekcji.
• int size()– zwraca rozmiar listy (liczbę aktualnie przechowywanych obiektów, a nie pojemności listy).

Metodę get(int index) wypisaliśmy tylko dlatego, że jest ona dostępna, jednak nie należy z niej korzystać, a w zamian korzystać z obiektu Iterator. Załóżmy, że w liście znajduje się 10 000 elementów, a my chcemy uzyskać numery 4000 i 4001. Można to zrobić w następujący sposób.

Dlaczego jednak nie pokusić się o metodę get(n)? Otóż przemawia za tym optymalizacja i liczba operacji. W przypadku get() za każdym razem kolekcja jest przemierzana od początku co oznacza dwa razy więcej operacji niż w przypadku wykorzystania iteratora.

Podsumowanie LinkedList

Nie ma jednoznacznej odpowiedzi, która implementacja kolekcji jest lepsza. Dobrze jest wcześniej znać szczegóły działania, aby móc wybrać optymalne rozwiązanie do swojego programu. LinkedList należy wybrać gdy będziemy mieć pewność, że będzie dużo modyfikacji w środku listy (zwiększenia bądź zmniejszenia liczby węzłów) i stosunkowo mało odczytów. Natomiast gdy liczba elementów będzie stała, a liczba odczytów duża, należy zdecydowanie wybrać ArrayList.