LinkedList (zoznam): Dátová štruktúra linked list v Jave
Java LinkedList je jednou z množstva dátových štruktúr (kolekcií) na jednoduchšiu prácu s dátami. V našom seriáli si postupne predstavíme aj rôzne ďalšie, ukážeme si ako s nimi pracovať, aké operácie sa s nimi dajú robiť, aké sú najčastejšie používané metódy, spomenieme výhody a nevýhody a kedy je vhodne tú ktorú dátovú štruktúru použiť.
V článku sa dozvieš:
V dnešnej časti sa zameriame na kolekciu LinkedList, ktorá reprezentuje obojstranne spojený zoznam, umožňujúci efektívne operácie pridávania a odstraňovania prvkov na ľubovoľnej pozícii.
LinkedList v Java – predstavenie dátovej štruktúry
V prípadoch, keď statické polia alebo kolekcie ako ArrayList nie sú dostatočne výkonné, pretože často pridávame alebo odstraňujeme prvky na začiatku alebo v strede, môžeme použiť triedu LinkedList. Táto trieda využíva dátovú štruktúru obojstranne spojeného zoznamu, kde každý prvok obsahuje referencie na predchádzajúci a nasledujúci prvok.
Trieda LinkedList bola predstavená v Jave 1.2 ako súčasť balíka java.util. Implementuje rozhrania List, Deque, a Queue a to jej umožňuje byť flexibilnou nielen ako lineárny zoznam, ale aj ako klasický front alebo obojsmerný front.
Keďže do LinkedList sa kvôli svojej implementácii nedá pristupovať pomocou náhodného prístupu ako pri ArrayList, prístup ku prvkom na danom indexe sa realizuje prechádzaním prvkov od začiatku zoznamu (head) alebo od konca zoznamu (tail), podľa toho, ktorí z nich je bližšie ku indexu daného prvku.
LinkedList – konštruktory
Na vytvorenie inštancie LinkedList môžeme použiť jeden z nasledujúcich konštruktorov:
1. Prázdny LinkedList
Vytvorí prázdny LinkedList.
LinkedList<String> list = new LinkedList<>();2. LinkedList skonštruovaný z kolekcie
Inicializuje LinkedList prvkami z danej kolekcie.
List<String> vegetables = List.of("Tomatoes", "Potatoes");
LinkedList<String> list = new LinkedList<>(vegetables);LinkedList – základné operácie
K základným operáciám s LinkedList patria:
- Pridávanie prvkov
– Na začiatok pomocou addFirst().
– Na koniec pomocou addLast() alebo add().
– Na konkrétnu pozíciu pomocou add(index, element). - Aktualizácia prvkov
Pomocou metódy set(index, element) môžeme nahradiť prvok na určitom indexe. - Odstraňovanie prvkov
Prvky môžeme odstraňovať pomocou removeFirst(), removeLast(), alebo remove(index).
Odstránenie všetkých prvkov pomocou clear(). - Prístup k prvkom
Použitie metódy get(index) na získanie prvku podľa indexu, getFirst(), getLast(). - Prechádzanie cez prvky
Pomocou cyklov for, for-each, alebo cez Iterator. - Hľadanie prvkov
Metódy contains() a indexOf() umožňujú vyhľadávať konkrétne hodnoty. - Zotriedenie prvkov
Použitie metódy sort() so zadaným porovnávačom (Comparator).
LinkedList – dokumentácia
Kompletný prehľad metód triedy LinkedList nájdeš v oficiálnej dokumentácii.
Java LinkedList – výhody a nevýhody
Výhody LinkedList
- Efektívne pridávanie a odstraňovanie prvkov na začiatku alebo v strede zoznamu
Operácie ako addFirst(), add(index, element), alebo remove(index) sú rýchlejšie v porovnaní s ArrayList, pretože nevyžadujú presun prvkov, iba zmenu referencií. - Flexibilita v používaní
LinkedList implementuje rozhrania List, Deque, a Queue, čo mu umožňuje fungovať ako lineárny zoznam, fronta (FIFO), alebo zásobník (LIFO). - Nevyžaduje spojité bloky pamäte
Prvky sú uložené v uzloch rozmiestnených po pamäti, čo môže byť výhodné, ak nie je k dispozícii dostatočne veľký spojitý blok pamäte. - Rovnaká rýchlosť pridávania a odstraňovania na začiatku aj na konci
Operácie ako addFirst() a addLast() sú rovnako efektívne vďaka referenciám na prvý a posledný uzol.
Nevýhody LinkedList
- Náhodný prístup k prvkom je pomalý
Pri prístupe pomocou get(index) alebo pri iterácii cez zoznam musí prechádzať uzly jeden po druhom, to môže byť neefektívne pri veľkom počte prvkov. Naopak, ArrayList ponúka rýchly náhodný prístup. - Vyššia pamäťová náročnosť
Každý uzol v LinkedList vyžaduje dodatočnú pamäť na uloženie referencií na predchádzajúci a nasledujúci uzol, čo môže byť nevýhodné pri veľkých kolekciách. - Nižšia efektivita pri iterácii
Kvôli absencii indexov je iterácia cez prvky pomalšia, pretože musí prechádzať celý zoznam uzol po uzle.
LinkedList – kedy ho použiť a kedy nie?
LinkedList je ideálny v nasledovných prípadoch:
- Ak často pridávame alebo odstraňujeme prvky na začiatku alebo v strede zoznamu.
- Ak zoznam má fungovať ako fronta (FIFO) alebo zásobník (LIFO).
- Ak nevyžadujeme častý náhodný prístup k prvkom.
Naopak, nie je vhodný, ak:
- Ak potrebujeme rýchly prístup k prvkom podľa indexu.
- Ak pracujeme s veľkými kolekciami, kde je dôležitá pamäťová efektívnosť. V takom prípade je ArrayList môže lepšou voľbou.
ArrayList vs LinkedList – časová zložitosť základných operácií
| Add Element | Remove Element | Get By Index | Contains Element | |
| ArrayList | O(1) | O(n) | O(1) | O(n) |
| LinkedList | O(1) | O(1) | O(n) | O(n) |
Príklad použitia LinkedList v Jave
Teraz sa pohráme s kolekciou LinkedList v Jave a urobíme si program so zameraním na dynamické triedenie a spracovanie prvkov. Začína vytvorením počiatočného zoznamu znakov (A-F) s viacerými (konkrétne tromi) kópiami, následne tento zoznam zamieša a spracováva ho postupne, prvok po prvku.
Počas spracovania sa jednotlivé znaky odstraňujú zo zamiešaného zoznamu a vkladajú do nového LinkedList-u na správne pozície tak, aby bol vždy zotriedený. Program zároveň sleduje náhodne vybraný cieľový znak (napr. D) a zastaví sa, keď sa tento znak objaví v zoradenom zozname trikrát. Výstup na konzolu ukazuje všetky kroky procesu vrátane odstraňovania, vkladania a konečného stavu zoradeného zoznamu.
Main.java
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public class Main {
public static void main(String[] args) {
// Prepare the initial list.
List<Character> initialList = new LinkedList<>();
// Add the first set of letters A-F using addAll.
initialList.addAll(List.of('A', 'B', 'C', 'D', 'E', 'F'));
// Add the second set of letters A-F to the beginning.
for (char c = 'A'; c <= 'F'; c++) {
((LinkedList<Character>) initialList).addFirst(c);
}
// Add the third set of letters A-F to the end.
for (char c = 'A'; c <= 'F'; c++) {
((LinkedList<Character>) initialList).addLast(c);
}
// Shuffle the list.
Collections.shuffle(initialList);
System.out.println("Initial shuffled list: " + initialList);
// Randomly select a letter to track.
char targetChar = (char) ('A' + new Random().nextInt(6));
System.out.println("Tracking letter: " + targetChar);
// Create sorted LinkedList.
LinkedList<Character> sortedList = new LinkedList<>();
// Process elements.
while (!initialList.isEmpty()) {
// Remove the first element from the initial list.
Character current = initialList.removeFirst();
System.out.println("Removed element from initial list: " + current);
// Insert the element in the correct position (sorted)
insertSorted(sortedList, current);
// Check if the tracked letter (targetChar) is in the correct positions
if (isTargetComplete(sortedList, targetChar)) {
System.out.println("We have reached 3x correct positions for '" + targetChar + "'.");
break;
}
}
System.out.println("Final state of the sorted list: " + sortedList);
}
// Method to insert an element into the LinkedList in the correct position.
private static void insertSorted(LinkedList<Character> list, Character element) {
int index = 0;
while (index < list.size() && list.get(index) < element) {
index++;
}
// Insert at the correct position.
list.add(index, element);
System.out.println("Added '" + element + "' at index " + index + ": " + list);
}
// Method to check if the tracked letter appears 3 times in the correct positions.
private static boolean isTargetComplete(LinkedList<Character> list, char target) {
int count = 0;
for (Character c : list) {
if (c == target)
count++;
}
// If the letter is found 3 times, the task is complete.
return count == 3;
}
}Výstup z tohto príkladu je:
Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si Java kód pre LinkedList tu.
