List ehk järjend

Sissejuhatus

Järjend on korrastatud andmekogum. See tähendab, et see säilitab elementide järjekorra. Kui lisada elemendid loendisse, siis hiljem on nad lugemisel täpselt samas järjekorras kui sisestamisel.

Javas on mitmeid erinevaid järjendeid. Enim kasutatavad nendest on List liidesel põhinevad implementatsioonid ArrayList ning LinkedList.

ArrayList

ArrayList on List implementatsioon, mis töötab sisemiselt massiivide põhjal. ArrayList sees olevat massiivi suurust muudetakse automaatselt, kui selleks tekib vajadus.

ArrayList-i loomine

ArrayList-i saab luua järgnevalt:

// Empty list
ArrayList<String> names = new ArrayList<>();

// List with initial elements
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);

ArrayList-i töö põhimõte

Nagu varasemalt mainitud, siis ArrayList hoiab endas massiivi, kuhu elemendid salvestatakse. Elemendi järjendisse lisamisel:

1. Elemente lisatakse järjest massiivi
2. Kui massiiv saab täis, siis luuakse uus suurem massiiv
3. Elemendid kopeeritakse vanalt uuele üle
4. Vana massiiv kustutatakse.

See võimaldab kiiret ligipääsu elementidele läbi indeksite, nagu tavapäraste massiivide puhul. Samas elementide lisamine ja eemaldamine võib osutada kulukaks ettevõtmiseks sõltuvalt järjendi suurusest. Kui elemente lisada järjendi lõppu, siis selle kiirus on hetkeline ehk O(1) kiirusega. Elementide lisamisel näiteks järjendi algusesse või keskele peab esiteks ruumi tegema selleks (elemente nihutama) ning alles siis saab selle soovitud asukohale lisada. See kiirus on O(n) ehk sõltub elementide arvust. Seega sobib see eriti hästi juhtudeks, kus on vaja elemente kiiresti nende asukoha järgi kätte saada.

Levinumad operatsioonid

Elementide lisamine

ArrayList<String> list = new ArrayList<>();
list.add("First");           // Add at end
list.add("Second");
list.add(1, "Middle");       // Insert at specific index

// Result: ["First", "Middle", "Second"]

// addAll allows to add multiple elements at once (merges lists)
list.addAll(Arrays.asList("a", "b", "c", "d"));

// Since Java 21 ArrayLists also support these methods
list.addFirst("a");
list.addLast("b");

Elementidele ligipääsemine

String first = list.get(0);               // Get by index
String last = list.get(list.size() - 1);  // Get last element

// Since Java 21 ArrayLists also support these methods
list.getFirst();
list.getLast();

Elementide muutmine

list.set(0, "Updated");      // Replace element at index

Elementide eemaldamine

list.remove(0);              // Remove by index
list.remove("Second");       // Remove by value (removes first occurrence)

list.removeAll(Arrays.asList("a", "b"));   // Removes all "a" and "b" from list

list.clear();               // Clears the whole list

// Since Java 21 ArrayLists also support these methods
list.removeFirst();
list.removeLast();

Järjendi sisu kontrollimine

// Checks if element(s) exists in list
boolean hasElement = list.contains("First");
boolean hasElements = list.containsAll(Arrays.asList("a", "b")); // True if all elements exist in list

// Returns position of element, first occurence
int position = list.indexOf("Second");  // Returns -1 if not found

// Returns size of list
int size = list.size();

// Returns if list is empty or not
boolean empty = list.isEmpty();

warninghoiatus

Seda, kas järjend on tühi või mitte, võiks kontrollida isEmpty meetodiga:

if (list.size() == 0) {}    // Bad example
if (list.isEmpty()) {}     // Good example

Alamjärjendi loomine

List<String> list = new ArrayList<>(Arrays.asList("b", "c", "a", "b", "a"));
list.subList(1, 3); // ["c", "a"]

LinkedList

LinkedList salvestab elemente sõlmedena (node), kus iga sõlm sisaldab endas elemendi väärtust ning viidet järgmisele ja eelmisele sõlmele.

LinkedList-i loomine

LinkedList-i loomine on sarnane ArrayList-iga:

LinkedList<String> names = new LinkedList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");

LinkedList-i töö põhimõte

LinkedList kasutab kahepoolset seotud ahelat (doubly linked list), kus iga element on eraldi sõlm. Iga sõlm sisaldab väärtust ning viiteid nii eelmisele kui ka järgmisele sõlmele.

Diagrammil näitavad nooled, et iga otspunkt teab oma naaberpunkti mõlemas suunas, mis võimaldab efektiivset liikumist edasi ja tagasi ahelas.

See tähendab, et:

• Indeksipõhine ligipääs elementidele on aeglane, kuna elemendini jõudmiseks tuleb ahel läbida kas algusest või lõpust.
• Elementide lisamine on kiire, kuna vaja on muuta vaid sõlmede viiteid.
• Sobib olukorras, kus on vaja tihedalt läbi viia muudatusi.

LinkedList-i spetsiifilised operatsioonid

Kuigi alates Java versioon 21-st on need meetodid olemas ka ArrayList-is, siis need algselt olid olemas ainult LinkedList-is. Need meetodid keskenduvad järjendi otstes (alguses/lõpus) opereerimisele:

// Adding to beginning or end
list.addFirst("First");      // Add at beginning
list.addLast("Last");        // Add at end (same as add())

// Accessing beginning or end
String first = list.getFirst();
String last = list.getLast();

// Removing from beginning or end
list.removeFirst();
list.removeLast();

ArrayList ja LinkedList jõudluse võrdlus

Operation	ArrayList	LinkedList
Indeksi põhine ligipääs - get(i)	Kiire O(1)	Aeglane O(n)
Elemendi lisamine lõppu - add(e)	Kiire O(1)*	Kiire O(1)
Elemendi lisamine algusesse - add(0, e)	Aeglane O(n)	Kiire O(1)
Elemendi lisamine keskele add(i, e)	Aeglane O(n)	Aeglane O(n)
Lõpust eemaldamine	Kiire O(1)	Kiire O(1)
Algusest eemaldamine	Aeglane O(n)	Kiire O(1)
Mälukasutus	Väike	Suur

* - ArrayList-i add() meetod on tavaliselt O(1) kiirusega, kuid sisemise massiivi suurendamisel on O(n) kiirusega.

Kumba millal eelistada?

Eelista ArrayList-i juhul, kui:

• Vajad kiiret ligipääsu elementidele indeksi alusel
• Lisad või eemaldad elemente peamiselt lõpust
• Läbid järjendit sageli tsükkliga
• Mälukasutuse efektiivsus on oluline

Samuti on ArrayList-i puhul tegemist kõige levinumalt kasutusel oleva implementatsiooniga. Seda kasutatakse vaikimisi pea kõikjal.

Eelista LinkedList-i juhul, kui:

• Lisad või eemaldad elemente sageli algusest
• Tegeled andmete järjekorrapõhise töötlemisega
• Harva kasutad indekseid andmetele ligipääsemiseks

Muutumatud järjendid

Lisaks tavapärastele järjenditele on võimalik ka luua muutumatuid (immutable) järjendeid. Nende puhul sisu sõltub sellest, mis initsialiseerimise hetkel järjendisse sisestati, peale mida enam sisu muuta ei saa.

Muutumatuid järjendeid saab luua järgnevalt:

// Option 1: Create immutable lists directly
List<String> immutableList = List.of("A", "B", "C");
immutableList.add("D");  // Throws UnsupportedOperationException

// Option 2: Create a read-only list based on existing data
List<String> original = new ArrayList<>();
original.add("A");

List<String> readOnly = Collections.unmodifiableList(original);

Muutumatuid järjendeid tasub kasutada, kui järjendi sisu peab olema kas konstante (List.of) või on mingi protsessi tulemus, mida ei tohiks saada enam muuta (unmodifiableList).

Levinumad vead järjenditega tegelemisel

Järjendi töötlemine itereerimise ajal

Olukorras, kus üritada järjendit muuta seda tsükkliga läbimise ajal, lõppeb erindiga:

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

for (String item : list) {
    list.remove(item);  // ConcurrentModificationException
}

Selle vältimiseks tuleks kasutada Iterator-it, mis loob eraldi objekti järjendi elementide läbikäimiseks ja turvaliseks eemaldamiseks.

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    iterator.remove();  // Safe removal
}

IndexOutOfBoundsException

Massiividele sarnaselt peab ka järjendite puhul arvestama indeksite maksimaalse piirdega:

ArrayList<String> list = new ArrayList<>();
list.add("First");
System.out.println(list.get(1));  // IndexOutOfBoundsException

Kui pole kindel, kui suur võib järjend olla ning on vaja kindlalt indeksilt elementi kätte saada, siis tasuks alati eelnev kontroll teha:

if (list.size() > 1) {
    System.out.println(list.get(1));
}

Järjendite omavaheline võrdlemine

Javas järjendid on objektid, seega == operaatoriga neid võrrelda ei tohiks. Objektide omavaheliseks võrdlemiseks on ette nähtud .equals() meetod. Järjendid implementeerivad .equals() meetodit elementide sisu ja järjestuse alusel. Kui kaks järjendit koosnevad samadest elementidest, aga erineva järjestusega, siis need loetakse erinevateks järjenditeks.

Seda probleemi annab lahendada mitmel erineval viisil, üks nendest oleks näiteks esmalt järjendite sorteerimine ning siis võrdsuse kontrollimine:

List<String> list1 = new ArrayList<>(Arrays.asList("C", "A", "B"));
List<String> list2 = new ArrayList<>(Arrays.asList("A", "B", "C"));

Collections.sort(list1);
Collections.sort(list2);
System.out.println(list1.equals(list2));   // true

warninghoiatus

Collections.sort muudab algsete järjendite järjekorda. Kui originaalsete järjendite järjekord on tähtis, siis tasub enne sorteerimist nendest koopia teha ning koopiate peal tegeleda.