Java'nın hazır veri yapıları: Collections

Sekiz haftadır bağlı listeyi, yığını ve kuyruğu elle yazdık. Gerçek projede bunları sıfırdan yazmazsın: Java’nın java.util paketinde hepsinin test edilmiş, hızlı versiyonları var. Bu haftanın amacı iki şey: elle yazdığın her yapının Java’daki karşılığını tanımak ve doğru işe doğru sınıfı seçmek. Sınav soruları genellikle “what is printed?” tipinde ve küçük tuzaklar içerir: remove(1) indeks mi değer mi, Stack ile ArrayDeque’nin toString farkı, boş kuyrukta poll ile remove farkı.

Altın kurallar:

1. Değişkeni arayüz tipiyle tanımla. List<Integer> a = new ArrayList<>();
2. Yığın ve kuyruk için ArrayDeque. Stack sınıfı eskidir.
3. İndeksle erişim çoksa ArrayList, uçlardan ekleme çoksa ArrayDeque/LinkedList.
4. Gezerken silme: Iterator.remove() ya da removeIf. for-each içinde list.remove yapma.
5. Anahtarla arama HashMap.

Collections Framework’ün haritası

Hepsi generic’tir: <Integer> gibi tip parametresi alır. İlkel tip (int, double) koyamazsın; sarmalayıcı sınıf (wrapper) kullanılır. Java int ile Integer arasında otomatik dönüşüm yapar (autoboxing).

ArrayList: büyüyen dizi

İçeride bir dizi tutar, dolunca yaklaşık 1.5 katı büyüklüğe kopyalar. 5. haftadaki “büyütülen dizi yığını” fikrinin aynısı.

List<String> s = new ArrayList<>();
s.add("A"); s.add("B"); s.add("C");
s.add(1, "X");          // araya ekle, sağı kaydır
s.set(0, "Y");          // değiştir
System.out.println(s + " size=" + s.size() + " indexOf(B)=" + s.indexOf("B") + " contains(A)=" + s.contains("A"));

[Y, X, B, C] size=4 indexOf(B)=2 contains(A)=false

TUZAK · remove(int) ve remove(Object). List<Integer> üzerinde list.remove(1) indeks 1’i siler. Değeri 1 olan elemanı silmek için list.remove(Integer.valueOf(1)) yaz. Java, int argüman görünce indeks versiyonunu seçer.

List<Integer> list = new ArrayList<>(List.of(10, 20, 30, 40));
list.remove(1);                     // indeks 1 → 20 gider
System.out.println(list);
list.remove(Integer.valueOf(30));   // değer 30
System.out.println(list);

[10, 30, 40]
[10, 40]

LinkedList: çift yönlü bağlı liste

3. haftadaki DoublyLinkedList’in hazır hali. Hem List hem Deque arayüzünü uygular, yani hem indeksle hem uçlardan kullanılabilir.

LinkedList<Integer> ll = new LinkedList<>();
ll.add(5); ll.addFirst(2); ll.addLast(8); ll.add(1, 4);
System.out.println(ll + " getFirst=" + ll.getFirst() + " get(2)=" + ll.get(2));
ll.removeLast(); ll.removeFirst();
System.out.println(ll);

[2, 4, 5, 8] getFirst=2 get(2)=5
[4, 5]

get(2) çalışır ama içeride baştan (ya da sondan, hangisi yakınsa) yürür: O(n). LinkedList üzerinde for (int i = 0; i < ll.size(); i++) ll.get(i) döngüsü toplam O(n²) olur. Gezmek için for-each kullan.

Ölçüm: n elemanı başa eklemek.

n=10000 ArrayList add(0) 3.1 ms, LinkedList addFirst 0.6 ms
n=20000 ArrayList add(0) 11.3 ms, LinkedList addFirst 0.8 ms
n=40000 ArrayList add(0) 46.2 ms, LinkedList addFirst 0.8 ms

n dört katına çıkınca ArrayList yaklaşık 15 kat yavaşladı (her ekleme O(n), toplam O(n²)). LinkedList neredeyse sabit kaldı (her ekleme O(1)). Süreler makineye göre değişir, oran değişmez.

Yığın ve kuyruk: ArrayDeque

ArrayDeque, 8. haftadaki dairesel dizi deque’sinin hazır halidir. Yığın olarak da kuyruk olarak da en hızlı seçenektir.

Deque<Integer> stack = new ArrayDeque<>();   // yığın
stack.push(1); stack.push(2); stack.push(3);
System.out.println(stack + " peek=" + stack.peek());

Queue<Integer> q = new LinkedList<>();       // kuyruk
q.offer(7); q.offer(3); q.offer(5);
System.out.println(q.poll() + " " + q.peek() + " " + q);

[3, 2, 1] peek=3
7 3 [3, 5]

Eski Stack sınıfı

java.util.Stack hâlâ var ve bazı hocalar onu kullanır. Vector’den türer, her metodu senkronizedir (yavaş) ve indeksle erişime de izin verir (yığın kuralını bozar).

Stack<Integer> st = new Stack<>();
st.push(1); st.push(2); st.push(3);
System.out.println(st.pop() + " " + st.peek() + " " + st);

3 2 [1, 2]

TUZAK · İki farklı toString. Aynı push sırasıyla Stack dipten tepeye ([1, 2, 3]), ArrayDeque tepeden dibe ([3, 2, 1]) yazar. pop ikisinde de 3 verir. Çıktı sorusunda hangi sınıf olduğuna bak.

İki aile: istisna mı, özel değer mi?

Boş kuyrukta:

null null
remove: NoSuchElementException
element: NoSuchElementException
deque peek=null
deque pop: NoSuchElementException
Stack pop: EmptyStackException
ArrayDeque null: NullPointerException

Son satır: ArrayDeque içine null konamaz, çünkü poll’un null döndürmesi “boş” anlamına gelir.

Iterator

Her koleksiyon bir Iterator verir: hasNext(), next(), remove(). for-each döngüsü arka planda bunu kullanır. Bağlı listede p = p.next ile yaptığın gezinmenin soyut hali.

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
Iterator<Integer> it = nums.iterator();
while (it.hasNext())
    if (it.next() % 2 == 0) it.remove();
System.out.println(nums);

[1, 3, 5]

for-each içinde listeyi doğrudan değiştirirsen iterator bunu fark eder ve bir sonraki next()’te ConcurrentModificationException fırlatır. Tek satırlık modern alternatif: nums.removeIf(x -> x % 2 == 0);

HashMap temelleri

Anahtar (key) ile değer (value) eşleyen tablo. Arama, ekleme, silme ortalama O(1). Nasıl çalıştığı (hashing) SEN2212’nin konusu; burada kullanmayı öğreniyoruz.

Map<String, Integer> count = new HashMap<>();
for (String w : "to be or not to be".split(" "))
    count.put(w, count.getOrDefault(w, 0) + 1);
System.out.println(count.get("to") + " " + count.get("or") + " " + count.get("is") + " size=" + count.size());
System.out.println(new TreeMap<>(count));

2 1 null size=4
{be=2, not=1, or=1, to=2}

HashMap’in gezinme sırası belirsizdir; sıralı istiyorsan TreeMap, ekleme sırası istiyorsan LinkedHashMap.

Hangi işe hangi yapı?

Sık yapılan hatalar

List<Integer> list = new ArrayList<>(List.of(10, 20, 30, 40));
list.remove(1);
System.out.println(list);
list.remove(Integer.valueOf(30));
System.out.println(list);

List<String> s = new ArrayList<>();
s.add("A"); s.add("B"); s.add("C");
s.add(1, "X");
s.set(0, "Y");
System.out.println(s + " " + s.indexOf("B") + " " + s.contains("A"));

Stack<Integer> st = new Stack<>();
st.push(1); st.push(2); st.push(3);
System.out.println(st.pop() + " " + st.peek() + " " + st);

Deque<Integer> ad = new ArrayDeque<>();
ad.push(1); ad.push(2); ad.push(3);
System.out.println(ad + " peek=" + ad.peek());

Queue<Integer> q = new LinkedList<>();
q.offer(7); q.offer(3); q.offer(5);
System.out.println(q.poll() + " " + q.peek() + " " + q);
q.offer(q.poll());
System.out.println(q);

System.out.println(q.poll());
System.out.println(q.peek());
q.remove();

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
Iterator<Integer> it = nums.iterator();
while (it.hasNext())
    if (it.next() % 2 == 0) it.remove();
System.out.println(nums);

List<Integer> a = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : a) if (x == 2) a.remove(x);   // (i)

List<Integer> b = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : b) if (x == 3) b.remove(x);   // (ii)
System.out.println(b);

Map<String, Integer> count = new HashMap<>();
for (String w : "to be or not to be".split(" "))
    count.put(w, count.getOrDefault(w, 0) + 1);
System.out.println(count.get("to") + " " + count.get("or") + " " + count.get("is") + " size=" + count.size());

Map<String, Integer> m = new HashMap<>();
System.out.println(m.put("ali", 70));
System.out.println(m.put("ali", 85));
m.put("ece", 90);
System.out.println(m.get("ali") + " " + m.size() + " " + m.getOrDefault("can", -1));