Programski jezici → Java → Kolekcije u Javi: ArrayList i LinkedList

Kolekcije u Javi: ArrayList i LinkedList

ArrayList: osnovne operacije

U uglastim zagradama navodi se tip elemenata (generički tip). Za proste tipove koriste se klase omotači: Integer umesto int, Double umesto double, Character umesto char.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> imena = new ArrayList<>();
        imena.add("Ana");                    // dodaje na kraj
        imena.add("Marko");
        imena.add("Iva");
        imena.add(1, "Luka");                // umeće na poziciju 1
        System.out.println(imena + " velicina " + imena.size());

        System.out.println("Na poziciji 2: " + imena.get(2));
        imena.set(0, "Ana Marija");          // menja element
        imena.remove("Iva");                 // uklanja po vrednosti
        imena.remove(0);                     // uklanja po poziciji
        System.out.println(imena);
        System.out.println("Sadrzi Marko? " + imena.contains("Marko") + ", pozicija " + imena.indexOf("Marko"));
    }
}

Prolazak kroz listu

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> brojevi = new ArrayList<>();
        // učitavaj dok ne dođe 0 – broj elemenata nije unapred poznat
        int x;
        while ((x = sc.nextInt()) != 0)
            brojevi.add(x);

        int zbir = 0;
        for (int b : brojevi)                 // for-each
            zbir += b;
        System.out.println("Ucitano " + brojevi.size() + ", zbir " + zbir);

        // klasična petlja kada treba indeks
        for (int i = 0; i < brojevi.size(); i++)
            if (brojevi.get(i) > zbir / brojevi.size())
                System.out.println("iznad proseka: " + brojevi.get(i) + " (pozicija " + i + ")");

        // uklanjanje u toku prolaska: removeIf (ne remove u for-each petlji!)
        brojevi.removeIf(b -> b % 2 == 0);
        System.out.println("Neparni: " + brojevi);
    }
}

Uklanjanje elemenata u for-each petlji baca ConcurrentModificationException. Koristi removeIf sa uslovom (lambda izraz b -> b % 2 == 0 čita se „element b takav da je paran“) ili petlju unazad po indeksu.

Sortiranje: Collections.sort i Comparator

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(List.of(5, 2, 9, 1, 7));
        Collections.sort(a);                              // rastuće
        System.out.println(a);
        a.sort(Comparator.reverseOrder());                // opadajuće
        System.out.println(a);
        System.out.println("max=" + Collections.max(a) + " min=" + Collections.min(a));

        List<String> reci = new ArrayList<>(List.of("sljiva", "kivi", "jabuka", "dunja"));
        Collections.sort(reci);                           // abecedno
        System.out.println(reci);
        reci.sort(Comparator.comparing(String::length));  // po dužini (stabilno)
        System.out.println(reci);
    }
}

List.of(...) pravi listu koja se ne može menjati; zato se njeni elementi kopiraju u new ArrayList<>(...).

Lista objekata i sortiranje po više kriterijuma

Za sopstvene klase redosled se zadaje Comparator-om. Metode comparing i thenComparing grade poređenje po više polja:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
    // record: kratak zapis klase sa poljima, konstruktorom, geterima i toString (Java 16+)
    record Ucenik(String ime, int razred, double prosek) { }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Ucenik> lista = new ArrayList<>();
        for (int i = 0; i < n; i++)
            lista.add(new Ucenik(sc.next(), sc.nextInt(), Double.parseDouble(sc.next())));

        // po razredu rastuće, pa po proseku opadajuće, pa po imenu
        lista.sort(Comparator.comparingInt(Ucenik::razred)
                .thenComparing(Ucenik::prosek, Comparator.reverseOrder())
                .thenComparing(Ucenik::ime));

        for (Ucenik u : lista)
            System.out.println(u.razred() + ". " + u.ime() + " " + u.prosek());
    }
}

Ucenik::razred je referenca na metodu – kraći zapis za u -> u.razred(). Više o tome u lekciji Lambda izrazi i Stream API.

LinkedList, red i stek

LinkedList je povezana lista: dodavanje i uklanjanje na početku i kraju je brzo, ali je get(i) spor (prolazi od početka). Za red (queue) i stek u Javi se preporučuje ArrayDeque:

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        // red: prvi ušao – prvi izašao (FIFO)
        Queue<String> red = new LinkedList<>();
        red.offer("Ana");
        red.offer("Marko");
        red.offer("Iva");
        System.out.println("Na redu je: " + red.poll() + ", ostali: " + red);

        // stek: poslednji ušao – prvi izašao (LIFO)
        Deque<Character> stek = new ArrayDeque<>();
        String izraz = "(a+[b*c])";
        boolean ispravno = true;
        for (char c : izraz.toCharArray()) {
            if (c == '(' || c == '[')
                stek.push(c);
            else if (c == ')' || c == ']') {
                char otv = c == ')' ? '(' : '[';
                if (stek.isEmpty() || stek.pop() != otv)
                    ispravno = false;
            }
        }
        System.out.println(izraz + (ispravno && stek.isEmpty() ? " ispravne zagrade" : " neispravne zagrade"));
    }
}

U praksi se najčešće koristi ArrayList.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje