Doğrusal Veri Kapları

Bu yazımızda, Veri Kapları Çerçevesi'nce (VKÇ) desteklenen doğrusal veri yapılarına değineceğiz. Bunu yaparken izleyeceğimiz yöntem, söz konusu veri yapılarının ortak özelliklerini anlattığımız giriş bölümünü takiben, anılan kategoriye giren kapları en geniş anlamda temsil eden genel liste veri yapısının desteklediği arayüzleri açıklamak ve kapların doğrusallaştırılmaları sonrasında ardışık erişimli görüntülerini sağlayarak dolaşılmasını olanaklı kılan gezicilere bakmak olacak. Yazımızın devamında ise, değişik doğrusal yapıların farklı gerçekleştirimlerine göz atarak işimizi bitireceğiz.

• Giriş
• Genel liste arayüzü
• Geziciler
• Genel liste gerçekleştirimleri
• Doğrudan erişimli listeler
• Kısıtlı listeler
• Bağlaçlı liste
• Değişken uzunluklu diziler: java.util.Vector🔎

Giriş

Doğrusal veri yapıları, eleman ekleme, silme ve güncelleme işlemlerinin hangi sırada uygulandığının bilinmesi durumunda, elemanların nasıl sıralanacağının bilindiği kaplardır. Örnek olarak, 1, 2 ve 3 sayılarının bir genel listenin, sırasıyla, başına, sonuna ve başına eklendikten sonra elde edilen kaptan ikinci elemanın silindiğini düşünün. Bu işlemlerin sonrasında listemiz, ne tür bir gerçekleştirim kullanılırsa kullanılsın, [3, 2] sıralamasıyla gezilecektir. Halbuki, küme veya eşlemlerde elde edilecek sıralama gerçekleştirime bağlı olarak oluşacak ve dolayısıyla kestirilemeyecektir.

Genel Liste Arayüzü: java.util.List

Doğrusal veri yapılarını en geniş anlamda temsil eden soyut veri yapısı genel listedir. VKÇ'deki List arayüzü ile karşılanan bu yapı, gerçekleştirim biçiminden bağımsız olarak bir genel listenin desteklemesi beklenen işlemleri tanımlar. Yani, ister dizi gibi doğrudan erişimli bir yapı kullanılarak gerçekleştirilsin isterse bağlaçlı bir yapı kullanılarak, tüm genel listeler List arayüzündeki işlemleri desteklemek zorundadır.

Collection'dan kalıtlanmak suretiyle List arayüzünde gözüken iletilerin başında, equals ve hashCode gelir. Bu iletilerin List arayüzüne konulmuş olmasını başta yadırgayabilirsiniz. Ne de olsa, tüm sınıfların [dolayısıyla List arayüzünü gerçekleştirecek sınıfların da] kalıtladığı Object sınıfında bu iletilere dair gerçekleştirimler sağlanmaktadır. Ancak, buradaki amaç gerçekleştirimciye bir hatırlatma yaparak onu uyarmaktır; tanımlayıcıları List arayüzünü gerçekleştirmek isteyenlere şunu demektedirler:

Tutacakları karşılaştırmak yoluyla işini gören Object sınıfındaki equals metodu, muhtemelen senin işine gelmeyecektir. Ne de olsa, bu metot eşitlik denetimi yerine aynılık denetimi yapar. Bunun bir sonucu olarak, iki listenin eşit olması ancak ve ancak aynı olmaları durumunda mümkün olacaktır; eşit içeriğe sahip iki farklı liste eşitsiz ilan edilecektir. Dolayısıyla, sen iyisi mi, equals iletisini gerçekleştirmeyi bir daha düşün. Ha bu arada; hashCode iletisini de gözden geçirmeyi unutma. Malum, birbirine eşit farklı nesnelerin kıyım değerleri de eşit olmalıdır. Bu koşulu sağlayabilmenin yolu ise hashCode ile equals'ı birlikte ele almaktan geçer. Çünkü, Object sınıfındaki equals metodunu ezip de hashCode metodunu ezmezsen, eşit kapların farklı kıyım değerleri üretmesi durumu ortadan kalkmaz.

List arayüzündeki iletilerin çoğu VKÇ'yi daha önceden kullanmış olanlara tanıdık gelecektir. Bunun başlıca sebebi, VKÇ'de desteklenen kapların bir standardizasyon çabası kapsamında birlikte ele alınmış olmasıdır.¹ Doğal olarak, aynı işlemler için olabildiğince aynı ileti adları seçilmeye çalışılmış ve ilintili işlemler kategorizasyon amacıyla aynı arayüze konulmuştur. Örneğin, ne tür bir kap olursa olsun, isEmpty hedef nesnenin boş olup olmadığını denetlerken size kaç eleman içerdiğini döndürür. Benzer bir şekilde, ilişkisel olmayan veri yapıları (genel liste, kuyruk, yığıt, çift-uçlu kuyruk, küme) Collection arayüzünde belirlenen işlevselliği paylaşırlar. Mesela, ister Vector olsun isterse TreeSet, bir nesnenin hedef kapta olup olmadığı contains iletisi ile sorgulanabilir; hedef kabın sonuna add ile eleman eklenirken, hedef kaptan verilen bir nesneye eşit ilk elemanın silinmesi remove ile sağlanır. Bunlara paralel olarak, containsAll, addAll ve removeAll/retainAll iletileri, sırasıyla, sorgulama, sona ekleme ve silme işlemlerini kendilerine geçirilen kapta var olan tüm nesneleri dikkate alarak yerine getirirler. clear iletisi ise, hedef kabın tüm elemenlarını siler.

List arayüzünün Collection'dan kalıtladığı diğer iletiler hedef kabın dizi şeklindeki görüntüsünü döndüren toArray iletileridir. Kap içeriğini baştan sona dolaşılma sıralarını koruyacak şekilde diziye kopyalayan iletilerden argümansız olanı, sonucu Object dizisi olarak döndürürken, kopyalamanın yapılacağı dizinin bileşen türünü argümanındaki dizinin bileşen türünü belirleyen tür argümanıyla alan ikinci uyarlama, sonucu dönüş değerinin yanısıra, yeterli yere sahip olması durumunda, argümanda geçirilen dizinin içinde de döndürür. Argümandaki dizinin yeterli yere sahip olması halinde, dönüş değeri için ikinci bir dizi yaratılmayacak, aynı dizi nesnesi paylaştırılacaktır.

Üst arayüzlerden kalıtlanmayıp List arayüzünün eklediği doğrusal kaplara özel tüm iletiler, kendilerine sağlanan indis değerlerini kullanarak ya da sonuçlarında indis değeri döndürerek işlerini görürler. Bunlardan get/set çifti, dizi erişim işleci ([]) görevini görür: get argümanında sağlanan indisteki elemanı döndürürken, set belirtilen konumdaki elemanı ikinci argümanındaki yeni değerle güncelledikten sonra söz konusu konumdaki eski değeri döndürür. get'in tersi olarak da görülebilecek indexOf ve lastIndexOf iletileri ise, contains iletisinin boolean yerine sorgulanan nesnenin, sırasıyla, kap içindeki ilk ve son geçiş yerlerini döndüren uyarlamaları olarak düşünülebilir. Argümandaki nesnenin kap içinde bulunmaması halinde her iki ileti de -1 döndürecektir.

List arayüzüne özel add, addAll ve remove iletilerinin yukarıda anılan adaşlarından şöyle bir farkı vardır: ekleme kap sonu yerine sağlanan ekstra argümanla belirtilen konuma yapılırken, silme nesne-eleman eşitliği denetlenerek bulunan konumu değil argümandaki indisin gösterdiği konumu etkiler.

Değineceğimiz son ileti, ilk başta göründüğünden çok daha hünerli olan subList. Hedef kabın argümanlar ile sınırlanan [kapalı-açık] dilimini bir List görüntüsü≝ olarak döndüren bu ileti, dilim işlemlerinin gerçekleştirilmesini kolaylaştırır. İstersek, bir nesnenin kabımızın belirli bir diliminde var olup olmadığını sorgulayabiliriz; istersek, aşağıda olduğu gibi, kabımızın bir bölümünü silebiliriz.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
...
  List<Integer> ls = new LinkedList<>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
  ls.subList(3, 7).clear(); // ls → [0, 1, 2, 7, 8, 9]

Geziciler: java.util.Iterator ve java.util.ListIterator

List arayüzünün Collection vasıtasıyla Iterable'dan kalıtladığı düşünüldüğünde, liste elemanlarının, tıpkı diziler gibi, gezici for döngüsü ile dolaşılabileceği görülecektir. Yani, gezici nesne yaratıp başa konuşlandıktan sonra hasNext ve next iletilerinden yararlanarak dolaşmaktansa, listemizi aşağıdaki gibi dolaşmak da mümkündür ve kodun anlaşılabilirliğini artırmak adına bu yöntem yeğlenmelidir.

import java.util.List;
import java.util.ArrayList;
...
  List<ElmTürü> ls = new ArrayList<>();
  ... // ls'yi doldur]
  for (ElmTürü elm : ls) { ... }

Ön-derleme sonrasında yukarıdaki for döngüsü J2SE 5.0 öncesinde programcının yazmak zorunda kaldığı şu şablon koda çevrilecektir. Dolayısıyla, gezici for döngüsünün, dolaşılabilir kapların kullanımında yararlanılan sözdizimsel bir kolaylık olduğunu söyleyebiliriz.

import java.util.Iterator;
...
  for (Iterator<ElmTürü> gzc = ls.iterator(); gzc.hasNext();) {
    ElmTürü elm = gzc.next();
    ...
  }

Gezicinin soyutlanarak doğrudan kullanımının önüne geçilmesi nedeniyle, gezici for döngüsünün gövdesinde kap içeriğinin güncellenmesi olanaksızdır; dolaşma esnasında kabın güncellenebilmesi için gezicinin bizzat programcı tarafından yaratılması gerekir. Bu durumda, geziciye gönderilecek bir remove iletisi, next ile döndürülen son elemanı silecektir.

...
  for (Iterator<ElmTürü> gzc = ls.iterator(); gzc.hasNext();) {
    ElmTürü elm = gzc.next();
    if (...) gzc.remove();
    ...
  }

iterator'ın döndürdüğü gezicinin anılan üç iletiye sınırlı olması bazen kısıtlayıcı olabilir. Doğru ya, ardışık elemanların ilişkilerini görebilmek için kabımız içinde ileriye doğru olduğu gibi geriye doğru da dolaşmak isteyebiliriz; gezme sırasında elemanları silmek isteyebileceğimiz gibi güncellemek, öncesine veya sonrasına yeni bir değer eklemek isteyebiliriz. Bu takdirde, List tutacağı aracılığıyla gönderilebilecek listIterator iletisinin kullanımı düşünülebilir. Hedef kabın ListIterator arayüzü tutacağı ile kullandırılan bir görüntüsünü döndüren bu ileti, geziciyi kabın başına veya argümanla belirtilen konuma konuşlandırabilir. İlkleme sonrasında, gezicinin sağladığı görüntü kullanılarak altyapıdaki kap ileri/geri yönde dolaşılabilir, uygun görülen yerlere yeni eleman eklenebildiği gibi, var olan elemanlar değiştirilebilir veya silinebilir. Bu noktada, yıkıcı (güncelleyici) işlemlerin etkisini altyapıdaki kap üzerinde göstereceği unutulmamalıdır. Örneğin, aşağıdaki kod parçasında gzc ls ile gösterilen kabın ortasına konuşlanmakta ve başa doğru dolaşırken değeri 3 olan elemanları 33 olacak şekilde güncellemektedir.

import java.util.ListIterator;
...
  List<Integer> ls = new ArrayList<>();
  // ls'yi doldur...
  int orta = ls.size / 2;
  for (ListIterator<Integer> gzc = ls.listIterator(orta); gzc.hasPrevious();) {
    int elm = gzc.previous(); // Derleyici Integer→int dönüşümünü yapıyor
    if (elm == 3) gzc.set(33);
    ...
  }

Kabın paylaşılması nedeniyle, yapılan değişikliklerin hem liste hem de gezici tutacağı ile görüleceği unutulmamalıdır. Bu noktanın gözden kaçırılması, çok-izlekli programlarda—mesela, kabın bir izlekte liste tutacağı yoluyla bir diğerinde ise gezici tutacağıyla değiştirildiği durumlarda—soruna yol açabilir.

Iterator arayüzünden kalıtlayan ListIterator aşağıdaki tabloda verilen iletileri içerir. Eklemenin yapılacağı nokta aynı kapıya çıkan iki şekilde tanımlanabilir: i) hasNext'in false döndürmesi durumunda listenin sonuna, aksi takdirde next ile döndürülecek elemanın öncesine, ii) hasPrevious'ın false döndürmesi durumunda listenin başına, aksi takdirde previous ile döndürülecek elemanın sonrasına. Ayrıca, remove ve set iletilerinin en son okunmuş olanın dışında bir elemanı etkilemeyeceği ve bu iletilerin add veya bir diğer remove iletisi sonrasında bir başka okuma yapılmaksızın kullanılamayacağı unutulmamalıdır. Aksi takdirde, gönderi IllegalStateException ayrıksı durumunun firlatılmasıyla sona erecektir.

ListIterator arayüzü

İleti	İşlev
hasNext	Liste sonu sorgulama
next	Bir sonraki eleman
remove	En son okunan elemanı silme
nextIndex	Bir sonraki elemanın indisi
hasPrevious	Liste başı sorgulama
previous	Bir önceki eleman
previousIndex	Bir önceki elemanın indisi
add	Ekleme
set	En son okunan elemanı güncelleme

Gezici kullanımı sırasında şu husus akılda tutulmalıdır: geziciler dolaştırdıkları listenin değişebilirlik, çok/tek-izleklilik ve tür güvenlilik gibi özelliklerini korur. Buna göre, aşağıdaki kod parçasında, lsGzc vasıtasıyla değişikliğe izin verilirken, sabitLsGzc'nin aynı kabı değiştirmek amacıyla kullanılması UnsupportedOperationException ayrıksı durumuna neden olacaktır.

import java.util.Collections;
...
  List<Integer> ls = new ArrayList<>();
  // ls'yi doldur...
  List<Integer> sabitLs = Collections.unmodifiableList(ls);
  ...
  ListIterator<Integer> lsGzc = ls.listIterator();
  ListIterator<Integer> sabitLsGzc = sabitLs.listIterator();

java.util.Enumeration arayüzüne değinerek geziciler bahsini kapatalım. İşlevsel olarak Iterator arayüzünün silme özelliği barındırmayan uyarlaması olarak düşünülebilecek bu arayüzün kullanımından kaçınılmalıdır. Daha önceden tanımlanmış olup ıslah edilerek VKÇ'ye katılan Hashtable ve Vector gibi kapların bu arayüzün tutacağı ile görüntü döndüren iletileri yerine, eşdeğer bir diğer iletinin kullanılması yerinde olacaktır. Örneğin, Vector nesnelerine elements yerine iterator iletisi gönderilmelidir. Bu, VKÇ ile birlikte tanımlanan Vector benzeri (ArrayList gibi) kapların elements'i desteklemeyip iterator'ı desteklemesi nedeniyle kodun yeniden kullanılabilirliği adına daha doğru olacaktır.

Genel Liste Gerçekleştirimleri

Altyapıda yararlanılan kabın erişim özelliğine bağlı olarak List arayüzünü gerçekleştiren sınıflar, doğrudan erişimli ve ardışık erişimli olmak üzere ikiye ayrılırlar. Bu ayrım, kimi iletilerin performanslarını etkilemesi ve desteklenebilecek ekstra iletiler nedeniyle, söz konusu kapların kullanıldıkları programların çalışma hızını ve anlaşılabilirliğini etkileyecektir; hangi somut sınıfın kullanılacağına dair yapılan seçimde bu nokta göz önünde bulundurulmalıdır. Kodun yeniden kullanılabilirliğini artırmak ve yapılacak muhtemel değişikliklerin etkisini en aza indirmek adına, tutacak türü olarak arayüz ve soyut sınıf adları kullanmaya çalışılmalı, somut sınıfların kullanımı nesne yaratma noktalarına sınırlı tutulmalıdır. Tercih edilen somut sınıfın kesinleşmesinden sonra bile arayüzlerde listelenen iletiler sınıfa özel eşdeğer iletilere yeğlenmeli, sınıfa özel iletiler ancak ek getirileri olmaları durumunda seçilmelidir. Örneğin, Vector'de karar kılınsa dahi List arayüzündeki get kullanılmalıdır, Vector sınıfına özel elementAt değil. Buna karşılık, subList ve tek argümanlı indexOf iletisinin birlikte kullanımı yerine iki argümanlı indexOf iletisinin kullanımı daha anlaşılabilir olması ve [marjinal] hız farkı nedeniyle tercih edilebilir.

adlar.indexOf("Ali", 5); // adlar.sublist(5, adlar.size()).indexOf("Ali") 

Java VKÇ, gerçekleştirimcinin işini kolaylaştırmak amacıyla somut sınıfların üzerine inşa edileceği soyut sınıflar sağlar. Doğrudan erişimli bir altyapı üzerine oturtulan bir genel liste için bu soyut sınıf AbstractList iken, ardışık erişimli altyapı kullanarak aynı işe soyunanların doğru adresi, AbstractList'ten kalıtlayan AbstractSequentialList'tir. İskelet görevi gören bu sınıflar, yararlanılacak altyapının ayrıntılarına dair varsayımlarda bulunulamaması nedeniyle, kimi iletilere karşılık gerçekleştirim sağlamazken kimi iletiler için genel [ve yavaş] gerçekleştirimler sağlar. Dolayısıyla, VKÇ'ye yeni bir kap gerçekleştirimi eklemek isteyenler, soyut sınıflardan uygun olanından kalıtlayarak iskeleti ete büründürmelidir.

VKÇ'ye yeni bir kap gerçekleştirimi eklemek isteyenlerin sabit içeriklilik ve değişken uzunlukluluk özelliklerini destekleyip desteklememelerine bağlı olarak sorumlulukları da değişir. Örneğin, tüm doğrudan erişimli listeler get ve size iletilerine karşılık gelen metotları sağlamak zorundayken, listenin değişken içerikli olmasının istenmesi durumunda, AbstractList'te UnsupportedOperationException ayrıksı durumu fırlatacak şekilde gerçekleştirilen set ezilmelidir. Benzer şekilde, listenin değişken uzunluklu olması isteniyorsa, iki argümanlı add ve int argüman alan remove metotlarının da ezilmesi gerekir. Ardışık erişimli listelerin gerçekleştiriminde de aynı ayrım geçerlidir: AbstractSequentialList'ten kalıtlayıp size ve listIterator iletilerini gerçekleştirmesi beklenen geliştiriciler, listIterator'ın döndürdüğü gezicinin alacağı iletileri gerçekleştirirken sabit içeriklilik ve değişken uzunlukluluk özelliklerini hesaba katmalıdırlar. Ardışık erişimli listelerden sabit içerikli [ve dolayısıyla sabit uzunluklu] olanlar, ListIterator arayüzünde bulunan next, hasNext, nextIndex, previous, hasPrevious ve previousIndex için gerçekleştirim sağlamak zorundayken, diğer iletilerin gerçekleştiriminde UnsupportedOperationException döndürmelidirler. Buna karşılık, değişken içerikli, sabit uzunluklu listeler, anılan arayüzün add adlı iletisini de gerçekleştirmek durumundadır. Son olarak, değişken uzunluklu listeler, arayüzde bulunan tüm iletileri gerçekleştirmelidir.

Doğrudan Erişimli Listeler: java.util.ArrayList ve java.util.Vector

VKÇ'de doğrudan erişimli genel liste gerçekleştirimi sağlayan iki sınıf vardır: ArrayList ve Vector🔎. Diziden yararlanarak işini gören bu sınıflar arasında işlevsellik ve performans açısından pek fark yoktur. Ancak, yine de şu noktaların akılda tutulmasında yarar olacaktır:

• Java'nın ilk uyarlamasından bu yana var olan Vector, diğer J2SE 1.2 öncesi kaplar gibi, çok-izlekli iken ArrayList tek-izleklidir. Dolayısıyla, ArrayList türlü kapların çok-izlekli bir programda kullanılması durumunda, farklı izleklerden eşzamanlı erişimin sebep olabileceği tutarsızlıkları önlemek adına bazı kod bölgelerinin synchronized bloğu içine alınarak çok-izlekli hale getirilmeleri gerekir. Buna karşılık, kamuya açık tüm metotları synchronized olan Vector sınıfının tek-izlekli veya erişim serileştirme gereksiniminin düşük olduğu çok-izlekli programlarda kullanılması, çalışma hızının gereksiz yere yavaşlamasına neden olacaktır. Bu gibi durumlarda, ArrayList türlü bir kabın kullanımı ve gerekli noktalarda Collections sınıfındaki synchronizedList metodu ile döndürülen görüntü üzerinde işlem yapılması da bir çözüm olarak hesaba katılmalıdır.²
• Her iki sınıf da, eleman sayısının artmasını gerektirecek bir işlem sırasında sığanın otomatik olarak büyümesini sağlar. Ne var ki, Vector sınıfında ilişkin kabın yaratılması esnasında sağlanacak bir argüman ile sığa artımına müdahale edilebilirken, ArrayList sınıfında böyle bir olanak yoktur.

Yukarıda da söylediğimiz gibi, her iki sınıf da benzer performansa sahiptir. get, set, size, isEmpty, iterator ve listIterator iletileri sabit zamanlı performans sergilerler. Ayrıca, kabın sığa artımına ihtiyaç duyduğu durumlarda yaşanan düşüşe karşın, kap sonuna eleman ekleyen add iletisi de ortalamada sabit zamanlı bir performans gösterir. Buna karşılık, diğer iletilerin arama temelli olanları, kap içeriğini dolaşmak zorunluluğu nedeniyle doğrusal veya daha pahalı bir performans sergileyecektir.

Kısıtlı Listeler: java.util.PriorityQueue ve java.util.ArrayDeque

C'den başka programlama dili bilmeyenlerin yaydığı bir efsanedir: liste denince akla bağlaçlar, bağlaç denince ise göstericiler gelir. Eğer bu bedbahtlardansanız, olasıdır ki yazımızın bağlaçlı listelerle başlamamış olması sizi şaşırtmıştır. Size kötü bir haber daha verelim, genel liste arayüzünün bir altkümesine sınırlı işlevsellik sunan kısıtlı listelere değinmeden bağlaçlı listelere geçmeyeceğiz.

VKÇ'de desteklenen ve tür sıradüzeni aşağıda verilen kısıtlı liste çeşitlerini anımsayarak başlayalım. Üç temel işlemin de üst olarak nitelenen aynı liste ucunu etkilediği bir kısıtlı liste olan yığıt (İng., stack), herhangi bir noktada çıkarılacak (veya sorgulanılacak) ilk elemanın en son eklenen eleman olması nedeniyle son giren ilk çıkar listesi olarak da adlandırılır. Bir diğer kısıtlı liste, gerçek yaşamdaki aynı adlı kavramı temsil eden ve uygarlıktan nasibini almış herkesin takdir edeceği nedenlerden ötürü ilk giren ilk çıkar listesi olarak adlandırılan kuyruktur (İng., queue). Kuyruğun elemanları arasında bir sıralamanın istenmesi halinde—yani, kuyruğun belirli bir ölçüte göre oluşturulması istendiğinde—ekleme işlemi kuyruğun sonu yerine herhangi bir yerine yapılabilir. Böylesine kuyruklara, öncelikli kuyruk (İng., priority queue) denir. Son olarak, temel işlemlerin aynı listenin her iki ucuna da uygulanabildiği kısıtlı listelere çift-uçlu kuyruk adı verilir.

Yukarıdaki şeklin incelenmesi kuyruk ve yığıt yapılarının VKÇ tarafından desteklenmediği kanısını yaratabilir. Java uzmanı olanlarınız ise, aslında bu desteğin var olduğunu, sorunun şeklin eksik olmasında yattığını iddia edeceklerdir. Her iki görüşte de haklılık payı olduğunu, duruma daha sonra açıklık getirileceğini söyleyelim ve Queue arayüzünün açıklaması ile devam edelim. Collection'dan kalıtlayan bu arayüz, aynı işlemin istisnai durumlarda iki farklı biçimde davranması nedeniyle, aşağıdaki tabloda listelenen altı iletiyi içerir. Sabit uzunluklu, dolu bir kuyruğa add ile ekleme yapılması IllegalStateException ayrıksı durumuna neden olurken, aynı kuyruğa offer ile eleman eklenmeye çalışılması, C fonksiyonlarını andırırcasına, null değerinin döndürülmesine neden olacaktır. Sorgulama ve çıkarma işlemleri de boş bir kuyruğa uygulanmaları halinde benzer bir davranış sergileyecektir.

Kuyruk: İlk giren ilk çıkar listesi

İşlem	İleti (Queue)	Başarısızlıkta döndürülen değer	Denk ileti (Deque)
Ekleme	add	IllegalStateException	addLast
	offer	false	offerLast
Sorgulama	element	NoSuchElementException	getFirst
	peek	null	peekFirst
Çıkarma	remove	NoSuchElementException	removeFirst
	poll	null	pollFirst

Queue arayüzüne dayalı kuyruk gerçekleştirimini kolaylaştırmak amacıyla sağlanan AbstractQueue'dan kalıtlayan sınıflara baktığımızda, değişken uzunluklu öncelikli kuyruk yapısını ikili yığın (İng., binary heap) kullanarak gerçekleştiren PriorityQueue sınıfını görürüz. Dizi üzerine ikili ağaç benzeri bir yapı oturtarak işini gören bu gerçekleştirim stratejisi sayesinde, temel işlemlerden sorgulama sabit zamanda sonuç verirken, ekleme ve çıkarma logaritmik zaman almaktadır. Öncelikli kuyruğun eleman sayısını öğrenme, boşluk yüklemi ve gezici yaratma da sabit zamanda mümkün olmaktadır. Buna karşılık, geri kalan iletiler doğrusal zaman gerektirmektedir.

PriorityQueue sınıfının yapıcılarına bakıldığında iki nokta dikkat çeker. Öncelikle, değişken uzunluklu olması hasebiyle taşmaması için büyütülen kuyruklar, istenildiği takdirde yaratıldıkları noktada belirli bir ilk sığaya sahip olacak şekilde yaratılabilir. Kuyruğun eleman eklenerek büyümesi sırasında altyapıdaki dizinin büyütülmesinden kaynaklanacak performans kaybını azaltacak bu parametre, sabit uzunluklu kuyruklarda yer ve zaman kayıplarını sıfıra indirecektir. Dikkatimizi çeken ikinci husus, iki argümanlı yapıcıdaki ikinci argümanın Comparator türlü olmasının hatırlattığı ayrıntıdır: öncelikli kuyruk içine konulmak istenecek nesnelerin, hangi sınıftan olurlarsa olsunlar, karşılaştırılabilir olmaları gerekir. Durup düşünüldüğünde bu önkoşulun çok doğal olduğu görülecektir: karşılaştırılamayan nesneler sıraya dizilemezler!³ Dolayısıyla, nesnelerin Comparable arayüzünü gerçekleştiren bir sınıfa ait olması veya nesneleri karşılaştırmayı bilen bir karşılaştırıcı nesnenin fazladan sağlanması zorunludur.

Gelelim ortalıkta gözükmeyen yığıt ve kuyruk gerçekleştirimlerinin nerede olduklarına. Bunun için, çift-uçlu kuyruk yapısının tanımlandığı Deque arayüzünü gerçekleştiren ArrayDeque sınıfına bakmak yetecektir. Çünkü, VKÇ'de bir kabın yığıt veya kuyruk gibi davranması, bu yapılara uyumlu iletilerin ArrayDeque nesnelerine gönderilmesiyle sağlanır.⁴

import java.util.Deque;
import java.util.Queue;
import java.util.ArrayDeque;
...
  Deque<Integer> yığıt = new ArrayDeque<>();
  Queue<Integer> kuyruk = new ArrayDeque<>();

Örneğimizdeki asimetrik kullanım dikkatinizi çekmiştir: tutacak türü olarak, kuyruk için Queue arayüzü kullanılırken, yığıt için çok-uçlu kuyruğa dair Deque arayüzü kullanılmaktadır. Dolayısıyla, kuyruk adlı kap kuyruklara özel iletilerle kullanılacakken, yığıt'ın kullanımında seçtiğimiz tanımlayıcı adı aldatıcı olacaktır. Zira, söz konusu tutacak Deque arayüzünde tanımlı olan ve aşağıdaki tabloda sağlanan yığıt iletilerinin yanısıra diğer tüm iletilere de izin verecektir.

Yığıt: Son giren ilk çıkar listesi

İşlem	İleti	Başarısızlıkta döndürülen değer	Denk ileti
Ekleme	push	IllegalStateException	addFirst
	—	false	offerFirst
Sorgulama	peek	null	peekFirst
	—	NoSuchElementException	getFirst
Çıkarma	pop	NoSuchElementException	removeFirst
	—	null	pollFirst

Bu noktada, bazılarınız, Java'nın ilk uyarlamasından bu yana var olan Stack sınıfı nerelerde, diye soruyor olabilir. Hemen yanıtlayalım: eskiden olduğu yerde, emrinize amade sizi bekliyor. Ama, sakın ola ki, sırf adı yığıt sözcüğünün İngilizce karşılığı olduğu için bu sınıfı kullanmanın daha iyi bir fikir olduğunu düşünmeyin. Çünkü, geliştiricilerin, muhtemelen işi aceleye getirmeleri nedeniyle, Vector sınıfından kalıtlayarak gerçekleştirdiği bu sınıf, yığıt kavramıyla ilgili ilgisiz çok sayıda iletiyi desteklemektedir. Mesela, aşağıdaki kod parçasında yaratılan kap, yığıta dair iletilerin yanısıra, Vector sınıfının desteklediği diğer iletileri de, doğrudan erişimliler dahil olmak üzere, itiraz etmeden kabul eder.

import java.util.Stack;
...
  Stack<Integer> yığıt = new Stack<>();
  // List arayüzündeki tüm iletiler yığıt'a gönderilebilir!

Geldiğimiz noktada, üç farklı kısıtlı liste için sağladığı destek ve söz konusu yapıların farklı terminoloji kullanması nedeniyle, Deque arayüzünü (ve gerçekleştirimcisi ArrayDeque sınıfını) anlamakta zorluk çekiyor olabilirsiniz; bazı işlemlerin istisnai durumlarda iki değişik şekilde tepki vermesi işi daha da kötüleştirebilir. Ancak ürkmeyin, aşağıdaki tablonun yorumu sizi işinizin düşündüğünüz kadar zor olmadığına inandıracaktır.

Çift-uçlu kuyruktan yararlanarak kuyruk ve yığıt

			Denk iletiler
			C tarzı dönüş	Ayrıksı durum
Kuyruk	Ekleme	add	—	addLast
		offer	offerLast	—
	Sorgulama	element	—	getFirst
		peek	peekFirst	—
	Çıkarma	remove	—	removeFirst
		poll	pollFirst	—
Yığıt	Ekleme	push	offerFirst	addFirst
	Sorgulama	peek	peekFirst	getFirst
	Çıkarma	pop	pollFirst	removeFirst

Çift-uçlu kuyruklarda üç temel işlemin—ekleme, çıkarma (silme) ve sorgulama (göz atma)—kabın her iki ucuna da uygulanabileceğini hatırlatarak başlayalım. Söz konusu altı işlemin istisnai durumlarda farklı tepki veren iki ileti ile karşılandığı da düşünüldüğünde, yedi tanesi tablomuzun sağ kısmında yer alan on iki iletinin gizemi çözülür. Bunlara, temel işlemlerin yığıt ve kuyruk terminolojisindeki karşılıkları olan üçüncü sütunda listelenen dokuz iletiyi de eklersek, toplamda yirmi bir iletiyi buluruz. Collection'dan gelenler ve Deque'in geri kalan üç iletisi (descendingIterator, removeFirstOccurrence ve removeLastOccurrence) ile beraber düşünüldüğünde, bu sayı başta korkutucu gelebilir. Ancak, çift-uçlu kuyruğu ne şekilde kullanacağınıza karar vermenizle birlikte yirmi bir ileti aniden yığıt için üçe, kuyruk için üç veya altıya, çift-uçlu kuyruk içinse altı veya on ikiye düşecektir.

ArrayDeque dairesel arabellek (İng., circular buffer) şeklinde kullanılan bir dizi ile gerçekleştirim sağlar. Bu sayede, temel işlemlerin her iki uca uygulanmasına karşılık gelen tüm iletiler sabit zamanda işlerini bitirirler. Aynı nedenden ötürü, temel işlemlerin toptan uygulanmaları da eleman başına sabit bir maliyet sergileyecektir. Buna karşılık, kabın taranmasını gerektiren arama iletileri doğrusal zamanlı performansa sahiptirler. Son olarak, altyapıda kullanılan dizinin yetersiz sığaya sahip olduğunun görülmesi dizinin genişletilmesine neden olacağı için, ekleme iletilerinin nadiren de olsa bazen reklam edilenden düşük bir performans sergileyebileceği unutulmamalıdır. Bu duruma düşmemek için ArrayDeque nesnesini muhtemel kullanıma uygun bir sığa ile yaratmak yardımcı olacaktır.

Bağlaçlı Liste: java.util.LinkedList

VKÇ'nin genel liste gerçekleştirimi olarak sunduğu ikinci seçenek, List ve Deque arayüzlerini ardışık erişimli bir yapı kullanarak gerçekleştiren LinkedList sınıfıdır. Baş ve son düğümlerin tutacaklarını barındıran çift bağlaçlı bir yapıya sahip bu sınıfta ekleme ve çıkarma, liste içindeki bağlaçların güncellenmesiyle tamamlanır. Bunun doğal bir sonucu olarak, herhangi bir elemana erişmenin tek yolu, get/set gibi iletiler kullanılıyor olsa bile, ardışık erişimdir; istenen bir elemana erişilmesi için, söz konusu eleman öncesindeki/sonrasındaki tüm elemanların ziyaret edilmesi zorunludur. Dolayısıyla, doğrudan erişim üzerine kurulu ikili arama gibi algoritmalarda bu sınıf yerine ArrayList veya Vector gibi bir sınıfın kullanılması daha mantıklı olacaktır. Buna karşılık, araya eklemenin sık yapıldığı ve ardışık erişime mecbur olunan durumlarda—mesela, ekleme sıralaması (İng., insertion sort) algoritmasının gerçekleştiriminde—seçimin LinkedList'ten yana olması gerekir. Çünkü, bağlaçlı bir yapı kullanılarak gerçekleştirilen bir kabın ortasına yapılan eklemeler/çıkarmalar doğrudan erişimli kapların neden olduğu gibi kaydırmanın getireceği olumsuzluktan etkilenmez. Son olarak, kabın iki ucuna erişimin sabit maliyetli olması, size yığıt ve kuyruk gibi kısıtlı listeler için LinkedList'in çekici bir seçenek olduğunu düşündürebilir.

...
import java.util.LinkedList;
...
  Deque<Integer> yığıt = new Linked<>();
  Queue<Integer> kuyruk = new LinkedList<>();

Yukarıda sağlanan çözümün ArrayDeque kullanılarak sağlanan çözümle daha sağlıklı bir şekilde karşılaştırılabilmesi için, ArrayDeque'in altyapıda kullanılan dizinin boş konumları için maliyet ödetmesine karşılık, LinkedList'in her bir eleman için fazladan iki bağlaç tutmak zorunda olduğu unutulmamalıdır. ArrayDeque nesnesinin duruma uygun bir ilk sığaya sahip yaratılması imkanı ile birlikte ele alındığında, bu durumun temel işlemlerin zaman maliyetini marjinal de olsa ArrayDeque lehine çevirdiği görülecektir. Dolayısıyla, yığıt ve kuyruk kullanımı için ilk önerdiğimiz yöntemin daha doğru olduğu söylenebilir.

Değişken Uzunluklu Diziler: Vector
Hızlı Arama Zamanlı Kaplar

---

1. VKÇ'nin ortaya konduğu J2SE 1.2 öncesinde tasarlanıp gerçekleştirilmiş olan veri kaplarının dokümantasyonunda iki noktayı kafa karıştırıcı bulabilirsiniz. [Islah edilerek çerçeveye oturtulması olanaksız gözüken] Dictionary ve Stack sınıflarını kullanmaktan kaçınılması tavsiye edilirken, Hashtable ve Vector sınıflarında tamamıyla aynı şeyi yapan farklı adlara sahip pek çok ileti çifti göze çarpar. Her iki durumda da sebep, VKÇ'nin ortaya koyduğu standart ve söz konusu sınıfların bu standarda uyumdaki başarısı(zlığı)dır. Programcı olarak bizim payımıza düşen ise, dokümantasyonda önerildiği gibi, ilk iki sınıf yerine önerilen seçeneklerden yararlanmak ve diğer iki sınıfta standartta bulunan ada sahip iletileri kullanmaktır. Böyle bir yaklaşım, yazdığımız kodun yeniden kullanılabilirliğini artıracaktır. ↑
2. Metotlarının synchronized ilan edilmiş olması, Vector sınıfını tamamıyla izlek güvenlikli kılmaz. Bu şekilde sağlanan güvence metotların teker teker kullanımlarına ilişkindir; Vector sınıfındaki iki veya daha fazla sayıda metodun aynı atomik işlemin parçası olarak icra edilmesini gerektiren durumlarda, iş yine programcıya düşecektir. ↑
3. Aslına bakarsanız, sıralanmak istenen verinin ikillerini 0 veya 1 olmasına göre gruplara ayırarak işini gören bazı algoritmalar karşılaştırma işleminden yararlanmazlar. Ne var ki, bu algoritmaların uygulanabilirliği bazı ilkel türlere kısıtlı olduğu için, bu istisna genelleştirilerek vardığımız yargıyı boşa çıkarmak için kullanılamaz. ↑
4. Aslına bakacak olursanız, ayrıcalıklı kuyruktan yararlanarak yığıt ve kuyruk displinine sahip kapların oluşturulması mümkündür. Bunun için yapılması gereken, elemanların ekleme zamanlarına dair bilgi içermeleri ve bu bilginin ayrıcalıklı kuyruğun sıralama ölçütü olarak kullanılmasıdır. ↑