Liste, Küme ve Kuyruk

Önceki ders dört aileyi tek bir bütün olarak ölçtü ve onbeş gözlemin kaçının arayüzden, kaçının seçilen sınıftan geldiğini saydı. Ama liste, küme ve kuyruk arasındaki seçimin kendisi hiç sorgulanmadı — üçü de birer koleksiyondur, üçü de aynı add çağrısını kabul eder. Bu ders o seçimi açar: aynı veri üçüne birden verildiğinde her biri neyi tutuyor, neyi sessizce bırakıyor? Yanıt, hiçbirinin ötekinden “daha iyi” olmadığını, üçünün de farklı bir soruya yanıt vermek üzere tasarlandığını gösterecek.

Veri Yapıları kursu liste, yığıt, kuyruk ve kümeyi soyut veri tipi olarak kurdu ve gerçekleştirim seçeneklerini karmaşıklıkla karşılaştırdı; o karşılaştırma burada tekrarlanmıyor. Buradaki soru büyüklük değil sözdür: bir liste seçmekle bir küme seçmek arasındaki fark, işlemlerin hızından önce, hangi bilginin saklanacağının taahhüdüdür.

Üç arayüzün adı bile bir vaat taşır: liste sıralı bir dizin çağrıştırır, küme matematikteki kümenin tekillik özelliğini, kuyruk fiziksel bir sıranın iki ucunu. Bu ders adların çağrıştırdığı sezgiyi ölçülebilir bir sayıya indiriyor: aynı girdi karşısında her arayüz kaç bilgiyi koruyor, kaçını feda ediyor — ve feda edilenin rastlantı mı, arayüzün kendi sözü mü olduğu ayrı ayrı sınanıyor.

Aynı İş Yükü, Üç Söz

• KO7 — İş yükü altı ögelik sabit bir listedir ve içinde iki yinelenen değer vardır (elma ve armut ikişer kez geçiyor); üç aile de aynı listeden, aynı sırayla doldurulur.
• KO8 — Ölçülen üç bilgi birbirinden bağımsızdır: yinelenen ögenin tutulup tutulmadığı, ekleme sırasının korunup korunmadığı, konuma (indekse) doğrudan erişilip erişilmediği. Bir ailenin kaç bilgiyi düşürdüğü bu üçünün toplamıdır.

Her aileden yalnız bir gerçekleştirim seçildi (ArrayList, HashSet, ArrayDeque) — önceki dersteki gibi üç gerçekleştirimi karşılaştırıp arayüz ile gerçekleştirimi ayırmak bu derste tekrarlanmıyor, çünkü soru burada başka: aynı gerçekleştirim seçiliyken üç arayüz birbirinden ne kadar ayrışıyor. HashSet bilinçli seçildi, çünkü onun gezinme sırası girdiyle örtüşmez; sırayı koruyan bir küme gerçekleştirimi seçilseydi bu bölümdeki ölçüm gizlenirdi.

// UcSoz.java — ayni is yukunu uc arayuze verip hangi bilginin dustugunu sayar
import java.util.*;

public class UcSoz {
    static final List<String> ISYUKU = List.of("elma", "armut", "elma", "kiraz", "armut", "erik");

    static void olc(String aile, Collection<String> kap) {
        boolean yinelemeTutuluyor = kap.size() == ISYUKU.size();
        boolean siraTutuluyor = new ArrayList<>(kap).equals(ISYUKU);
        boolean indeksErisimVar = kap instanceof List;
        int dusen = (yinelemeTutuluyor ? 0 : 1) + (siraTutuluyor ? 0 : 1) + (indeksErisimVar ? 0 : 1);
        System.out.printf("%-8s boyut=%-3d yineleme=%-6s sira=%-6s indeks=%-6s dusen=%d%n",
                aile, kap.size(), yinelemeTutuluyor, siraTutuluyor, indeksErisimVar, dusen);
    }

    public static void main(String[] args) {
        olc("liste", new ArrayList<>(ISYUKU));
        olc("kume", new HashSet<>(ISYUKU));
        olc("kuyruk", new ArrayDeque<>(ISYUKU));
    }
}

liste    boyut=6   yineleme=true   sira=true   indeks=true   dusen=0
kume     boyut=4   yineleme=false  sira=false  indeks=false  dusen=3
kuyruk   boyut=6   yineleme=true   sira=true   indeks=false  dusen=1

Üç satır üç ayrı taahhüt anlatıyor. ArrayList girdiden hiçbir şey düşürmüyor: altı öge de kalıyor, sırası korunuyor, herhangi bir konuma get ile doğrudan gidilebiliyor. HashSet girdinin üçünü birden düşürüyor: altı ögelik girdi dört ögeye iniyor (iki yinelenen atıldı), kalan dördün gezinme sırası girdiyle örtüşmüyor, konum erişimi hiç yok. ArrayDeque ise yalnızca birini düşürüyor: yineleneni de tutuyor, sırayı da koruyor, düşürdüğü tek şey konum erişimi.

Söz Karmaşıklıktan Değil Sözden Gelir

Kümenin düşürdüğü üç bilgi bir kusur değil, tekilliğin bedelidir: bir kap her ögeyi bir kez tutacağını vaat ediyorsa, ikinci elma girdiği anda ya reddedilir ya da birinciyle birleşir — ikisi de aynı sonucu, boyutun küçülmesini, doğurur. Kümenin sözü tektir: tekillik. Sıranın ne olacağını söylemez, çünkü tekilliği sağlamanın hangi iç yapıyla yapıldığı (karma tablosu, dengeli ağaç, ekleme sıralı bir bağlı liste) sıraya karışır ve arayüz bu iç yapıyı seçmez — önceki derste HashSet, LinkedHashSet ve TreeSet’in aynı soruya üç ayrı yanıt vermesi tam olarak bunun ölçümüydü.

Kümenin düşürdüğü sıra bilgisi, tekilliğin aksine, arayüzün zorunlu kıldığı bir kayıp değildir — bunu doğrudan ölçmek mümkün. Aynı iş yükü iki küme gerçekleştirimine verilip sonucun ilk-görülen sırayla (yinelenenler atıldıktan sonra kalan dört ögenin girdideki ilk geçiş sırası) örtüşüp örtüşmediğine bakılır.

// Tekil.java — kumenin dusurdugu sira arayuzun zorunlu kildigi bir sey mi
import java.util.*;

public class Tekil {
    static final List<String> ISYUKU = List.of("elma", "armut", "elma", "kiraz", "armut", "erik");
    static final List<String> ILKGORULEN = List.of("elma", "armut", "kiraz", "erik");

    static boolean siraIlkGorulenleAyniMi(Collection<String> kap) {
        return new ArrayList<>(kap).equals(ILKGORULEN);
    }

    public static void main(String[] args) {
        Set<String> hash = new HashSet<>(ISYUKU);
        Set<String> baglantili = new LinkedHashSet<>(ISYUKU);
        System.out.println("HashSet gezinme sirasi                  : " + hash);
        System.out.println("HashSet sira ilk-gorulenle ayni mi       : " + siraIlkGorulenleAyniMi(hash));
        System.out.println("LinkedHashSet gezinme sirasi             : " + baglantili);
        System.out.println("LinkedHashSet sira ilk-gorulenle ayni mi : " + siraIlkGorulenleAyniMi(baglantili));
    }
}

HashSet gezinme sirasi                  : [erik, elma, armut, kiraz]
HashSet sira ilk-gorulenle ayni mi       : false
LinkedHashSet gezinme sirasi             : [elma, armut, kiraz, erik]
LinkedHashSet sira ilk-gorulenle ayni mi : true

LinkedHashSet aynı tekillik sözünü tutarken sırayı da koruyor; HashSet korumuyor. Demek ki kümenin sırayı düşürmesi arayüzün dayattığı bir şey değil, seçilen sınıfın bir tercihidir — tıpkı önceki derste dört ailede ölçülen “gezinme sirasi ekleme sirasi mi” satırlarının gerceklestirim diye işaretlenmesi gibi. Arayüzün zorunlu kıldığı tek şey tekilliktir; sıra, konum erişimi gibi, sınıftan sınıfa değişebilen bir eklentidir.

Kuyruğun sözü de tektir ve kümeninkinden farklıdır: uç. Queue arayüzü offer, poll, peek üçlüsüyle “bir uçtan eklenir, bir uçtan çıkarılır ve o uç sabittir” der; hangi ögenin o uçta bekleyeceğini söylemez. ArrayDeque bu iş yükünde ekleme sırasını tesadüfen değil, kendi gerçekleştirim tercihiyle (uçtan uca bir dizi) koruyor; önceki derste aynı arayüzü konuşan PriorityQueue’nun aynı soruya false yanıtı vermesi, sıranın kuyruğun sözü olmadığını zaten gösterdi. Kuyruğun burada kaybettiği tek bilgi konum erişimidir, çünkü uç sözü veren bir kap ortadaki bir ögeye adres vermez — adres vermek listenin işidir.

Liste ise iki sözü birden taşır: sıra ve yineleme. Bir listeye eklenen her öge, eşiti daha önce eklenmiş olsa bile, kendi konumunda kalır; konumların hepsi get ile adreslenebilir. Bu iki söz kümenin ve kuyruğun tek tek verdiği sözlerin toplamı değildir — liste tekillik vaat etmez (iki elma da kalır), kuyruk gibi tek bir uçla sınırlı da değildir (herhangi bir konumdan okunabilir). Üç arayüz üç ayrı ihtiyaca karşılık gelir ve seçim, hangi bilginin tutulmasının gerektiğine bakılarak yapılır. Bu iki sözü aynı anda taşımanın bir bedeli de vardır, ama o bedel bu derste ölçülmüyor: ortadaki bir konuma ekleme ya da bir değerin var olup olmadığını arama, gerçekleştirime göre değişen bir maliyet taşır ve bu maliyet Veri Yapıları kursunda zaten sayılmıştı. Burada ölçülen yalnızca hangi bilginin kalıp kalmadığı; ne kadar sürede kaldığı ayrı bir eksendir.

Önceki dersteki isteğe bağlı işlem gözlemi burada bir kez daha karşımıza çıkıyor. Set.of ile üretilen sabit bir küme de, List.of ile üretilen sabit bir liste de ekleme girişimini aynı istisnayla reddediyordu; bu ders reddin biçimini değil, reddedilmeyen durumda hangi bilginin kaldığını ölçüyor. İki ölçüm birbirini tamamlıyor: biri “ekleme kabul edilirse ne olur” sorusuna, öteki “ekleme reddedilirse ne görürüz” sorusuna yanıt veriyor. İkisi de aynı sonuca çıkıyor: bir kabın davranışını anlamak için tek bir çağrının yazımı yetmiyor, hangi arayüzün hangi sözü verdiğini ayrı ayrı bilmek gerekiyor.

Sınırlayıcı Ölçüm: Aynı Nesne, İki Anlam

LinkedList çerçevenin tek çift kimlikli sınıfıdır: hem List hem Queue (Deque üzerinden) arayüzünü aynı anda gerçekleştirir. Yukarıdaki ölçümde kuyruk satırı ArrayDeque ile temsil edildi ve liste satırı ArrayList ile; ikisi de tek bir arayüzün sözünü taşıyan, saf sınıflardı. LinkedList saf değildir — aynı nesne, hangi referanstan çağrıldığına bağlı olarak, hem listenin hem kuyruğun sözünü taşıyabilir, ve bu iki söz aynı yöntem adını paylaştığında hangisinin geçerli olacağı çağrı yazımından görünmez. Nesneye Dayalı Java kursunda ölçülen kural burada aynen geçerlidir: bir çağrının hangi yönteme bağlanacağını çalışma zamanı tipi değil, bildirilen tip belirler.

• KO9 — Tek bir LinkedList nesnesi kurulur ve iki değişkene atanır: biri List, öteki Queue tipiyle bildirilmiştir. İkisi de aynı nesneyi gösterir; == ile doğrulanabilir ama ölçüm buna gerek duymaz, çünkü ikinci çağrının etkisi birincinin bıraktığı durumu değiştiriyor.

// Ikilem.java — ayni nesne, iki arayuz, iki ayri remove yontemi
import java.util.*;

public class Ikilem {
    public static void main(String[] args) {
        LinkedList<Integer> gercek = new LinkedList<>(List.of(10, 20, 30, 40));
        List<Integer> listeRef = gercek;
        Queue<Integer> kuyrukRef = gercek;

        System.out.println("baslangic                     : " + gercek);
        boolean silindiMi = kuyrukRef.remove(1);
        System.out.println("kuyruk referansindan remove(1) -> donen=" + silindiMi
                + "  sonuc=" + gercek);

        Integer silinenDeger = listeRef.remove(1);
        System.out.println("liste referansindan remove(1) -> donen=" + silinenDeger
                + "  sonuc=" + gercek);
    }
}

baslangic                     : [10, 20, 30, 40]
kuyruk referansindan remove(1) -> donen=false  sonuc=[10, 20, 30, 40]
liste referansindan remove(1) -> donen=20  sonuc=[10, 30, 40]

Yazılan satır ikisinde de birebir aynıdır: remove(1). Sonuç hiç aynı değildir. Queue arayüzünde remove(int) diye bir yöntem yoktur; derleyici 1 argümanını Integer’a kutulayıp Collection’dan gelen remove(Object)’e bağlar — kap içinde değeri 1 olan bir öge arar, bulamaz, false döndürür ve hiçbir şeyi değiştirmez. List arayüzünde ise remove(int) doğrudan tanımlıdır ve derleyici 1’i bir indeks olarak okur; ikinci konumdaki 20 silinir ve silinen değer geri döner. Aynı iki karakter — (1) — bir yerde “değeri bul ve sil”, ötekinde “ikinci konumu sil” anlamına geliyor.

Burada kırılan hiçbir garanti yoktur. İki arayüz de sözünü tam tutuyor: Queue bir ögeyi değerine göre silmeyi, List bir ögeyi konumuna göre silmeyi vaat etmişti ve ikisi de vaat ettiğini yaptı. Gerçekleştirim de suçsuzdur; nesne baştan sona aynı LinkedList nesnesidir ve içinde hiçbir şey değişmedi. Boşluk çağıranın yazdığı satırdadır: iki sözün aynı ada ve aynı yazıma düştüğü yerde hangisini istediğini söylemek çağıranın yükümlülüğüdür.

Bu yükümlülük kırıldığında sonuç, kursun ölçtüğü üç sınıftan sessiz olanıdır. “İkinci ögeyi sil” niyetiyle yazılan çağrı hiçbir istisna fırlatmaz, hiçbir şey yapmaz ve false döner; dönüş değeri okunmazsa kusur fark edilmeden geçer. LinkedList’in iki arayüzü birden konuşması burada bir kolaylık değil, bir tuzaktır — çünkü tek bir sınıf, iki sözü aynı çağrı yazımında çakıştırabilen ender yerlerden biridir.

• KO10 — Çağıranın söylemesi gereken şey yalnızca hangi arayüzden konuştuğu değil, argümanı hangi biçimde yazdığıdır. Aynı List üzerinden argüman açıkça Integer olarak kutulanırsa “değerle sil” sözü seçilir — ölçüm bunu tek bir referansla, ikinci bir değişken açmadan gösteriyor.

// Cozum.java — karari veren referansin tipi degil, argumanin tipi
import java.util.*;

public class Cozum {
    public static void main(String[] args) {
        LinkedList<Integer> gercek = new LinkedList<>(List.of(10, 20, 30, 40));
        List<Integer> listeRef = gercek;

        boolean silindiMi = listeRef.remove(Integer.valueOf(1));
        System.out.println("liste referansi, remove(Integer.valueOf(1)) -> donen="
                + silindiMi + "  sonuc=" + gercek);

        Integer silinenDeger = listeRef.remove(1);
        System.out.println("liste referansi, remove(1) (int)            -> donen="
                + silinenDeger + "  sonuc=" + gercek);
    }
}

liste referansi, remove(Integer.valueOf(1)) -> donen=false  sonuc=[10, 20, 30, 40]
liste referansi, remove(1) (int)            -> donen=20  sonuc=[10, 30, 40]

Değişken aynı listeRef, konuşulan arayüz aynı List<Integer>. Yalnızca argümanın yazımı değişti: birinci çağrıda Integer.valueOf(1) bir nesnedir ve “değerle sil” sözüne düşer — kap içinde 1 değerine eşit bir öge aranır, bulunamaz, false döner. İkinci çağrıda 1 bir int sabitidir ve “konumla sil” sözüne düşer. Demek ki yükümlülük arayüz seçimiyle bitmiyor: çağıran, argümanı yazarken de hangi sözü istediğini söylemiş oluyor ve bunu farkında olmadan söyleyebiliyor. Nesneye Dayalı Java kursu bu seçimin hangi tarafta yapıldığını ölçmüştü; burada ölçülen şey seçimin tarafı değil, seçimi çağırana bırakan kütüphanenin bunu hiçbir yerde sormamasıdır.

Bu tuzağın yalnız LinkedList üzerinde gösterilebilir olmasının nedeni onun iki arayüzü birden konuşmasıdır. ArrayList yalnızca List’i, ArrayDeque yalnızca Queue’yu konuşur; o sınıflarda remove(1) yazımının karşılığı tektir ve çakışma hiç doğmaz. LinkedList ise iki sözü aynı nesnede toplar; bu yüzden ölçüm iki ayrı sınıf değil, tek bir nesne üzerinde, yalnız iki değişkenle yapılabiliyor. “Konumla sil” yalnızca List tarafında vardır, Queue tarafında hiç yoktur — ayrım nesnenin davranışından değil, iki arayüzün verdiği sözlerin kümesinden doğuyor. Bu, kütüphanede birden çok arayüzü aynı anda gerçekleştiren her sınıf için geçerli genel bir kuraldır; LinkedList bunu tek bir çağrıyla göstermeye en yakın örnektir.

Özet

• Aynı altı ögelik girdi listeye, kümeye ve kuyruğa verildiğinde liste hiçbir bilgi düşürmüyor, küme üç bilgiyi (yineleme, sıra, konum erişimi) birden düşürüyor, kuyruk yalnızca konum erişimini düşürüyor.
• Üç arayüzün seçim ölçütü işlem hızı değil sözdür: liste sıra ve yineleme, küme tekillik, kuyruk uç vaat eder. Karmaşıklık karşılaştırması Veri Yapıları kursunda yapılmıştı ve burada tekrarlanmadı; burada ölçülen yalnızca hangi bilginin girdiden çıktığında hâlâ okunabilir olduğu.
• Kümenin düşürdüğü bilgi bir kusur değildir; tekillik sözünü tutmanın zorunlu bedelidir. Kuyruğun sırayı koruması ise arayüzün sözü değil, seçilen gerçekleştirimin tercihidir.
• LinkedList hem List hem Queue arayüzünü aynı anda taşır ve iki arayüzün remove sözü tek bir çağrı yazımında çakışır: birebir aynı yazılan remove(1) bir yerde konumla, bir yerde değerle siler.
• Çakışmada hiçbir garanti kırılmaz — iki arayüz de sözünü tutar, nesne değişmez. Kırılan şey çağıranın yükümlülüğüdür ve kırılma sessizdir: istisna düşmez, false döner ve dönüş değeri okunmazsa kusur fark edilmez.

Sonraki Adım

Bu derste liste, küme ve kuyruğun her biri, tuttuğu ögeye tek bir yoldan erişiyordu: konum, üyelik ya da uç. Bu üç erişim yolunun ortak noktası, kabın kendi kendine yetmesiydi — ögenin nerede olduğunu bulmak için kabın dışından hiçbir bilgi gerekmiyordu. Anahtar-değer eşleşmesi bu üçünden farklı bir söz veriyor: bir ögeye anahtarıyla erişilir ve arayüz o anahtarın karşılığını tekil tutacağını vaat eder. Ama anahtarın kendisinin ne olabileceğine dair sözün yarısı kütüphanede değil, çağıranın yazdığı sınıfta durur — kap yalnız anahtarı sorar, anahtarın kendi kendiyle tutarlı davranıp davranmayacağını denetlemez. Sıradaki ders bu yarıyı ölçer: bir anahtar sınıfı yanlış yazıldığında arama nereye düşer, hangi istisna fırlar ve fırlamıyorsa yerine ne olur.