Wewnętrzne działanie LinkedList
Poznaj strukturę dwukierunkowo połączonych węzłów LinkedList oraz charakterystykę jej złożoności czasowej.
Wewnętrzne działanie LinkedList to bezpłatna lekcja Java Academy na CoddyKit. To lekcja 1 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.
Wewnętrzne działanie LinkedList
Java's LinkedList to lista dwukierunkowa: każdy węzeł przechowuje odwołanie do poprzedniego i następnego węzła oraz wartość elementu. W przeciwieństwie do ArrayList nie ma tablicy bazowej — pamięć jest przydzielana dla każdego węzła.
class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) { this.data = data; }
}Charakterystyka złożoności czasowej
Charakterystyka wydajnościowa LinkedList znacznie różni się od ArrayList:
- addFirst / addLast: O(1)
- get(index): O(n) — trzeba przejść od początku lub końca
- remove(index): O(n) na znalezienie, a następnie O(1) na odłączenie
- Iterator traversal: O(n)
LinkedList należy używać, gdy potrzebne są częste wstawienia na początku lub końcu, a nie dostęp losowy.
Tworzenie i przechodzenie po LinkedList
Tworzenie LinkedList i iteracja przebiegają przez ten sam interfejs List, który jest już znany. Różnica dotyczy struktury wewnętrznej.
import java.util.LinkedList;
LinkedList<String> list = new LinkedList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");
for (String name : list) {
System.out.println(name);
}
System.out.println("First: " + list.getFirst()); // Alice
System.out.println("Last: " + list.getLast()); // CaroladdFirst, addLast, removeFirst, removeLast
LinkedList udostępnia operacje na początku i końcu, których ArrayList nie oferuje wydajnie:
LinkedList<Integer> nums = new LinkedList<>();
nums.addLast(10); // [10]
nums.addLast(20); // [10, 20]
nums.addFirst(5); // [5, 10, 20]
System.out.println(nums.removeFirst()); // 5 → [10, 20]
System.out.println(nums.removeLast()); // 20 → [10]Odłączanie węzła: usunięcie O(1) po znalezieniu
Po uzyskaniu odwołania do węzła (za pomocą iteratora) usunięcie ma złożoność O(1), ponieważ trzeba zaktualizować tylko wskaźniki next/prev — nie ma przesuwania elementów jak w ArrayList.
import java.util.*;
LinkedList<String> tasks = new LinkedList<>(List.of("A","B","C","D"));
Iterator<String> it = tasks.iterator();
while (it.hasNext()) {
String t = it.next();
if (t.equals("B") || t.equals("D")) {
it.remove(); // O(1) unlink
}
}
System.out.println(tasks); // [A, C]Narzut pamięci względem ArrayList
Każdy węzeł LinkedList przechowuje dwa dodatkowe odwołania (prev, next) oraz odwołanie do elementu — około 48 bajtów na wpis w 64-bitowej maszynie JVM. ArrayList przechowuje tylko odwołanie do elementu (8 bajtów) w ciągłej tablicy.
W przypadku dużych zbiorów danych, w których przeważają operacje odczytu, ArrayList zwykle lepiej wykorzystuje pamięć podręczną i zajmuje mniej pamięci.
Operacje Deque: stos i kolejka
LinkedList implementuje interfejs Deque, dzięki czemu można jej używać jako stosu i kolejki.
import java.util.LinkedList;
import java.util.Deque;
// As a Queue (FIFO)
Deque<String> queue = new LinkedList<>();
queue.offer("first");
queue.offer("second");
System.out.println(queue.poll()); // first
// As a Stack (LIFO)
Deque<String> stack = new LinkedList<>();
stack.push("bottom");
stack.push("top");
System.out.println(stack.pop()); // topOmówienie PriorityQueue
PriorityQueue to kolejka oparta na kopcu, w której najmniejszy element (według naturalnego porządku lub komparatora) jest zawsze usuwany jako pierwszy. NIE jest oparta na liście wiązanej — używa tablicy kopca binarnego.
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(40);
pq.offer(10);
pq.offer(25);
System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 25
System.out.println(pq.poll()); // 40PriorityQueue z niestandardowym komparatorem
Przekaż Comparator, aby odwrócić kolejność lub sortować według niestandardowego pola:
import java.util.*;
record Task(String name, int priority) {}
PriorityQueue<Task> tasks = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).reversed() // highest first
);
tasks.offer(new Task("Low", 1));
tasks.offer(new Task("High", 10));
tasks.offer(new Task("Med", 5));
while (!tasks.isEmpty()) {
System.out.println(tasks.poll().name());
}
// High, Med, LowWybór między LinkedList a ArrayList
Ogólna zasada:
- Używaj ArrayList do dostępu losowego, iteracji i w większości scenariuszy.
- Używaj LinkedList, gdy potrzebne są częste wstawienia/usunięcia w czasie O(1) na obu końcach i nie jest potrzebny dostęp indeksowy.
- Używaj PriorityQueue, gdy potrzebne jest uporządkowane przetwarzanie (planowanie zadań, algorytm Dijkstry).
Typowe pułapki
Unikaj wywoływania get(i) w pętli dla LinkedList — łączna złożoność wynosi O(n²):
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add(i);
// BAD: O(n^2) — each get(i) traverses from head
for (int i = 0; i < list.size(); i++) {
int val = list.get(i); // slow!
}
// GOOD: O(n) — use iterator
for (int val : list) {
// process val
}Szybki test
Jaka operacja LinkedList ma złożoność O(1) niezależnie od rozmiaru listy?
Podsumowanie: LinkedList i Deque
Najważniejsze informacje:
- LinkedList to lista dwukierunkowa z operacjami na początku i końcu w czasie O(1)
- Dostęp losowy (get/set według indeksu) ma złożoność O(n)
- Implementuje Deque — można jej używać jako stosu lub kolejki
- PriorityQueue zapewnia przetwarzanie uporządkowane według kopca
- W większości przypadków należy preferować ArrayList; LinkedList sprawdza się przy częstych modyfikacjach początku i końca
Często zadawane pytania
Czy lekcja „Wewnętrzne działanie LinkedList” jest bezpłatna?
Tak — pełny tekst „Wewnętrzne działanie LinkedList” 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 „Wewnętrzne działanie LinkedList”?
Poznaj strukturę dwukierunkowo połączonych węzłów LinkedList oraz charakterystykę jej złożoności czasowej. Ć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 1 z 4.
Ile czasu zajmuje lekcja „Wewnętrzne działanie LinkedList”?
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
- Wewnętrzne działanie LinkedList
- Operacje Deque: stos i kolejka
- LinkedList a ArrayList — kompromisy
- PriorityQueue do uporządkowanego przetwarzania