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.
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ü:
Doğrusal veri yapılarını en geniş anlamda temsil eden soyut veri yapısı genel listedir. VKÇ'deki
Üst arayüzlerden kalıtlanmayıp
Değineceğimiz son ileti, ilk başta göründüğünden çok daha hünerli olan
Geziciler:
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,
Altyapıda yararlanılan kabın erişim özelliğine bağlı olarak
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
Doğrudan Erişimli Listeler:
VKÇ'de doğrudan erişimli genel liste gerçekleştirimi sağlayan iki sınıf vardır:
Yukarıda da söylediğimiz gibi, her iki sınıf da benzer performansa sahiptir.
Kısıtlı Listeler:
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
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ığı
Bu noktada, bazılarınız, Java'nın ilk uyarlamasından bu yana var olan
Ç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.
Bağlaçlı Liste:
VKÇ'nin genel liste gerçekleştirimi olarak sunduğu ikinci seçenek,
- 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örenObject
sınıfındakiequals
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 isehashCode
ileequals
'ı birlikte ele almaktan geçer. Çünkü,Object
sınıfındakiequals
metodunu ezip dehashCode
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.1 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.İ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 ikenArrayList
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ölgelerininsynchronized
bloğu içine alınarak çok-izlekli hale getirilmeleri gerekir. Buna karşılık, kamuya açık tüm metotlarısynchronized
olanVector
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 noktalardaCollections
sınıfındakisynchronizedList
metodu ile döndürülen görüntü üzerinde işlem yapılması da bir çözüm olarak hesaba katılmalıdır.2 - 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.İş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!3 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.4
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.İş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.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. - 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
veStack
sınıflarını kullanmaktan kaçınılması tavsiye edilirken,Hashtable
veVector
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. ↑ - 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. ↑ - 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. ↑
- 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. ↑