Dizi algoritmaları ve ArrayList

Diziyi oluşturmayı ve gezmeyi biliyorsun. Bu hafta onunla yapılan standart işler var: arama, sayma, ters çevirme, kopyalama, kaydırma. Hepsi birkaç satırlık kalıplar ve sınavda “write a method” sorusu olarak tekrar tekrar gelir. İkinci yarıda dizinin boyut sorununu çözen ArrayList’i öğreneceksin.

Altın kurallar:

1. Arama bulunca hemen return eder, bulamazsa döngüden sonra -1.
2. Yerinde ters çevirmede döngü yarıya kadar gider: i < length / 2.
3. b = a kopya değildir. Kopya için yeni dizi aç.
4. ArrayList’te boyut size(), eleman get(i). Köşeli parantez yok.
5. Döngüde eleman siliyorsan sondan başa git.

Doğrusal arama ve sayma

public static int linearSearch(int[] arr, int key) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == key) return i;     // bulduk, hemen çık
    }
    return -1;                           // hiç bulunmadı
}
public static int count(int[] arr, int key) {
    int c = 0;
    for (int x : arr) if (x == key) c++;
    return c;
}
// main içinde:
int[] a = {8, 3, 5, 3, 1};
System.out.println(linearSearch(a, 3) + " " + linearSearch(a, 1) + " " + linearSearch(a, 7));
System.out.println(count(a, 3));

1 4 -1
2

-1 geçerli bir indeks olmadığı için “bulunamadı” anlamında kullanılır. return -1 satırı döngünün dışında olmalı. İçeride bir else’e koyarsan sadece ilk elemanı kontrol etmiş olursun.

Yerinde ters çevirme

Baştaki ile sondakini takas et, sonra ikinci ile sondan ikinciyi, ortaya kadar.

public static void reverse(int[] arr) {
    for (int i = 0; i < arr.length / 2; i++) {
        int temp = arr[i];
        arr[i] = arr[arr.length - 1 - i];
        arr[arr.length - 1 - i] = temp;
    }
}

{1, 2, 3, 4, 5} ve {1, 2, 3, 4} için:

[5, 4, 3, 2, 1]
[4, 3, 2, 1]

i   takas edilen indeksler   dizi (5 eleman)
0   0 ↔ 4                    [5, 2, 3, 4, 1]
1   1 ↔ 3                    [5, 4, 3, 2, 1]
2   döngü biter (2 < 5/2 = 2 false), ortadaki 3 yerinde kalır

TUZAK · sonuna kadar gitmek. Döngüyü i < arr.length yaparsan ilk yarıda ters çevirir, ikinci yarıda geri çevirirsin. Doğrulamada bu sürüm diziyi [1, 2, 3, 4, 5] olarak, yani hiç değişmemiş bıraktı.

Kopya ve takma ad (alias)

int[] orig = {1, 2, 3};
int[] alias = orig;                              // aynı dizi
int[] real = copy(orig);                         // döngüyle kopya
int[] c2 = Arrays.copyOf(orig, orig.length);     // hazır kopya
orig[0] = 99;
System.out.println(alias[0] + " " + real[0] + " " + c2[0]);
System.out.println((orig == alias) + " " + (orig == real));
int[] x1 = {1, 2}, x2 = {1, 2};
System.out.println((x1 == x2) + " " + Arrays.equals(x1, x2));

99 1 1
true false
false true

Döngüyle kopya şöyle yazılır:

public static int[] copy(int[] arr) {
    int[] result = new int[arr.length];
    for (int i = 0; i < arr.length; i++) result[i] = arr[i];
    return result;
}

== dizilerde içeriğe bakmaz, iki değişkenin aynı diziyi gösterip göstermediğine bakar. İçerik karşılaştırması için Arrays.equals (ya da kendi döngün).

Sıralı mı? Kaydırma. Sıralama.

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {     // i+1'i kullandığımız için length-1
        if (arr[i] > arr[i + 1]) return false;
    }
    return true;
}
public static void shiftLeft(int[] arr) {          // sola döndür
    int first = arr[0];
    for (int i = 0; i < arr.length - 1; i++) arr[i] = arr[i + 1];
    arr[arr.length - 1] = first;
}

isSorted({1, 3, 3, 7}), isSorted({1, 5, 2}), shiftLeft({10, 20, 30, 40}) ve Arrays.sort({5, 2, 9, 1}):

true false
[20, 30, 40, 10]
[1, 2, 5, 9]

İPUCU · i + 1 görürsen sınırı düşür. Döngüde arr[i + 1] kullanıyorsan son tur i = length - 2 olmalı, yoksa son turda dizinin dışına çıkarsın. Koşul i < arr.length - 1.

ArrayList: boyutu değişen dizi

Dizinin boyutu baştan sabittir. Kaç eleman geleceğini bilmiyorsan (kullanıcı -1 girene kadar sayı oku, listeden eleman sil) ArrayList kullanırsın. Kendisi büyür ve küçülür.

import java.util.ArrayList;

ArrayList<String> names = new ArrayList<>();
names.add("Ali");
names.add("Can");
names.add("Ece");
System.out.println(names + " " + names.size());
names.add(1, "Bora");          // 1. indekse ekle, gerisi kayar
System.out.println(names);
System.out.println(names.get(2));
names.set(0, "Arda");          // değiştir
System.out.println(names);
names.remove(3);               // indeksle sil
System.out.println(names);
names.remove("Bora");          // değerle sil
System.out.println(names);
System.out.println(names.contains("Can") + " " + names.indexOf("Can") + " " + names.indexOf("Zeynep"));
System.out.println(names.isEmpty());

[Ali, Can, Ece] 3
[Ali, Bora, Can, Ece]
Can
[Arda, Bora, Can, Ece]
[Arda, Bora, Can]
[Arda, Can]
true 1 -1
false

Geçersiz indeksle get çağırırsan çöker: IndexOutOfBoundsException: Index 1 out of bounds for length 1.

Wrapper sınıflar ve autoboxing

ArrayList sadece nesne tutar, primitive tutamaz. ArrayList<int> derlenmez (unexpected type). Her primitive’in bir sarmalayıcı (wrapper) sınıfı var: int → Integer, double → Double, char → Character, boolean → Boolean. Java aralarındaki dönüşümü kendisi yapar (autoboxing / unboxing):

ArrayList<Integer> nums = new ArrayList<>();
for (int i = 1; i <= 5; i++) nums.add(i * 10);     // int → Integer otomatik
System.out.println(nums);
nums.remove(1);                                    // İNDEKS 1
System.out.println(nums);
nums.remove(Integer.valueOf(40));                  // DEĞER 40
System.out.println(nums);
int first = nums.get(0);                           // Integer → int otomatik
System.out.println(first + 1);
for (int i = 0; i < nums.size(); i++) System.out.print(nums.get(i) + " ");

[10, 20, 30, 40, 50]
[10, 30, 40, 50]
[10, 30, 50]
11
10 30 50 

TUZAK · remove(1) mi remove(değer) mi? Integer listesinde remove(1) int argüman aldığı için indeks 1’i siler. 1 değerini silmek istiyorsan remove(Integer.valueOf(1)) yaz. String listesinde karışıklık yok: remove("Bora") değeri siler.

Döngüde silme

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(2, 4, 5, 6, 7));
for (int i = 0; i < list.size(); i++) {
    if (list.get(i) % 2 == 0) list.remove(i);      // baştan: HATALI
}
System.out.println(list);
ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(2, 4, 5, 6, 7));
for (int i = list2.size() - 1; i >= 0; i--) {
    if (list2.get(i) % 2 == 0) list2.remove(i);    // sondan: DOĞRU
}
System.out.println(list2);

[4, 5, 7]
[5, 7]

Baştan giderken 2 silinince 4 sıfırıncı indekse kaydı, ama i 1’e geçtiği için 4 hiç kontrol edilmedi. Sondan gidersen silinen elemanın sağı zaten kontrol edilmiş olur.

Sık yapılan hatalar

int[] a = {4, 7, 4, 2, 4};
System.out.println(linearSearch(a, 4) + " " + count(a, 4) + " " + linearSearch(a, 9));

int[] a = {1, 2, 3, 4, 5, 6};
for (int i = 0; i < a.length / 2; i++) {
    int t = a[i];
    a[i] = a[a.length - 1 - i];
    a[a.length - 1 - i] = t;
}
System.out.println(a[0] + " " + a[2] + " " + a[5]);

int[] a = {3, 6, 9};
int[] b = a;
int[] c = Arrays.copyOf(a, 3);
b[0] = 0;
c[1] = 0;
System.out.println(a[0] + " " + a[1]);

int[] a = {1, 2, 3, 4, 5};
for (int i = 0; i < a.length - 1; i++) a[i] = a[i + 1];
System.out.println(Arrays.toString(a));

ArrayList<String> list = new ArrayList<>();
list.add("x");
list.add("y");
list.add(0, "z");
list.add("w");
list.set(2, "v");
System.out.println(list + " " + list.size());

ArrayList<Integer> list = new ArrayList<>();
list.add(5); list.add(10); list.add(15); list.add(20);
list.remove(1);
list.remove(Integer.valueOf(20));
System.out.println(list);

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(3, 3, 3, 8));
for (int i = 0; i < list.size(); i++) {
    if (list.get(i) == 3) list.remove(i);
}
System.out.println(list);

ArrayList<String> list = new ArrayList<>(Arrays.asList("cat", "dog", "cow"));
int total = 0;
for (String s : list) if (s.startsWith("c")) total += s.length();
System.out.println(total + " " + list.indexOf("cow") + " " + list.contains("Dog"));

int[] a = {2, 8, 5};
System.out.println(isSorted(a));
Arrays.sort(a);
System.out.println(isSorted(a) + " " + a[1]);

int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
System.out.println((a == b) + " " + Arrays.equals(a, b));