0Pricing
Java Academy · Lekcja

LinkedList a ArrayList — kompromisy

Porównuj wydajność wstawiania, usuwania i swobodnego dostępu, aby wybrać właściwy typ listy.

LinkedList a ArrayList — kompromisy to bezpłatna lekcja Java Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Java Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Java Academy zawiera 4 lekcji w sumie.

Kluczowe pytanie

Zarówno ArrayList, jak i LinkedList implementują List, więc udostępniają ten sam interfejs API. Różnica tkwi w ich wewnętrznych strukturach danych oraz w operacjach, które każda z nich wykonuje wydajnie.

Wewnętrzne działanie ArrayList

ArrayList przechowuje elementy w ciągłej tablicy. Gdy tablica się zapełni, jest zastępowana nową tablicą większą 1,5×, a wszystkie elementy są kopiowane.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

Wewnętrzne działanie LinkedList — ponownie

Każdy element znajduje się we własnym obiekcie Node ze wskaźnikami prev/next. Brak ciągłej pamięci — węzły mogą znajdować się w dowolnych miejscach sterty.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

Dostęp losowy: ArrayList wygrywa

ArrayList.get(i) ma złożoność O(1) — to bezpośredni indeks tablicy. LinkedList.get(i) ma złożoność O(n) — przechodzi przez maksymalnie n/2 węzłów.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

Wstawianie na początku: LinkedList wygrywa

Dodanie elementu pod indeksem 0 w ArrayList wymaga przesunięcia wszystkich elementów — O(n). LinkedList aktualizuje tylko dwa wskaźniki — O(1).

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

Wstawianie na końcu: mniej więcej remis

Zarówno ArrayList, jak i LinkedList zapewniają zamortyzowane dodawanie elementów na końcu w czasie O(1). ArrayList sporadycznie uruchamia kopiowanie podczas zmiany rozmiaru, ale w ujęciu zamortyzowanym nadal jest to O(1). LinkedList przydziela nowy węzeł — zmiana rozmiaru nie jest potrzebna.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

Zużycie pamięci

ArrayList: ~8 bajtów na element (jedno odwołanie w tablicy). LinkedList: ~48 bajtów na element (obiekt Node z danymi, wskaźnikami prev i next oraz nagłówkiem obiektu). W przypadku dużych zbiorów danych ArrayList zużywa znacznie mniej pamięci.

Wydajność iteracji

Iteracja sekwencyjna (pętla for-each lub iterator) ma złożoność O(n) dla obu struktur. ArrayList korzysta jednak z pobierania danych z wyprzedzeniem przez pamięć podręczną procesora — elementy są ułożone ciągle w pamięci. Węzły LinkedList są rozproszone na stercie, co powoduje chybienia pamięci podręcznej.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

Wstawianie/usuwanie w środku

W obu przypadkach znalezienie pozycji wymaga O(n). Po jej znalezieniu ArrayList przesuwa elementy w czasie O(n), a LinkedList tylko odłącza element w czasie O(1). Dlatego przy częstych modyfikacjach środka gdy iterator jest już dostępny LinkedList wygrywa; w przeciwnym razie obie struktury są podobne.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

Wskazówki dotyczące wyboru

Wybór zależy od dominującej operacji:

  • ArrayList: dostęp losowy, iteracja, dodawanie na końcu — obejmuje 90% przypadków użycia
  • LinkedList: częste wstawianie/usuwanie na początku lub końcu, implementowanie kolejki/deque/stosu
  • ArrayDeque: gdy potrzebny jest wyłącznie stos lub kolejka (lepszy wybór niż LinkedList)

Podsumowanie testów wydajności

Model wydajności, który warto zapamiętać:

  • get(i): ArrayList O(1) a LinkedList O(n)
  • add(0,x): ArrayList O(n) a LinkedList O(1)
  • add(x): w obu przypadkach zamortyzowane O(1)
  • Usuwanie przez iterator: w obu przypadkach O(1) po ustawieniu pozycji
  • Pamięć na element: ArrayList ~8B a LinkedList ~48B

Szybki test

Tworzona jest kolejka zadań, do której zadania są dodawane na końcu i usuwane z początku miliony razy na sekundę. Która struktura danych jest najbardziej odpowiednia?

Podsumowanie: LinkedList a ArrayList

Najważniejsze informacje:

  • ArrayList świetnie sprawdza się przy dostępie swobodnym (O(1)) i iterowaniu przyjaznym dla pamięci podręcznej
  • LinkedList świetnie sprawdza się przy operacjach O(1) na początku i końcu listy
  • Pamięć: około 8 B na element w ArrayList; około 48 B na element w LinkedList
  • W przypadku kolejek i stosów należy preferować ArrayDeque zamiast LinkedList
  • ArrayList to właściwy wybór domyślny w większości przypadków

Często zadawane pytania

Czy lekcja „LinkedList a ArrayList — kompromisy” jest bezpłatna?

Tak — pełny tekst „LinkedList a ArrayList — kompromisy” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Java Academy, przejdź na CoddyKit PRO. Kurs Java Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „LinkedList a ArrayList — kompromisy”?

Porównuj wydajność wstawiania, usuwania i swobodnego dostępu, aby wybrać właściwy typ listy. Ćwiczysz Java Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Java Academy?

Nie wymagamy żadnego doświadczenia. Java Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „LinkedList a ArrayList — kompromisy”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Java Academy?

Tak. Każda lekcja Java Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Wewnętrzne działanie LinkedList
  2. Operacje Deque: stos i kolejka
  3. LinkedList a ArrayList — kompromisy
  4. PriorityQueue do uporządkowanego przetwarzania
← Powrót do Java Academy