LinkedList – List

LinkedList to jedna z fundamentalnych struktur danych oferowanych przez język Java w ramach kolekcji w bibliotece standardowej. Jest to implementacja interfejsu List, która pozwala na efektywne zarządzanie elementami w kolekcji dzięki swojej dynamicznej strukturze. Pozwala na przechowywanie danych w uporządkowanej formie z zachowaniem kolejności wstawiania elementów, a jednocześnie umożliwia efektywne operacje na początku i końcu listy.

Struktura LinkedList

LinkedList jest oparta na węzłach, z których każdy przechowuje dane i referencje do poprzedniego oraz następnego węzła. Ta struktura nazywana jest listą dwukierunkową (ang. doubly linked list). Dzięki temu:

1. Wstawianie elementów na początku lub na końcu listy jest bardzo szybkie – odbywa się w czasie O(1).
2. Operacje na elementach w środku listy, takie jak dodawanie czy usuwanie, mogą wymagać przejścia przez kolejne węzły, co zajmuje czas O(n).

Każdy węzeł w LinkedList składa się z trzech głównych części:

• Referencji do poprzedniego węzła – umożliwia cofanie się w strukturze.
• Danych – właściwy element przechowywany w liście.
• Referencji do następnego węzła – pozwala na przechodzenie w przód.

Tworzenie LinkedList

Przykładowa inicjalizacja LinkedList w Javie wygląda następująco:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        // Dodawanie elementów do listy
        list.add("Element 1");
        list.add("Element 2");
        list.add("Element 3");

        // Wyświetlenie zawartości listy
        System.out.println("Lista: " + list);
    }
}

W powyższym przykładzie utworzono listę przechowującą obiekty typu String. Metoda add() dodaje element na końcu listy.

Główne metody w LinkedList

LinkedList dostarcza wielu przydatnych metod, które pozwalają na manipulację jej zawartością:

1. Dodawanie elementów:
   • add(E e) – dodaje element na końcu listy.
   • add(int index, E element) – wstawia element na określonym indeksie.
   • addFirst(E e) – dodaje element na początku listy.
   • addLast(E e) – dodaje element na końcu listy (tożsama z add(E e)).
2. Usuwanie elementów:
   • remove() – usuwa pierwszy element listy.
   • remove(int index) – usuwa element na wskazanym indeksie.
   • removeFirst() – usuwa pierwszy element listy.
   • removeLast() – usuwa ostatni element listy.
3. Pobieranie elementów:
   • get(int index) – zwraca element na wskazanym indeksie.
   • getFirst() – zwraca pierwszy element listy.
   • getLast() – zwraca ostatni element listy.
4. Sprawdzanie zawartości:
   • contains(Object o) – sprawdza, czy lista zawiera dany element.
   • isEmpty() – zwraca true, jeśli lista jest pusta.
5. Inne:
   • size() – zwraca liczbę elementów w liście.
   • clear() – usuwa wszystkie elementy z listy.

Przykłady zastosowań

Kolejka

LinkedList może być używana jako implementacja kolejki dzięki metodom addFirst i removeLast:

LinkedList<String> queue = new LinkedList<>();
queue.addLast("Zadanie 1");
queue.addLast("Zadanie 2");
queue.addLast("Zadanie 3");

System.out.println("Pierwsze zadanie: " + queue.removeFirst());

Stos

Można również wykorzystać LinkedList jako stos (Last-In-First-Out, LIFO):

LinkedList<String> stack = new LinkedList<>();
stack.addFirst("Element 1");
stack.addFirst("Element 2");
stack.addFirst("Element 3");

System.out.println("Zdejmowany element: " + stack.removeFirst());

Przechowywanie historii przeglądarki

LinkedList świetnie nadaje się do implementacji historii przeglądania stron internetowych, gdzie użytkownik może przechodzić wstecz i do przodu:

LinkedList<String> history = new LinkedList<>();
history.add("Strona główna");
history.add("Strona 1");
history.add("Strona 2");

System.out.println("Aktualna strona: " + history.getLast());
history.removeLast();
System.out.println("Powrót do: " + history.getLast());

Wydajność LinkedList

Zrozumienie wydajności operacji w LinkedList jest kluczowe do jej efektywnego wykorzystania:

• Dodawanie na początku/końcu: O(1) – dzięki wsparciu referencji do pierwszego i ostatniego węzła.
• Dostęp do elementu: O(n) – konieczne jest przejście przez węzły od początku lub końca listy.
• Usuwanie elementów: O(1) – na początku lub końcu; O(n) – w środku.

W związku z tym, LinkedList sprawdza się w scenariuszach, gdzie operacje są wykonywane głównie na końcu lub początku listy.

LinkedList vs ArrayList

Porównanie tych dwóch popularnych implementacji interfejsu List jest często zadawanym pytaniem:

Praktyczne wskazówki

1. Korzystaj z LinkedList, gdy konieczne są częste operacje na początku lub końcu listy.
2. Unikaj LinkedList, jeśli dostęp do elementów w środku listy jest kluczowy – lepiej wtedy wybrać ArrayList.
3. Pamiętaj, że LinkedList nie jest synchronizowana, co oznacza, że w środowiskach wielowątkowych należy dodatkowo zadbać o bezpieczeństwo wątków (np. używając Collections.synchronizedList()).

LinkedList to potężne narzędzie w rękach programisty, szczególnie w sytuacjach, gdy wymagane są dynamiczne zmiany w strukturze danych. Dzięki swoim unikalnym cechom może być podstawą wielu aplikacji i systemów, gdzie optymalizacja operacji na danych jest kluczowa.