Bölüm 1: Giriş

1.1Dijital veri

Veri yapıları dersinin konusu, verinin bellekte düzenlenmesidir. Bir düzenden söz edebilmek için önce düzenlenecek şeyin ne olduğunu bilmek gerekir. Bilgisayarın belleğinde ne harf vardır ne fotoğraf ne de şarkı; yalnızca 0 ve 1 değerli küçük hücreler vardır. Gündelik hayattaki bilgiler bu hücrelere nasıl sığdırılır? Bu kesimin sorusu budur.

1.1.1Dijital veri nedir?

Telefonla bir ses kaydı yapıldığını düşünelim. Konuşan kişinin sesi havada bir basınç dalgası olarak yayılır. Bu dalga süreklidir: her an bir değeri vardır ve bu değer iki ölçüm arasında da sürekli değişir. Böyle sürekli büyüklüklere analog denir. Telefonun mikrofonu bu dalgayı bir elektrik gerilimine çevirir; gerilim de hâlâ analogdur. Telefonun işlemcisi ise sürekli bir büyüklükle çalışamaz. Ona sayılar, daha doğrusu 0 ve 1'lerden oluşan diziler gerekir.

Analog sinyali sayılara çeviren devreye analogdan dijitale dönüştürücü (analog-to-digital converter, kısaca ADC) denir. ADC, sinyalin değerini belirli aralıklarla ölçer ve her ölçümü bir sayı olarak kaydeder. Kayıt dinlenirken tersi yapılır: dijitalden analoğa dönüştürücü (digital-to-analog converter, kısaca DAC) sayıları yeniden bir gerilime, hoparlör de bu gerilimi ses dalgasına çevirir. Aradaki her iş bilgisayarın sayılar üzerinde yaptığı bir işlemdir: kaydetmek, kopyalamak, göndermek, sesi açıp kısmak, gürültüyü azaltmak. Şekil 1.1 bu zinciri gösterir.

Tanımdaki önemli sözcük temsildir. Bilgisayardaki 0 ve 1'ler, kendi başlarına hiçbir şey anlatmaz. Aynı sekiz bitlik dizi bir yerde bir harfi, başka bir yerde bir sayıyı, bir başka yerde bir pikselin kırmızılık düzeyini gösterebilir. Bitlere anlam kazandıran, onların nasıl yorumlanacağını söyleyen kuraldır. Bu kurala kodlama denir. Dosya uzantısı (.txt, .png, .mp3) da bir ipucudur: programa, dosyadaki bitleri hangi kodlamayla okuyacağını söyler.

1.1.2Bit, bayt ve ikili sayılar

Belleğin en küçük birimine bit (binary digit: ikili basamak) denir. Bir bit yalnız iki değer alabilir: 0 ya da 1. Donanımda bu iki değer, örneğin bir devredeki gerilimin düşük ya da yüksek olmasıyla, bir disk yüzeyindeki küçük bir bölgenin iki ayrı yönde mıknatıslanmasıyla gösterilir. İki durumu ayırt etmek, on durumu ayırt etmekten çok daha kolay ve güvenilirdir. Bilgisayarların ikili sistemi kullanmasının temel nedeni budur.

Tek bir bit az bilgi taşır, bu yüzden bitler gruplar hâlinde kullanılır. Sekiz bitlik gruba bayt (byte) denir. Bit sayısı arttıkça temsil edilebilecek değer sayısı hızla büyür. Bir bit 2 değer verir. İki bit 00, 01, 10, 11 olmak üzere 4 değer verir. Her yeni bit, var olan her diziyi bir 0 ve bir 1 ile sürdürerek değer sayısını iki katına çıkarır. Dolayısıyla n bit 2ⁿ farklı değer temsil edebilir: 8 bit 256, 16 bit 65.536, 32 bit 4.294.967.296 değer.

Bir bit dizisini sayı olarak okumanın kuralı ikili sayı sistemidir. Onluk sistemde her basamak, sağdan sola 1, 10, 100, 1000 gibi onun kuvvetleriyle çarpılır: 365 = 3·100 + 6·10 + 5·1. İkili sistemde aynı fikir ikinin kuvvetleriyle uygulanır. Sekiz bitlik bir dizide basamak değerleri soldan sağa 128, 64, 32, 16, 8, 4, 2, 1'dir.

Bayttan büyük birimler de günlük kullanımda karşımıza çıkar. Bir kilobayt (KB) yaklaşık bin bayt, bir megabayt (MB) yaklaşık bir milyon bayt, bir gigabayt (GB) yaklaşık bir milyar bayttır. “Yaklaşık” denmesinin nedeni, bazı yazılımların bu birimleri 1000 yerine 1024'ün kuvvetleriyle hesaplamasıdır; 1024 = 2¹⁰, ikili sistemde yuvarlak bir sayıdır.

1.1.3Dijital verinin özellikleri

Dijital verinin yaygınlaşmasının ardında üç özellik vardır.

• Sayısal olması. Veriler 0 ve 1 olarak, yani ikili sayılarla temsil edilir; örneğin 1011 0010. Her şey sayı olduğu için her tür bilgi aynı donanımla saklanabilir, aynı devrelerle taşınabilir. Bir sabit disk, içinde fotoğraf mı yoksa roman mı olduğunu bilmez.
• Kolay saklanması. Dijital veri elektronik ortamda saklanabilir ve kolayca paylaşılabilir: disk, bulut ve ağ bunun örnekleridir. Daha önemlisi, kopyalama kayıpsızdır. Bir plak ya da kaset her kopyalamada biraz bozulur; dijital bir dosyanın milyonuncu kopyası ilkiyle bit bit aynıdır.
• İşlemeye uygun olması. Bilgisayarlar dijital veriyi çok hızlı işler. Günümüzün sıradan bir işlemcisi saniyede yaklaşık 10⁹, yani bir milyar düzeyinde temel işlem yapar.

Üçüncü madde, veri yapıları dersinin neden var olduğunu da açıklar. Saniyede bir milyar işlem, ilk bakışta her problemi anında çözmeye yetecek gibi görünür. Oysa veri büyüdükçe kötü düzenlenmiş bir programın yaptığı iş, verinin boyutundan çok daha hızlı büyüyebilir. Bir milyon kayıt olsun ve program her kaydı öteki bütün kayıtlarla karşılaştırsın. Bu, 10⁶ · 10⁶ = 10¹² karşılaştırma eder. Saniyede 10⁹ işlemle iş yaklaşık 1000 saniye, yani 16 dakikadan fazla sürer. Aynı iş, verileri uygun bir yapıda tutan bir programla saniyenin çok küçük bir kesrinde bitebilir. Bilgisayar yalnızca 0 ve 1'leri tanır. Veri yapıları, bu bitleri anlamlı ve verimli bir düzende tutmanın yollarıdır.

1.1.4Metin, sayı, görüntü ve sesin temsili

Her bilgi türü için ayrı bir kodlama kuralı vardır. Tablo 1.1 dört temel türü ve her birinin kısa bir örneğini verir; ardından her biri ayrı ayrı açıklanır.

Metin. Bir metni saklamak için her karaktere bir sayı karşılık getirilir. Bu eşlemeyi veren tabloya karakter kodlaması denir. En eski ve en yaygın kodlamalardan biri ASCII'dir (American Standard Code for Information Interchange). ASCII, 128 karakteri 0–127 arasındaki sayılarla gösterir: büyük harfler 65'ten ('A'), küçük harfler 97'den ('a'), rakamlar 48'den ('0') başlar. 128 değer 7 bite sığar; pratikte her karakter bir baytta saklanır. Örneğin 'A' karakteri 65 sayısıyla, o da 01000001 bit dizisiyle temsil edilir.

ASCII yalnız İngilizce harfleri kapsar; “ş”, “ğ”, “ı” gibi harfler onda yoktur. Dünyadaki bütün yazı sistemlerini tek bir tabloda toplayan standart Unicode'dur. Unicode her karaktere bir kod noktası verir; örneğin “ş” harfinin kod noktası 351'dir. Bu sayının bayt olarak nasıl yazılacağı ayrı bir kuraldır. Web'de en yaygın biçim olan UTF-8, ASCII karakterlerini yine tek baytla, “ş” gibi karakterleri iki ya da daha çok baytla yazar. Bu yüzden Türkçe harf içeren bir sözcük, harf sayısından fazla bayt tutabilir. “Veri” 4 harf ve 4 bayttır. “Şeker” ise 5 harflidir ama UTF-8'de 6 bayt tutar, çünkü “Ş” iki bayt kaplar. Java'nın char tipi ise 16 bitlik bir UTF-16 kod birimidir; “ş” Java'da tek bir char'a sığar.

Sayılar. Tam sayılar ikili sistemde doğrudan yazılır. Negatif sayılar için bilgisayarlar ikiye tümleyen denen bir kural kullanır; bu kuralın ayrıntısı burada gerekmez, sonucu yeterlidir: n bitlik bir işaretli tam sayı −2ⁿ⁻¹ ile 2ⁿ⁻¹ − 1 arasındaki değerleri alır. 8 bit için bu aralık −128 … 127'dir. Ondalıklı sayılar ise kayan nokta (floating point) biçiminde saklanır. Bu biçimi tanımlayan standart IEEE 754'tür. Kayan nokta sayısı, bilimsel gösterimdeki gibi bir işaret, bir anlamlı basamaklar kısmı ve bir üs taşır: 3,14 gibi bir sayı yaklaşık olarak 1,57 · 2¹ biçiminde saklanır. Anlamlı basamak sayısı sınırlı olduğu için pek çok ondalıklı sayı ancak yaklaşık olarak temsil edilebilir.

Görüntü. Bir dijital görüntü, piksel denen küçük kareler ızgarasıdır. Her pikselin rengi, kırmızı (R), yeşil (G) ve mavi (B) ışığın ne kadar karıştırıldığını gösteren üç sayıyla verilir. Her bileşen genellikle bir bayttır, yani 0 ile 255 arasında bir değer alır. Tam kırmızı bir piksel (255, 0, 0), beyaz (255, 255, 255), siyah (0, 0, 0) olarak yazılır. Görüntü, satır satır dizilmiş bu üçlülerin uzun bir dizisi olarak saklanır.

Ses. Ses, ADC'nin sinyali belirli aralıklarla ölçmesiyle sayıya dönüşür. Her ölçüme örnek, saniyedeki ölçüm sayısına örnekleme hızı denir. Müzik CD'leri saniyede 44.100 örnek alır; her örnek 16 bitlik bir tam sayıdır ve stereo kayıtta sol ve sağ kanal için ayrı ayrı örnek tutulur.

1.1.5Dijital veri türleri

Dijital veriler, nasıl düzenlendiklerine göre de sınıflandırılır. Tablo 1.2 yaygın bir sınıflandırmayı verir.

Yapısal veride her kaydın hangi alanlardan oluştuğu önceden bellidir. Bir öğrenci tablosunun her satırı numara, ad, bölüm ve not ortalaması alanlarını içerir; bu alanların listesine şema denir. CSV (comma-separated values: virgülle ayrılmış değerler) dosyası da yapısaldır: her satır bir kayıt, virgüllerle ayrılan her sütun bir alandır. Yapısal veride arama ve sıralama kolaydır, çünkü her değerin yeri bellidir.

Yarı yapısal veride bir şema yoktur ya da gevşektir, ama veri etiketlerle kendi yapısını kendisi anlatır. Aşağıdaki JSON (JavaScript Object Notation) parçası bir öğrenciyi anlatır:

{ "no": 101, "ad": "Ayşe", "dersler": ["Veri Yapıları", "Fizik"] }

Her değerin önünde onun ne olduğunu söyleyen bir etiket ("no", "ad") vardır. Bir başka öğrencinin kaydında "dersler" alanı hiç olmayabilir ya da fazladan bir "telefon" alanı bulunabilir. XML (eXtensible Markup Language) aynı işi <ad>Ayşe</ad> gibi açılış ve kapanış etiketleriyle yapar. Yarı yapısal veri iç içe yapılar kurmaya elverişlidir: bir öğrencinin içinde bir ders listesi, her dersin içinde bir not listesi bulunabilir. Bu iç içelik, ağaç biçiminde bir düzendir.

Metin, görüntü ve ses gibi türler ise bir şemaya göre değil, içeriğe göre düzenlenir. Bir e-postanın gövdesi ya da bir fotoğrafın pikselleri, bir veritabanı tablosu gibi alanlara bölünmez. Bu tür veriler çoğu zaman yapısal olmayan veri olarak da anılır.

Bu sınıflandırmadan veri yapıları için şu sonuç çıkar: verinin dışarıdaki biçimi, program içinde seçilecek yapıyı etkiler. CSV satırları doğal olarak bir dizi ya da liste içinde tutulur. JSON ve XML'in iç içe yapısı, program içinde bir ağaçla temsil edilir. Bir e-posta adresinden kişiye ulaşmak için ise anahtar–değer eşlemesi kullanılır.

1.2Veri yapıları ve algoritmalar

Bir program iki şeyden oluşur: üzerinde çalıştığı veriler ve bu verilere uyguladığı adımlar. Bu iki parça birbirinden bağımsız değildir. Verilerin nasıl tutulduğu, hangi adımların kolay, hangilerinin zahmetli olacağını belirler. Adımların neler olacağı da verilerin nasıl tutulması gerektiğini belirler.

1.2.1Algoritma ve veri yapısı

Yemek tarifi, algoritmanın gündelik hayattaki en tanıdık örneğidir: malzemeler bellidir, adımlar sıralıdır, her adım ne yapılacağını açıkça söyler ve tarif sonunda biter. Bilgisayardaki bir algoritmanın da aynı özellikleri taşıması gerekir. Adımlar bilgisayarın yapabileceği kadar açık olmalı, belirsiz bir talimat (“biraz tuz ekle”) bulunmamalı ve algoritma sonlu sayıda adımda durmalıdır.

Veri yapısı, verileri yönetmek ve işlemek için gereken altyapıdır. Algoritma bu altyapının üzerinde çalışır. İkisi birlikte iyi seçilirse yazılım verimli çalışır ve problem sistemli biçimde çözülür. İsviçreli bilgisayar bilimci Niklaus Wirth, bu ilişkiyi 1976'da yayımladığı kitabının adıyla özetlemiştir: Algoritmalar + Veri Yapıları = Programlar (Algorithms + Data Structures = Programs).

İlişkiyi bir örnekle görelim. Bin kişilik bir telefon rehberinde bir ismi aramak gerekiyor. İsimler rastgele sırada duruyorsa tek yol baştan başlayıp her ismi tek tek kontrol etmektir. Aranan isim en sonda ya da hiç yoksa bin karşılaştırma gerekir. İsimler alfabetik sıradaysa bambaşka bir algoritma kullanılabilir: ortadaki isme bakılır; aranan isim alfabede ondan önceyse sağ yarı, sonraysa sol yarı tümüyle elenir. Her karşılaştırma aday sayısını yarıya indirir: 1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1. En çok 10 karşılaştırmada sonuca ulaşılır. Aynı veriler, farklı bir düzende tutulunca yüz kat hızlı bir algoritmaya izin vermiştir. Bunun bedeli de vardır: sıralı düzeni korumak için her yeni isim doğru yere eklenmelidir.

1.2.2Düzenin bedeli ve kazancı

Veri yapılarının temel amacı verilere hızlı ve etkili erişimdir. Sunumdaki şekil bunu bir mutfak çekmecesiyle anlatır. Aynı eşyalar bir çekmecede karmakarışık, ötekinde bölmelere ayrılmış olarak durur. Karışık çekmecede bir kaşık aramak, bütün eşyaları tek tek elden geçirmeyi gerektirebilir. Düzenli çekmecede kaşıkların bölmesi bellidir; el doğrudan oraya uzanır.

Benzetmenin öğrettiği ikinci şey daha az fark edilir: düzen bedava değildir. Düzenli çekmeceye bir eşya koyarken onun bölmesini bulmak gerekir. Karışık çekmeceye ise eşya gelişigüzel atılır. Demek ki düzen, ekleme işini biraz zorlaştırıp arama işini çok kolaylaştırır. Hangi düzenin seçileceği, hangi işin daha sık yapılacağına bağlıdır. Çekmeceye yılda bir eşya giriyor ama her gün bir şey aranıyorsa düzen kesinlikle kazançlıdır. Bir şey her gün atılıp hiç aranmıyorsa (çöp kutusunu düşünelim) düzenle uğraşmak gereksizdir.

Veri yapısı seçmenin özü bu ödünleşimdir (trade-off). Her yapı bazı işlemleri ucuzlatır, bazılarını pahalılaştırır. Programın hızını ve bellek kullanımını doğrudan bu seçim belirler.

1.2.3Temel yapı taşları: nesneler, diziler, bağlantılar

Ne kadar karmaşık görünürse görünsün, veri yapılarının neredeyse hepsi üç temel parçadan kurulur.

Nesneler. Bir nesne, birbiriyle ilgili nitelikleri adlandırılmış alanlar hâlinde tek bir birimde toplar. Bir öğrencinin adı ve numarası iki ayrı değişkende de tutulabilir, ama bu durumda hangi adın hangi numaraya ait olduğunu programcının aklında tutması gerekir. Java'da bu iki niteliği tek bir birimde toplayan sınıf şöyle yazılır:

class Ogrenci {
  String ad;   // öğrencinin adı
  int no;      // öğrenci numarası
  Ogrenci(String ad, int no) { this.ad = ad; this.no = no; }
}

Bir Ogrenci nesnesi oluşturulduğunda ad ve no alanları bellekte birlikte durur ve birlikte taşınır. Nesneler, veri yapılarındaki düğümlerin de temelidir: bir düğüm, bir değer ile o değerin komşularını gösteren alanları bir arada tutan küçük bir nesnedir.

Diziler. Bir dizi, aynı türden öğeleri bellekte ardışık yuvalarda toplu olarak saklar. Ardışıklık dizinin en büyük gücüdür. Dizinin bellekte nerede başladığı ve her öğenin kaç bayt tuttuğu biliniyorsa i. öğenin adresi tek bir çarpma ve toplamayla hesaplanır: başlangıç adresi + i × öğe boyutu. Öğe 4 baytlık bir int ise ve dizi 1000 numaralı adreste başlıyorsa 5 numaralı öğe 1000 + 5 × 4 = 1020 adresindedir. Bu hesap dizinin boyundan bağımsızdır; on öğeli bir dizide de on milyon öğeli bir dizide de aynı sürede yapılır.

Bağlantılar. Bir bağlantı, bir varlıktan başka bir varlığa yönelen bir işarettir. Java'da bu işarete referans denir. Bağlantılar varlıklar arasında isteğe bağlı, yönlü ilişkiler kurar: bir öğrenci danışmanını, bir şehir komşu şehirleri, bir müzik listesindeki şarkı sıradaki şarkıyı gösterebilir. Bağlantılı yapıların öğeleri bellekte dağınık durabilir; düzeni ardışıklık değil, oklar sağlar. Sunumdaki şekilde son figürün okunun ucunda bir soru işareti vardır. Zincirin bir sonu olmalıdır ve hiçbir şeyi göstermeyen bu son bağlantı Java'da null ile ifade edilir.

Dizi ile bağlantılar arasındaki seçim, veri yapıları dersinin ana temalarından biridir. Dizi indisle anında erişim sağlar ama boyutu baştan bellidir ve araya ekleme yapmak için öğeleri kaydırmak gerekir. Bağlantılı yapı istediği kadar büyür ve araya ekleme yalnızca birkaç okun yönünü değiştirmekle yapılır; ama i. öğeye ulaşmak için baştan başlayıp okları tek tek izlemek gerekir.

1.3Veri tipleri

Bir programlama dili, bitleri nasıl yorumlayacağını programcıdan öğrenir. Programcı her değişkenin tipini belirterek “bu bellek alanındaki bitleri tam sayı olarak oku” ya da “bunları bir karakter olarak oku” demiş olur. Bu kesim Java'nın hazır tiplerini ve tiplerin programı hatalardan nasıl koruduğunu anlatır.

1.3.1İlkel veri tipleri

Java'da dilin kendisine gömülü sekiz temel tip vardır. Bunlara ilkel tip (primitive type) denir. İlkel tipler tam sayıları, ondalıklı sayıları, mantıksal değerleri ve karakterleri temsil eder. Tablo 1.3 bu tipleri, bellekte kapladıkları yeri ve alabilecekleri değerleri gösterir.

Tablodaki aralıklar rastgele değildir; 1.1.4'teki kuraldan doğrudan çıkar. n bitlik işaretli bir tam sayı −2ⁿ⁻¹ ile 2ⁿ⁻¹ − 1 arasında değer alır. byte için n = 8: 2⁷ = 128, aralık −128 … 127. short için 2¹⁵ = 32.768. int için 2³¹ = 2.147.483.648; “yaklaşık ±2,1 milyar” buradan gelir. long için 2⁶³ ≈ 9,22·10¹⁸'dir. Pozitif tarafın bir eksik olmasının nedeni, 0'ın da pozitif yarıdaki değerlerden birini kullanmasıdır.

İlkel tiplerin dört ortak özelliği vardır. Basit ve temel tiplerdir; başka tiplerden kurulmazlar. Bellekte sabit bir boyut kaplarlar: bir int içinde 3 de olsa 2 milyar da olsa 32 bit tutar. İşlemci onları doğrudan işler; iki int'i toplamak işlemcinin tek bir komutudur. Son olarak, bir ilkel değişken değerini doğrudan kendi içinde tutar. Bu son özelliğin önemi 1.4'te ortaya çıkacak.

Sabit boyutun bir sonucu, her tipin bir sınırı olmasıdır. Sınır aşıldığında Java hata vermez; değer, aralığın öbür ucuna sarar. Buna taşma (overflow) denir.

int buyuk = Integer.MAX_VALUE;           // 2147483647
System.out.println(buyuk + 1);           // -2147483648
long genis = (long) buyuk + 1;
System.out.println(genis);               // 2147483648
System.out.println(0.1 + 0.2);           // 0.30000000000000004

Ondalıklı tiplerin sınırı farklıdır: çok büyük ya da çok küçük sayılar temsil edilebilir, ama her sayı yalnız yaklaşık olarak. float yaklaşık 7, double yaklaşık 15 anlamlı basamak tutar. 0,1 sayısı ikili sistemde sonsuz bir kesirdir (onluk sistemde 1/3'ün 0,333… olması gibi); bu yüzden bellekte ancak yaklaşığı durur. Kodun son satırı bunun sonucunu gösterir: 0.1 + 0.2 ifadesi 0.30000000000000004 yazdırır.

1.3.2Veri tipi: değer kümesi ve işlemler

Bir tipi yalnızca “alabileceği değerler” olarak düşünmek eksiktir. int ile String arasındaki fark, yalnız birinin sayı ötekinin metin tutması değildir; ikisine uygulanabilen işlemler de farklıdır.

Tam sayılar için toplama, çıkarma, çarpma ve bölme gibi işlemler tanımlıdır. Metin dizileri (String) için ise karşılaştırma, birleştirme ve alt dize alma gibi işlemler vardır: "veri" + "yapısı" ifadesi "veriyapısı" dizesini, "yapısı".substring(0, 4) ise "yapı" dizesini verir. Aynı + işareti iki tipte farklı iş görür: sayılarda toplar, dizelerde uç uca ekler. Davranışın tipe ait olduğunun en açık göstergesi budur.

Tipin davranışı belirlediğini en iyi gösteren örnek bölmedir. Java'da iki int'in bölümü yine bir int'tir; ondalık kısım yuvarlanmaz, doğrudan atılır.

System.out.println(7 / 2);     // 3
System.out.println(7 % 2);     // 1
System.out.println(-7 / 2);    // -3
System.out.println(-7 % 2);    // -1
System.out.println(7.0 / 2);   // 3.5
System.out.println(7 / 2.0);   // 3.5
int n1 = 7, n2 = 8;
double ort1 = (n1 + n2) / 2;     // 7.0
double ort2 = (n1 + n2) / 2.0;   // 7.5

Kodu satır satır okuyalım. 7 / 2 iki tam sayının bölümüdür: 3,5'in ondalık kısmı atılır, sonuç 3 olur. 7 % 2 kalan işlemidir ve 1 verir; bölüm ile kalan birlikte 7 = 2 · 3 + 1 eşitliğini sağlar. -7 / 2 sonucu −4 değil −3'tür, çünkü Java ondalık kısmı sıfıra doğru atar; buna uygun olarak kalan da −1 olur: −7 = 2 · (−3) + (−1). İşlenenlerden biri double olduğunda, örneğin 7.0 / 2 ya da 7 / 2.0, bölme ondalıklı yapılır ve sonuç 3.5'tir.

Tipler birbirine karıştığında Java belirli kurallar uygular. char aslında 16 bitlik bir sayıdır; aritmetik bir işlemde int'e yükseltilir. Bu yüzden 'A' + 1 ifadesi 66 verir. + işleminin bir tarafı String olduğunda ise öbür taraf metne çevrilip eklenir: "A" + 1 ifadesi "A1" dizesini verir. İşlemler soldan sağa yapıldığı için 1 + 2 + "x" önce 3'ü hesaplar ve "3x" verir; "x" + 1 + 2 ise "x12" verir.

1.3.3Tip güvenliği

Her işlem her tipte geçerli değildir. Bir metni bir sayıyla çarpmanın Java'da bir anlamı yoktur: "abc" * 2 yazıldığında derleyici programı hiç çalıştırmadan hatayı bildirir. Tiplerin bu koruyucu rolüne tip güvenliği denir. Veri tipleri hataları en aza indirmek için kullanılır; tipin getirdiği kısıtlamalar, programcıya neyin mümkün olup neyin olmadığını söyler.

Hatanın ne zaman yakalandığı çok önemlidir. Java gibi statik tipli dillerde değişkenlerin tipi kaynak kodda yazılıdır ve derleyici her işlemin tiplere uygun olup olmadığını program çalışmadan önce denetler. Bu denetime derleme zamanı denetimi denir. Bir hata derleme zamanında yakalanırsa programcı onu daha programı kimseye vermeden görür ve düzeltir. Aynı hata ancak çalışma zamanında ortaya çıkabilseydi, program belki aylarca sorunsuz çalışır, sonra o satıra ilk kez gelindiğinde bir kullanıcının elinde çökerdi.

Tip güvenliği, veri yapılarında özellikle değerlidir. Bir veri yapısı binlerce öğe tutar ve bu öğeler programın çok farklı yerlerinde eklenip çıkarılır. Yanlış tipte tek bir öğenin yapıya girmesi, hatanın kaynağından çok uzakta bir yerde sorun çıkarır. Bu yüzden Java'da veri yapıları, içlerine hangi tipte öğe gireceğini derleyiciye bildiren jeneriklerle yazılır (1.5).

1.4Java bellek modeli

Veri yapılarının neredeyse hepsi, bir değişkenin başka bir yerdeki veriyi “göstermesi” fikrine dayanır. Bu fikri doğru kavramadan bağlı liste, ağaç ya da çizge kodu okunamaz. Bu kesim, Java programı çalışırken değişkenlerin ve nesnelerin bellekte nerede durduğunu anlatır.

1.4.1Çağrı yığını ve heap

Çalışan bir Java programı belleği iki ana bölgede kullanır. Birinci bölge çağrı yığınıdır (call stack). Bir metot her çağrıldığında çağrı yığınında o çağrıya ait bir çerçeve (stack frame) açılır. Metodun parametreleri ve yerel değişkenleri bu çerçevede durur. Metot bittiğinde çerçeve silinir ve içindeki bütün yerel değişkenler onunla birlikte yok olur. Çerçeveler üst üste konur ve en son açılan ilk kapanır; bölgenin “yığın” adını alması bu yüzdendir.

İkinci bölge heap bellektir (heap memory). new ile oluşturulan her nesne, her dizi ve her String heap'te yer alır. Heap'teki nesneler hiçbir metodun çerçevesine bağlı değildir; onları oluşturan metot bittikten sonra da yaşamaya devam edebilir.

Java'da sekiz ilkel tipin dışındaki her tip bir referans tipidir: diziler, String, kendi yazdığımız sınıflar ve kütüphanedeki bütün sınıflar. Aşağıdaki dört satır iki türü yan yana gösterir:

int x = 5;               // ilkel: değer
int[] a = {7, 2, 9};     // referans → dizi
String s = "veri";       // referans → nesne
int[] p = null;          // hiçbir şeyi göstermez

Şekil 1.2 bu satırların bellekte bıraktığı izi gösterir. Çerçevedeki dört kutunun dördü de küçüktür ve aynı boydadır. Dizi ister 3 ister 3 milyon öğeli olsun, a değişkeni yalnız bir adres tutar. Asıl veri heap'tedir.

Bir nesneyi artık hiçbir referans göstermiyorsa programın ona ulaşmasının bir yolu kalmaz. Böyle nesneler boşuna yer kaplar. Java'da bu nesneleri çöp toplayıcı (garbage collector) zaman zaman bulup temizler; programcının belleği elle geri vermesi gerekmez. C gibi dillerde bu iş programcıya kalır ve unutulması bellek sızıntısına yol açar.

null bir referansın gösterdiği nesneye erişmeye çalışmak çalışma zamanında hata verir. p hiçbir diziyi göstermediği için p[0] ifadesi bir öğe bulamaz ve Java NullPointerException fırlatır. Bağlı yapılarla çalışırken en sık karşılaşılan hata budur.

1.4.2Kod izleme: değer mi, referans mı?

Atama işlemi =, sağdaki değeri soldaki değişkene kopyalar. Kopyalanan şeyin ne olduğu ise değişkenin türüne bağlıdır. Aşağıdaki sekiz satırlık kod bu farkı adım adım gösterir:

int x = 5;
int y = x;
y = 7;
int[] a = {1, 2, 3};
int[] b = a;
b[0] = 9;
b = new int[2];
System.out.println(x + " " + a[0]);

Kodu satır satır izleyelim. Tablo 1.4 her satırdan sonra değişkenlerin ve heap'teki nesnelerin durumunu verir; nesneler oluşturulma sırasına göre #1, #2 diye numaralandırılmıştır.

Satır 1–3. x ilkel bir değişkendir ve 5 değeri doğrudan çerçevededir. int y = x; satırı x'in değerinin bir kopyasını y'ye yazar. Artık iki ayrı kutuda iki ayrı 5 vardır ve bu kutular birbirinden bağımsızdır. y = 7; yalnız y'nin kutusunu değiştirir; x hâlâ 5'tir.

Satır 4. {1, 2, 3} ifadesi heap'te üç öğeli yeni bir dizi oluşturur. a dizinin kendisini değil, ona bir referansı tutar; şekillerde bu referans bir okla çizilir.

Satır 5. int[] b = a; satırı da bir atamadır ve yine kopyalama yapar. Ama kopyalanan şey a'nın içindeki değerdir, o değer de bir adrestir. Dizi kopyalanmaz; heap'te hâlâ tek bir dizi vardır. a ile b şimdi aynı nesneyi gösteren iki oktur.

Satır 6. b[0] = 9; satırı b'nin gösterdiği nesneye gider ve onun 0. hücresini değiştirir. Aynı nesneyi a da gösterdiği için a[0] da artık 9'dur. Bir nesneye birden çok referansla ulaşılabilmesine takma ad (aliasing) denir: a ve b aynı dizinin iki ayrı adıdır.

Satır 7. b = new int[2]; heap'te iki öğeli yeni bir dizi oluşturur ve b'nin okunu ona çevirir. Java yeni bir int dizisinin hücrelerini 0 ile doldurur. Bu satır a'yı etkilemez: değişen, b'nin içindeki adrestir, 1 numaralı nesne değildir.

Satır 8. x + " " + a[0] ifadesi 5, bir boşluk ve 9'u yan yana yazar. Çıktı 5 9'dur.

Bütün izlemenin özeti tek bir kuraldır: = işareti ilkel tipte değeri, referans tipte adresi kopyalar. Referans tipte bir değişkene yapılan atama okun yönünü değiştirir. Referansın gösterdiği nesneye b[0] = … ya da nesne.alan = … biçiminde yapılan atama ise nesnenin kendisini değiştirir. Aynı kural kendi yazdığımız sınıflar için de geçerlidir:

Ogrenci o1 = new Ogrenci("Ayşe", 101);
Ogrenci o2 = o1;          // ikinci referans, yeni nesne yok
o2.no = 202;
System.out.println(o1.no);   // 202

o2 = o1 yeni bir öğrenci oluşturmaz; ikinci bir ok çizer. o2.no = 202 ortak nesnenin alanını değiştirdiği için o1.no da 202 olur.

1.4.3Metotlara değer geçirme

Bir metot çağrıldığında, çağıran tarafın verdiği her argüman metodun parametresine atanır. Bu atama da sıradan bir = gibi çalışır. Java her zaman değerle geçirir: parametre, argümanın bir kopyasını alır. İlkel tipte kopyalanan değer sayının kendisi, referans tipte ise adrestir. Sonuç iki takas metodunda açıkça görülür:

static void takas(int a, int b) {
  int g = a; a = b; b = g;
}
static void takas(int[] d) {
  int g = d[0]; d[0] = d[1]; d[1] = g;
}

int p = 1, q = 2;
takas(p, q);
System.out.println(p + " " + q);              // 1 2
int[] dd = {1, 2};
takas(dd);
System.out.println(Arrays.toString(dd));      // [2, 1]

Bu kuralın sınırını da bilmek gerekir. Metot içinde d = new int[2]; gibi bir atama yapılsaydı yalnız yerel d okunun yönü değişirdi; çağıranın dd değişkeni eski diziyi göstermeye devam ederdi. Metot bitince yeni diziyi gösteren bir referans kalmaz ve çöp toplayıcı onu temizler. Kısacası metot, nesnenin içini değiştirebilir ama çağıranın değişkenini başka bir nesneye yöneltemez.

1.4.4String nesneleri ve karşılaştırma

String bir referans tipidir, ama dizilerden önemli bir farkı vardır: bir String nesnesi oluşturulduktan sonra içeriği değiştirilemez. Bu özelliğe değiştirilemezlik (immutability) denir. toUpperCase(), substring() ya da + gibi işlemler var olan nesneyi değiştirmez; sonucu yeni bir nesne olarak döndürür.

String s1 = "ders";
String s2 = s1;
s2 = s2.toUpperCase();
System.out.println(s1 + " " + s2);      // ders DERS
String u1 = new String("veri");
String u2 = new String("veri");
System.out.println(u1 == u2);           // false
System.out.println(u1.equals(u2));      // true

İlk iki satırdan sonra s1 ve s2 aynı "ders" nesnesini gösterir. Üçüncü satırda s2.toUpperCase() yeni bir "DERS" nesnesi oluşturur ve atama s2'nin okunu bu yeni nesneye çevirir. Eski nesne değişmemiştir; s1 hâlâ onu gösterir ve ders yazdırır. Dizide ortak nesneyi değiştirmek mümkündü (b[0] = 9), String'de böyle bir işlem yoktur. Bu yüzden aynı String'i paylaşan değişkenler birbirini etkileyemez.

Kodun son iki satırı ikinci önemli noktayı gösterir. new String("veri") her çağrıldığında heap'te ayrı bir nesne oluşturur. u1 == u2 ifadesi iki referansı karşılaştırır, yani “iki ok aynı nesneyi mi gösteriyor?” diye sorar; cevap false'tur. u1.equals(u2) ise nesnelerin içeriğini karşılaştırır ve true verir.

1.5Jenerikler

Bir yığın, bir liste ya da bir kuyruk, içinde ne tuttuğundan bağımsız olarak aynı biçimde çalışır. Tam sayıları tutan bir yığın ile öğrenci nesnelerini tutan bir yığının push ve pop işlemleri arasında hiçbir fark yoktur. Her öğe tipi için ayrı bir yığın sınıfı yazmak emek kaybıdır. Üstelik bir hata, sınıfın bütün kopyalarında tekrarlanır. Jenerikler bu sorunu tip güvenliğinden ödün vermeden çözer.

1.5.1Jenerik olmayan kutunun sorunu

Tek bir öğe saklayan en basit “veri yapısını”, bir kutuyu düşünelim. Her tipte öğe alabilmesi için Java'daki bütün sınıfların ortak atası olan Object tipini kullanabiliriz:

public class EskiKutu {
  private Object icerik;
  public void koy(Object x) { icerik = x; }
  public Object al() { return icerik; }
}

EskiKutu e = new EskiKutu();
e.koy(42);                    // derlenir: 42 de bir Object
String z = (String) e.al();   // derlenir, ama çalışırken ClassCastException

Bu kutu her şeyi kabul eder; sorun da buradadır. koy(42) çağrısı derlenir. al() ise Object döndürdüğü için sonucu bir String değişkenine yazmak isteyen programcı bir tür dönüşümü ((String)) yazmak zorundadır. Derleyici bu dönüşümün doğru olup olmadığını bilemez ve programı derler. Hata ancak program çalışırken, kutudan çıkan 42'nin bir String olmadığı anlaşıldığında ortaya çıkar: ClassCastException. 1.3.3'teki ölçüye göre bu en kötü durumdur: hata derleme zamanında değil, çalışma zamanında yakalanmıştır.

1.5.2Kutu<T>: her tür için tek yapı

Aynı kutunun jenerik hâli şöyledir:

public class Kutu<T> {
  private T icerik;
  public void koy(T x) { icerik = x; }
  public T al() { return icerik; }
}

Kutu<String> k = new Kutu<>();
k.koy("veri");
String s = k.al();      // dönüşüm gerekmez
Kutu<Integer> m = new Kutu<>();
m.koy(42);              // int → Integer
// m.koy("x");          // DERLEME HATASI

Sınıf adının yanındaki <T>, T'nin bir tür parametresi olduğunu bildirir. Sınıfın içinde T, sanki gerçek bir tipmiş gibi kullanılır: icerik alanı T tipindedir, koy bir T alır, al bir T döndürür.

İstemci kod Kutu<String> k yazdığında, derleyici bu değişken için T'nin yerine String koyar. k.koy artık yalnız String kabul eder, k.al() bir String döndürür. Bu yüzden String s = k.al(); satırında tür dönüşümüne gerek yoktur. new Kutu<>() yazımındaki boş açılı ayraçlara elmas işleci denir; derleyici tür argümanını soldaki bildirimden çıkarır.

Kutu<Integer> m ise aynı sınıftan, bu kez tam sayılar için üretilmiş bir kutudur. Açıklama satırı yapılmış m.koy("x") çağrısı açılırsa program derlenmez: Kutu<Integer>'ın koy metodu yalnız Integer kabul eder. 1.5.1'deki hata artık derleme zamanında yakalanır.

Şekil 1.4 bu ilişkiyi özetler: kod bir kez yazılır, her tür argümanı için ayrı ve tip güvenli bir sınıf gibi kullanılır. Jeneriklerin kazancı üç maddeyle söylenebilir. Tür denetimi derleme zamanında yapılır; yanlış tür program çalışmadan yakalanır. Kutudan çıkan değer için tür dönüşümü yazılmaz. Kod tekrarı ortadan kalkar.

1.5.3Sarmalayıcı sınıflar ve otomatik kutulama

Tür parametresinin önemli bir kısıtı vardır: T yalnız bir referans tipi olabilir. Kutu<int> yazılamaz. Bunun nedeni, jenerik sınıfın içinde T tipindeki değerlerin hep referans gibi işlenmesidir; ilkel bir değer ise referans değildir, değeri doğrudan tutar.

Çözüm, her ilkel tip için Java'da hazır bulunan sarmalayıcı sınıflardır. Bir sarmalayıcı nesne, içinde tek bir ilkel değer taşıyan küçük bir heap nesnesidir: int için Integer, double için Double, char için Character, boolean için Boolean ve diğerleri. Tam sayı tutan kutu bu yüzden Kutu<Integer> olarak yazılır.

Programcının her seferinde ilkel değeri elle sarmalayıcıya koyması zahmetli olurdu. Java bu dönüşümü kendiliğinden yapar. Bir int, Integer beklenen bir yere verildiğinde otomatik olarak bir Integer nesnesine konur; buna otomatik kutulama (autoboxing) denir. m.koy(42) satırındaki açıklama (“int → Integer”) bunu anlatır. Tersi de olur: bir Integer aritmetik bir işlemde ya da bir int değişkene atanırken içindeki değer çıkarılır; buna kutudan çıkarma (unboxing) denir.

Otomatik kutulama kodu kısaltır ama iki tuzak getirir. Birincisi null'dır. İçine hiçbir şey konmamış bir Kutu<Integer>'ın al() metodu null döndürür. Bu değer bir int'e atanmak istendiğinde Java içinden değer çıkarmaya çalışır ve NullPointerException fırlatır. İkincisi karşılaştırmadır:

Integer i1 = 127, i2 = 127;
Integer i3 = 128, i4 = 128;
System.out.println(i1 == i2);         // true
System.out.println(i3 == i4);         // false
System.out.println(i3.equals(i4));    // true

Integer bir referans tipi olduğu için == iki nesnenin adresini karşılaştırır. Java, −128 ile 127 arasındaki tam sayılar için hazır nesneler tutar ve kutulamada bunları yeniden kullanır. Bu yüzden 127 için iki değişken aynı nesneyi gösterir ve == true verir. 128 için iki ayrı nesne oluşur ve == false verir. equals ise içerikleri karşılaştırdığı için her iki durumda da doğru sonucu verir.

1.5.4Java koleksiyonları

Java'nın standart kütüphanesindeki veri yapılarının hepsi jeneriktir. Bu yapılara topluca koleksiyonlar denir. En sık kullanılanlardan ikisi ArrayList<E> ve Map<K,V>'dir. ArrayList<E>, E tipinde öğeleri sıralı tutan ve gerektikçe büyüyen bir listedir. Map<K,V> ise K tipindeki anahtarları V tipindeki değerlere eşler; iki tür parametresi alır. Aşağıdaki kod üç koleksiyonu birlikte kullanır:

ArrayList<String> liste = new ArrayList<>();
liste.add("Ali"); liste.add("Can"); liste.add("Ali");
HashSet<String> kume = new HashSet<>(liste);
HashMap<Integer, String> ogr = new HashMap<>();
ogr.put(101, "Ayşe");
ogr.put(102, "Mehmet");
ogr.put(101, "Zeynep");
System.out.println(liste.size() + " " + kume.size());   // 3 2
System.out.println(ogr.size() + " " + ogr.get(101));    // 2 Zeynep
System.out.println(ogr.get(103));                       // null

Liste aynı öğeyi birden çok kez tutabilir; üç add çağrısından sonra boyutu 3'tür. HashSet bir kümedir ve her öğeyi yalnız bir kez tutar; listeden oluşturulduğunda ikinci “Ali” elenir ve boyut 2 olur. HashMap'te anahtarlar benzersizdir: aynı anahtarla ikinci put yeni bir çift eklemez, eski değerin üzerine yazar. Bu yüzden 101 numarası artık “Zeynep”i gösterir ve eşlemede 2 çift vardır. Olmayan bir anahtar (103) için get null döndürür.

Tür parametreleri bu kodda da koruma sağlar. ogr.put("101", "Ayşe") yazılsaydı derleyici anahtarın Integer değil String olduğunu görüp programı derlemezdi. Bu notta yazılan kendi veri yapılarımız da aynı biçimde, jenerik sınıflar olarak yazılır.

1.6İlkel olmayan veri yapıları

İlkel tipler tek bir sayı, tek bir karakter ya da tek bir mantıksal değer tutar. Gerçek programlar ise yüzlerce öğrenciyi, binlerce şehri, milyonlarca kelimeyi bir arada işler. Bu kesim, çok sayıda değeri belirli bir düzende bir arada tutan yapıları tanıtır.

1.6.1Karmaşık yapılar

İlkel tiplerden ve başka yapılardan kurulan yapılara ilkel olmayan (non-primitive) veri yapıları denir. Bu yapılar, öğeleri arasında kurdukları ilişkiye göre kabaca şöyle gruplanır:

• Sıralı: diziler ve listeler. Öğeler bir sıra içindedir; her öğenin bir öncesi ve bir sonrası vardır.
• Bağlantılı: bağlı listeler. Sıra, öğeleri birbirine bağlayan referanslarla kurulur.
• Hiyerarşik: ağaçlar. Her öğenin bir üstü ve birden çok altı olabilir.
• Ağ: çizgeler. Her öğe istediği kadar başka öğeyle ilişkili olabilir.
• İndislenmiş: hash tabloları. Öğenin yeri, kendi anahtarından hesaplanır.
• Bunların yanında kümeler, eşlemeler ve daha birçok yapı.

İlkel olmayan yapıların üç ortak özelliği vardır. Birincisi, karmaşıktırlar ve birden fazla ilkel değeri, hatta farklı tiplerde değerleri bir arada içerebilirler. İkincisi, çoğu dinamik boyutludur: program çalışırken öğe eklendikçe büyür, çıkarıldıkça küçülür. Diziler bu kuralın istisnasıdır; Java'da bir dizinin uzunluğu oluşturulduğu anda belirlenir ve sonradan değişmez. Üçüncüsü, her yapı belirli işlemler için özelleştirilmiştir: biri en son ekleneni hızla verir, öteki bir anahtarı hızla bulur, bir başkası iki nokta arasındaki yolu bulmaya elverişlidir.

1.6.2Aynı dört değer, sekiz yapı

Yapıların farkını görmenin en iyi yolu, aynı verinin her birinde nasıl durduğuna bakmaktır. Şekil 1.5, 7, 2, 9, 5 değerlerini sekiz farklı düzende gösterir. Her birinin güçlü ve zayıf yönü farklıdır.

(a) Dizi. Değerler ardışık hücrelerde, 0'dan 3'e kadar indislerle durur. a[2] tek adımda 9'u verir; 1.2.3'teki adres hesabı sayesinde indisle erişim O(1)'dir. Boyut ise sabittir: beşinci bir değer için yer yoktur.

(b) Bağlı liste. Her değer ayrı bir düğümdedir ve her düğüm bir sonrakini gösterir: 7 → 2 → 9 → 5 → null. Listenin başını gösteren tek bir referans yeterlidir. Yeni bir düğüm eklemek için yalnız birkaç okun yönü değişir, boyut esnektir. Bedeli şudur: i. öğeye gitmek için baştan başlayıp i ok izlemek gerekir, bu da O(n)'dir.

(c) Yığın. Değerler üst üste konmuştur; 7 en alttadır, en son eklenen 5 en üsttedir. Ekleme (push) ve çıkarma (pop) yalnız üstten yapılır. Bu düzene LIFO (Last-In, First-Out: son giren ilk çıkar) denir. Bir sonraki pop 5'i verir.

(d) Kuyruk. Değerler geliş sırasıyla dizilmiştir: önde 7, arkada 5. Yeni öğe arkadan girer, çıkış önden yapılır. Bu düzene FIFO (First-In, First-Out: ilk giren ilk çıkar) denir. Bir sonraki çıkarma 7'yi verir. Yığın ile kuyruk aynı dört değeri tam ters sırada bırakır.

(e) Ağaç. Değerler bir hiyerarşi içindedir. 7 köktür; 2 ve 9 onun çocuklarıdır; 5, 2'nin çocuğudur. Çocuğu olmayan 9 ve 5 birer yapraktır. Kökten herhangi bir düğüme tek bir yol vardır.

(f) Çizge. Değerler düğümlerdir ve aralarındaki çizgiler kenarlardır. Şekildeki çizgede 7, 2, 9 ve 5'in her biri iki ya da üç düğüme bağlıdır. Ağaçtan farkı, ilişkinin hiyerarşik olmak zorunda olmamasıdır: bir düğüme birden çok yoldan ulaşılabilir, kenarlar döngü oluşturabilir. Bu tür ilişkiye birçoğa-birçok ilişki denir.

(g) Hash tablosu. Değerler 5 hücreli bir diziye, yerleri bir hash fonksiyonu h(k) ile hesaplanarak konmuştur. Şekildeki fonksiyon h(k) = k mod 5'tir, yani değerin 5'e bölümünden kalan. 5 mod 5 = 0, 7 mod 5 = 2, 9 mod 5 = 4'tür. 2 mod 5 de 2'dir, ama 2 numaralı hücrede 7 zaten vardır. İki değerin aynı hücreye düşmesine çakışma (collision) denir ve hash tabloları çakışmaları çözmek için ek kurallar kullanır. Çakışmalar az olduğunda bir değeri aramak, hücresini hesaplayıp oraya bakmaktan ibarettir; bu yüzden hash tablosunda arama ortalama O(1)'dir.

(h) Küme. Bir küme yalnız tekil öğeler tutar ve öğelerin sırası önemli değildir. {7, 2, 9, 5} kümesine 7'yi yeniden eklemek kümeyi değiştirmez: {7, 2, 9, 5} ∪ {7} yine aynı kümedir. Kümenin yakın akrabası olan eşleme ise her tekil anahtara bir değer bağlar (anahtar → değer).

1.7Soyut veri tipleri ve veri yapıları

“Yığın” denince iki farklı şey kastedilebilir. Birincisi bir davranıştır: öğeler üstten eklenir, üstten çıkar, son giren ilk çıkar. İkincisi bu davranışın bellekte kurulmuş hâlidir: belirli bir dizi, belirli bir indis değişkeni, belirli bir kod. Bu iki düzeyi birbirinden ayırmak, veri yapılarını anlamanın ve tasarlamanın anahtarıdır.

1.7.1Ne ile nasıl ayrımı

Listeler, yığınlar, kuyruklar, kümeler, eşlemeler ve çizgeler birer soyut veri tipidir. Hepsi bir davranış tarifidir. Bağlı listeler, diziler ve komşuluk matrisleri ise birer veri yapısıdır; soyut veri tiplerini bellekte kurmanın yollarıdır. ADT davranışa, veri yapısı bellek ve performans ayrıntılarına odaklanır.

Bir benzetme ayrımı netleştirir. Bir arabanın sürücüye sunduğu şey direksiyon, gaz ve fren pedalıdır; sürücü bu “arayüzü” bilerek her arabayı kullanabilir. Motorun benzinli mi elektrikli mi olduğu, frenin hangi mekanizmayla çalıştığı sürücüyü ilgilendirmez. Pedallar ve direksiyon ADT'ye, motor ve fren mekanizması veri yapısına karşılık gelir. Aynı arayüz bambaşka mekanizmalarla sağlanabilir; sürücü bunu fark etmeden araba değiştirebilir.

Şekil 1.6 bu ilişkiyi liste üzerinde gösterir. Liste ADT'si dört işlem sunar: ekle, sil, i. öğeyi al ve boyutu söyle. Bu dört işlem bir diziyle de, bir bağlı listeyle de sağlanabilir. Kullanıcı açısından iki gerçekleme aynı şeyi yapar. Farkları maliyettedir: dizide al(i) anında biter ama başa ekleme bütün öğeleri kaydırır; bağlı listede başa ekleme anında biter ama al(i) listeyi baştan gezer. Tablo 1.5 iki kavramı karşılaştırır.

1.7.2ADT'den Java'ya: arayüz

Java, “ne” ile “nasıl” ayrımı için iki ayrı dil öğesi sunar. Arayüz (interface), bir ADT'nin sözleşmesini yazmanın aracıdır: hangi metotların bulunacağını, her metodun ne aldığını ve ne döndürdüğünü söyler, ama metotların gövdesini içermez. Yığın ADT'sinin arayüzü şöyledir:

public interface Yigin<E> {
  int size();         // öğe sayısı
  boolean isEmpty();  // boş mu?
  void push(E e);     // üste ekle
  E top();            // üsttekini döndür
  E pop();            // üsttekini çıkar
}

Arayüz beş işlemi tanımlar. size() yığındaki öğe sayısını, isEmpty() yığının boş olup olmadığını döndürür. push(e), e öğesini üste ekler. top() üstteki öğeyi yığından çıkarmadan döndürür; pop() ise üstteki öğeyi çıkarır ve döndürür. Arayüz jeneriktir: E, yığında tutulacak öğelerin tipidir ve arayüz her öğe tipi için bir kez yazılır.

Arayüzde hiçbir alan ve hiçbir gövde yoktur. Öğelerin bir dizide mi, bağlı düğümlerde mi tutulacağı burada söylenmez. Bu bilgiyi bir sınıf verir: implements Yigin<E> diyen bir sınıf, arayüzdeki beş metodun hepsini gövdeleriyle yazmak zorundadır. Kısacası interface ADT'nin sözleşmesidir ve ne yapılacağını söyler; class ise veri yapısıdır ve nasıl yapılacağını söyler. Aynı ADT'nin birden çok gerçeklemesi (implementation) olabilir.

Yığını kullanan koda istemci kodu denir. Şekil 1.7 istemcinin yalnız arayüze bağlı olduğunu gösterir. İstemci, yığını şöyle oluşturur:

Yigin<Integer> y = new DiziYigin<>(10);

Değişkenin tipi arayüzdür (Yigin<Integer>), oluşturulan nesne ise belirli bir sınıftandır (DiziYigin). Bu satırdan sonraki bütün kod y.push(…), y.pop() gibi yalnız arayüzdeki işlemleri kullanabilir. Gerçeklemeyi değiştirmek, örneğin dizi yerine bağlı düğümler kullanan bir yığına geçmek için yalnız bu satır değişir: new DiziYigin<>(10) yerine new BagliYigin<>() yazılır. İstemci kodunun geri kalanı aynı kalır.

1.7.3Bir gerçekleme: DiziYigin

Yığın ADT'sini bir diziyle kurmanın fikri basittir. Öğeler dizinin başından itibaren sırayla yerleştirilir: ilk eklenen 0. hücreye, ikincisi 1. hücreye. Yığının üstü, dolu olan son hücredir. Bu hücrenin indisini tutan bir değişken yeterlidir; ona t (top) diyelim.

public class DiziYigin<E> implements Yigin<E> {
  private E[] veri;         // öğeler
  private int t = -1;       // üst öğenin indisi
  public DiziYigin(int kapasite) {
    veri = (E[]) new Object[kapasite];
  }
  public int size() { return t + 1; }
  public boolean isEmpty() { return t == -1; }
  public E top() {
    if (isEmpty()) return null;
    return veri[t];
  }
  // push ve pop
}

Sınıfı satır satır okuyalım.

• implements Yigin<E>: sınıf yığın sözleşmesini kabul eder. Sınıfın tür parametresi E, arayüzün E'sine aktarılır.
• private E[] veri: öğelerin tutulduğu dizi. private anahtar sözcüğü bu alana sınıf dışından erişilmesini engeller. İstemci diziyi doğrudan değiştiremez; yalnız arayüzdeki işlemleri kullanabilir. Böylece yığının kuralı (yalnız üstten erişim) korunur.
• private int t = -1: üst öğenin indisi. Boş yığında üst öğe yoktur; bu durumu −1 gösterir, çünkü −1 geçerli bir dizi indisi değildir.
• Kurucu metot, istenen kapasitede bir dizi oluşturur. Java'da new E[kapasite] yazılamaz: tür parametresi program çalışırken bilinmez ve Java bilinmeyen tipte dizi oluşturamaz. Bu yüzden bir Object dizisi oluşturulup (E[]) dönüşümüyle veri'ye atanır. Derleyici bu satır için “denetlenmemiş dönüşüm” uyarısı verir; dizi yalnız sınıfın içinde kullanıldığı ve içine yalnız E tipinde öğe konduğu için bu güvenlidir.
• size(): öğeler 0'dan t'ye kadar olan hücrelerdedir, yani t + 1 tanedir. Boş yığında −1 + 1 = 0 verir.
• isEmpty(): t == -1 ise yığın boştur.
• top(): yığın boşsa döndürülecek öğe yoktur ve null döner. Değilse üstteki öğe, veri[t] döner. Öğe yığından çıkarılmaz; t değişmez.

Şekil 1.8 bir ara durumu gösterir. Önce 5, sonra 8 eklenmiştir. t 1'dir ve 8'in bulunduğu hücreyi gösterir. Dizinin 2 ve 3 numaralı hücreleri boştur ve yeni öğeleri bekler.

1.7.4push ve pop

Sınıfın eksik kalan iki metodu yığını değiştiren işlemlerdir. Sunum, bu iki metodu onları kullanan kısa bir istemci koduyla birlikte verir:

public void push(E e) {
  if (size() == veri.length)
    throw new IllegalStateException("dolu");
  veri[++t] = e;
}
public E pop() {
  if (isEmpty()) return null;
  E e = veri[t];
  veri[t--] = null;     // GC için boşalt
  return e;
}
y.push(5); y.push(8);
System.out.println(y.pop());
y.push(3);

push(e). Önce dizinin dolu olup olmadığı denetlenir: öğe sayısı dizinin uzunluğuna eşitse yeni öğeye yer yoktur. Bu durumda metot IllegalStateException fırlatır; kapasitesi sabit bir yığına dolu iken eklemeye taşma denir. Yer varsa veri[++t] = e satırı çalışır. ++t önce t'yi bir artırır, sonra artırılmış değeri indis olarak kullanır. Yani önce artırılır, sonra yazılır. veri[t++] = e yazılsaydı öğe eski üstün üzerine yazılırdı.

pop(). Boş yığından çıkarılacak öğe yoktur; metot bu durumda null döndürür. Yığın boş değilse üstteki öğe e'ye alınır. veri[t--] = null satırı iki iş yapar: önce t'nin eski değeriyle gösterilen hücreye null yazar, sonra t'yi bir azaltır. Hücreyi boşaltmanın nedeni çöp toplayıcıdır. Hücre eski öğeyi göstermeye devam etseydi, istemci o öğeyle işini bitirmiş olsa bile nesne bellekten temizlenemezdi. Son olarak saklanan öğe döndürülür.

1.7.5Kod izleme: DiziYigin

İstemci kodu kapasitesi 4 olan boş bir DiziYigin üzerinde çalışır: push(5), push(8), pop()'un sonucunu yazdırma ve push(3). Tablo 1.6 her adımda çağrı yığınını, t'yi ve diziyi verir. Satır numaraları sunumdaki kod bloğuna göredir: push 1–5, pop 6–11, istemci 12–14.

İzlemede üç noktaya dikkat etmek gerekir. Birincisi, her metot çağrısı çağrı yığınında yeni bir çerçeve açar (“main | push(5)”) ve metot bitince bu çerçeve kapanır; 1.4.1'deki bellek modeli burada iş başındadır. İkincisi, pop en son eklenen 8'i döndürür; 5 eklenen ilk öğedir ve yerinde kalır (LIFO). Üçüncüsü, push(3) az önce boşaltılan 1 numaralı hücreyi yeniden kullanır. Dizi tabanlı yığında öğeler hiçbir zaman kaydırılmaz; yalnız t ileri geri hareket eder.

Örneğin son adımı bir tasarım kararını gösterir: bu sınıf boş yığından çıkarmayı (alt taşma, underflow) bir hata olarak değil, null döndürerek bildirir. Bazı kütüphaneler bu durumda istisna fırlatır. İki yol da kullanılır, ama null döndüren bir yığında istemci, dönen değeri kullanmadan önce null olup olmadığını denetlemelidir. Ayrıca yığına öğe olarak null konmuşsa, pop'un döndürdüğü null'ın “yığın boştu” mu yoksa “üstte null vardı” mı anlamına geldiği ayırt edilemez.

1.7.6İşlemlerin maliyeti

Bir veri yapısının işlemlerini karşılaştırmak için her işlemin ne kadar iş yaptığına bakılır. Bunun için yaygın olarak büyük O (Big O) gösterimi kullanılır. Bu gösterimin ayrıntısı burada gerekmez; şu iki anlamı bilmek yeterlidir. O(1), işlemin yaptığı adım sayısının yapıdaki öğe sayısından bağımsız, sabit olduğunu söyler. O(n) ise adım sayısının öğe sayısı n ile orantılı büyüdüğünü söyler: öğe sayısı iki katına çıkınca iş de yaklaşık iki katına çıkar.

Tablo 1.7 bütün işlemlerin O(1) olduğunu söyler. Gerekçesi kodun kendisindedir. size bir toplama, isEmpty bir karşılaştırma, top bir karşılaştırma ve bir dizi erişimi yapar. push bir karşılaştırma, bir artırma ve bir yazma yapar. pop bir karşılaştırma, bir okuma, bir yazma ve bir azaltma yapar. Hiçbir metotta döngü yoktur ve dizi erişimi 1.2.3'teki adres hesabıyla tek adımda yapılır. Yığında 3 öğe de olsa 3 milyon öğe de olsa her işlem aynı sayıda adımda biter.

Bellek ise kapasiteyle orantılıdır: kapasitesi N olan bir yığın, içinde kaç öğe olursa olsun N hücrelik bir dizi ayırır. Bu, dizi tabanlı gerçeklemenin bedelidir. Kapasite sabittir ve dolunca push hata fırlatır. Kapasite gereğinden büyük seçilirse bellek boşa harcanır, küçük seçilirse yığın erken dolar. Bu sorunu çözmenin iki yolu vardır: dizi dolunca daha büyük bir diziye taşınmak ya da diziden vazgeçip bağlı düğümler kullanmak. İki yolda da yığın ADT'si değişmez; yalnız onu gerçekleyen sınıf değişir. 1.7.1'deki ayrımın pratikteki kazancı budur.

1.8Verilerin düzenlenmesi ve yapı seçimi

Bir veri yapısı seçmeden önce verilerin birbiriyle nasıl bir ilişki içinde olduğunu görmek gerekir. Öğeler birbirinden bağımsız mı, bir sıra mı oluşturuyor, bir hiyerarşi mi kuruyor, yoksa karmaşık bir ağ mı? Bu sorunun cevabı, uygun yapıların listesini büyük ölçüde daraltır.

1.8.1Dört düzen biçimi

Şekil 1.10 dört temel düzeni gösterir. Tablo 1.8 her birinin öğeler arasında kurduğu ilişkiyi ve gündelik hayattan bir örneğini verir.

Konumsal olmayan düzende öğeler arasında bir ilişki yoktur. Sınıftaki öğrenciler bir topluluk oluşturur, ama “Ayşe'den sonraki öğrenci” diye bir kavram yoktur. Bu düzende sorulan sorular üyelikle ilgilidir: Mehmet bu sınıfta mı? Kaç öğrenci var? Küme ve eşleme bu düzene uyan yapılardır.

Sıralı düzende her öğenin en çok bir öncülü ve en çok bir ardılı vardır; ilişki bire-birdir. Kantinde sıra bekleyen öğrencilerde herkesin önünde ve arkasında birer kişi vardır, yalnız ilk ve son kişi bu kuralın uç noktalarıdır. Dizi, liste, bağlı liste, yığın ve kuyruk sıralı yapılardır. Aralarındaki fark, sıranın hangi uçlarından ekleme ve çıkarma yapılabildiğidir.

Ağaç düzeninde her öğenin en çok bir üstü (ebeveyni) vardır, ama birden çok altı (çocuğu) olabilir; ilişki bire-birçoktur. Aile ağacında, bir şirketin örgüt şemasında ya da bilgisayardaki klasör yapısında bu düzen görülür. Her klasörün tek bir üst klasörü vardır, ama içinde birçok alt klasör bulunabilir.

Çizge düzeninde her öğe istediği kadar öğeyle ilişkili olabilir; ilişki birçoğa-birçoktur. Yol haritasında bir şehirden birçok şehre yol gider ve her şehre birçok şehirden ulaşılır. Sosyal ağlardaki arkadaşlık ilişkileri ve bilgisayar ağları da çizgedir. Çizge en genel düzendir: sıralı düzen ve ağaç, çizgenin kısıtlanmış özel durumlarıdır.

1.8.2Veri yapısı seçimi

Doğru yapıyı seçmek için önce verilerin nasıl kullanılacağı anlaşılmalıdır. Seçimde şu sorular belirleyicidir.

• Veri yapısı başlangıçta tamamen doldurulabilir mi? Bütün veriler baştan biliniyorsa (örneğin bir yılın on iki ayının adları) yapı bir kez kurulur ve sonra yalnız okunur. Veriler zamanla geliyorsa yapının büyüyebilmesi gerekir.
• Veri yapısından öğeler silinebilir mi? Silme gerekmiyorsa yapı çok daha basit tutulabilir. Sık silme varsa, silinen öğenin bıraktığı boşluğu ucuza kapatabilen bir yapı gerekir.
• Ekleme sırasının önemi var mı? Öğeler geliş sırasıyla işlenecekse kuyruk, en son gelen önce işlenecekse yığın uygundur. Sıra önemsizse küme ya da eşleme düşünülebilir.
• Veri yapısındaki öğeler sıralanabilir mi? Öğeler büyüklüğe ya da alfabeye göre sıralanabiliyorsa, 1.2.1'deki ikiye bölerek arama gibi hızlı yöntemler kullanılabilir.
• Öğeler belirli bir sırayla mı işlenir, yoksa rastgele erişim de gerekli mi? “5. öğeyi ver” gibi konuma göre erişim sık gerekiyorsa dizi; yalnız baştan sona gezinmek yetiyorsa bağlı liste de iş görür.

Bu soruların ortak bir sonucu vardır: durum değişmeyecekse statik (static) yapılar, sık ekleme ve silme varsa dinamik yapılar tercih edilir. Statik bir yapı, örneğin sabit boyutlu bir dizi, bir kez kurulur ve en hızlı erişimi sağlar. Dinamik bir yapı, örneğin bağlı liste, değişime uyum sağlar ama erişimde bir miktar yavaştır.

Şekil 1.11 bu soruları bir akış hâlinde toplar. Akış kesin bir kural değil, bir başlangıç noktasıdır. Gerçek problemlerde birden çok soruya “evet” denebilir ve bu durumda birden çok yapı birlikte kullanılır.

1.9Temel veri yapılarına genel bakış

Önceki kesimlerde tek tek değinilen temel veri yapıları Tablo 1.9'de bir arada verilmiştir. Tablo her yapının temel fikrini ve tipik kullanımlarını özetler.

Tablodaki kullanımların her birinin ardında yapının temel özelliği yatar. Birkaçını açalım.

Dizi öteki yapıların temelidir. Yığın, kuyruk, hash tablosu ve öncelikli kuyruk çoğu zaman içeride bir diziyle kurulur. Bir resim, bir oyun tahtası ya da bir tablo, iki boyutlu dizi (matris) olarak saklanır.

Bağlı liste, öğe sayısı sürekli değişen ve sık sık başa ya da araya ekleme yapılan durumlara uyar. Bir müzik çalarda çalma listesine şarkı eklemek ya da çıkarmak, öteki şarkıları yerinden oynatmadan yapılır.

Yığın, “en son yapılanı ilk geri al” mantığının yapısıdır. Bir metin düzenleyicide her işlem yığına konur; geri al komutu üstteki işlemi çıkarıp tersini uygular. 1.4.1'deki çağrı yığını da metot çağrılarını aynı kuralla yönetir. Parantez kontrolünde her açılan parantez yığına konur ve her kapanan parantez üstteki açılışla eşleşmelidir.

Kuyruk, adil sıranın yapısıdır. Yazıcıya gönderilen belgeler, sunucuya gelen istekler ve bir işletim sisteminde çalışmayı bekleyen görevler geliş sırasıyla işlenir. Genişlik öncelikli arama (breadth-first search, kısaca BFS) da sıradaki düğümü bir kuyruktan alır.

Ağaç, hiyerarşinin yapısıdır. Bilgisayardaki klasörler, bir web sayfasının HTML öğeleri (tarayıcılarda bu ağaca DOM, Document Object Model denir) ve veritabanlarının hızlı arama için kullandığı indisler ağaçtır.

Öncelikli kuyruk, geliş sırasına değil önceliğe göre çıkarma yapar. Acil serviste hastalar geliş sırasıyla değil, durumlarının ağırlığına göre muayene edilir. Bu yapı genellikle heap denen özel bir ağaçla kurulur.

Eşleme ve hash tablosu, bir anahtardan değere hızla ulaşmanın yoludur. Öğrenci numarasından öğrenci kaydına, bir kelimeden metinde kaç kez geçtiğine ulaşmak tipik kullanımlardır. Bir web tarayıcısının önbelleği de adres → sayfa içeriği eşlemesidir.

Küme, tekrarları ayıklamanın ve “bu öğe var mı?” sorusunu hızla cevaplamanın yapısıdır. İki kümenin birleşimi ve kesişimi gibi matematiksel işlemler de doğrudan desteklenir.

Çizge, en genel ilişkileri modeller. Bir harita uygulaması şehirleri ya da kavşakları düğüm, yolları kenar olarak tutar ve iki nokta arasındaki en kısa yolu bu çizge üzerinde arar. Kenarlara mesafe gibi sayılar yazıldığında çizge ağırlıklı çizge adını alır.

1.10Sık yapılan hatalar

Bu notta tek tek ele alınan hatalar, Tablo 1.10'te bir arada verilmiştir. Çoğunun kaynağı aynıdır: bir değişkenin değeri mi yoksa bir nesneye referans mı tuttuğunu gözden kaçırmak ya da bir işlemin sonucunu belirleyen tipi yanlış yerde aramak.

1.11Özet

• Dijital veri, metin, sayı, görüntü ve sesin 0 ve 1'lerle temsil edilmiş biçimidir. Analog sinyal ADC ile sayılara, sayılar DAC ile yeniden sinyale çevrilir. n bit 2ⁿ değer temsil eder. Metin karakter kodlamalarıyla (ASCII, Unicode), ondalıklı sayılar IEEE 754 ile, görüntü piksellerin RGB değerleriyle, ses örneklemeyle temsil edilir.
• Algoritma bir görevi yerine getiren adımların planıdır; veri yapısı verileri düzenleme ve saklama yoludur. Wirth'in deyişiyle: Algoritmalar + Veri Yapıları = Programlar. Her yapı bazı işlemleri ucuzlatıp bazılarını pahalılaştırır. Yapıların temel parçaları nesneler, diziler ve bağlantılardır.
• Veri tipi, değer kümesi ile işlemleri birlikte tanımlar. Java'nın sekiz ilkel tipi sabit boyutludur; sınır aşılınca değer sarar. İki int'in bölümü int'tir. Tip güvenliği, tiplere aykırı işlemleri derleme zamanında yakalar.
• Java'da yerel değişkenler çağrı yığınındaki çerçevelerde, nesneler heap bellekte durur. İlkel değişken değeri, referans değişken adresi tutar. = ilkel tipte değeri, referans tipte adresi kopyalar; iki referans aynı nesneyi gösterebilir (takma ad). Java parametreleri değerle geçirir. Erişilemeyen nesneleri çöp toplayıcı temizler.
• Jenerikler (Kutu<T>) her referans tipi için tek bir sınıf yazmayı ve tür hatalarını derleme zamanında yakalamayı sağlar. Tür parametresi ilkel olamaz: int yerine Integer kullanılır ve dönüşümü otomatik kutulama yapar. Java koleksiyonları jeneriktir.
• Soyut veri tipi ne yapılacağını (davranışı), veri yapısı nasıl yapılacağını (bellek düzenini) belirler. Java'da ADT bir arayüzle, veri yapısı onu gerçekleyen bir sınıfla yazılır. İstemci arayüz tipinde değişken kullanırsa gerçeklemeyi değiştirmek tek satırlık iştir.
• DiziYigin, yığını bir dizi ve üst indis t ile kurar: boş yığında t = −1, size() = t + 1. push önce artırıp sonra yazar, pop önce okuyup sonra hücreyi boşaltır. Bütün işlemler O(1)'dir; bellek kapasiteyle orantılıdır ve kapasite dolunca push hata fırlatır.
• Veriler konumsal olmayan, sıralı, ağaç ve çizge biçiminde düzenlenir. Yapı seçimini erişim biçimi, ekleme ve silme sıklığı, sıra ihtiyacı ve ilişki türü belirler; durağan veride statik, sık değişen veride dinamik yapılar seçilir.

1.12Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• dijital veri digital data
• algoritma algorithm
• veri yapısı data structure
• veri tipi data type
• ilkel tip primitive type
• ilkel olmayan non-primitive
• referans reference
• null null
• heap bellek heap memory
• çağrı yığını call stack
• çerçeve stack frame
• sığ kopya shallow copy
• değiştirilemez immutable
• jenerik generic
• jenerikler generics
• otomatik kutulama autoboxing
• kutudan çıkarma unboxing
• koleksiyon collection
• soyut veri tipi abstract data type (ADT)
• arayüz interface
• dizi array
• indis index
• kapasite capacity
• bağlı liste linked list
• düğüm node
• yığın stack
• üst top
• taşma overflow
• alt taşma underflow
• kuyruk queue
• ilk giren ilk çıkar FIFO
• ağaç tree
• öncelikli kuyruk priority queue
• eşleme map
• hash tablosu hash table
• hash fonksiyonu hash function
• çakışma collision
• küme set
• çizge graph
• statik dizi static array
• büyük O Big O

1.13Kendini Dene

1. 1000 farklı değeri temsil etmek için en az kaç bit gerekir? 200 sayısı sekiz bitle nasıl yazılır ve Java'da (byte) 200 ifadesi hangi değeri verir?

   Cevap

   9 bit 2⁹ = 512 değer verir, yetmez; 10 bit 2¹⁰ = 1024 değer verir. En az 10 bit gerekir. 200 = 128 + 64 + 8 olduğu için 11001000 yazılır. byte işaretlidir ve en çok 127 tutar; en soldaki bit 1 olduğu için bu dizi negatif okunur: 200 − 256 = −56.

2. int a = 9; için a / 4 * 4 ve a * 4 / 4 ifadeleri ne verir? Neden farklıdır?

   Cevap

   İlki 8, ikincisi 9 verir. İşlemler soldan sağa yapılır. İlkinde 9 / 4 tam sayı bölmesiyle 2 olur, ondalık kısım kaybolur; 2 · 4 = 8. İkincisinde önce 9 · 4 = 36 hesaplanır, sonra 36 / 4 = 9 tam bölünür ve kayıp olmaz.

3. Aşağıdaki satırlardan sonra r ve r2 hangi dizileri gösterir?

   int[] r = {3, 4, 5};
   int[] r2 = r;
   r2[2] = r2[0] + r2[1];
   r2 = new int[]{0, 0, 0};
   r2[0] = 1;

   Cevap

   r: [3, 4, 7], r2: [1, 0, 0]. İkinci satır yalnız referansı kopyalar; üçüncü satır ortak dizinin 2. hücresine 3 + 4 = 7 yazar, bu yüzden r da değişir. Dördüncü satır r2'yi yeni bir diziye yöneltir; beşinci satır yalnız bu yeni diziyi değiştirir.

4. StringBuilder sb = new StringBuilder("ab"); StringBuilder sb2 = sb; sb2.append("c"); satırlarından sonra sb neyi içerir? StringBuilder yerine String ve append yerine sb2 = sb2 + "c" kullanılsaydı ne değişirdi?

   Cevap

   sb "abc" içerir. StringBuilder değiştirilebilir bir nesnedir; sb ve sb2 aynı nesneyi gösterir ve append o nesnenin içeriğini değiştirir. String ise değiştirilemez: sb2 + "c" yeni bir nesne oluşturur ve atama yalnız sb2'nin okunu ona çevirir. Bu durumda sb "ab" olarak kalırdı.

5. Kutu<Double> d = new Kutu<>(); d.koy(2.5); satırlarından sonra double x = d.al() * 2; hangi değeri verir? d.koy(3); satırı derlenir mi?

   Cevap

   x 5.0 olur: 2.5 otomatik olarak bir Double'a konmuş, çarpmada kutudan çıkarılmıştır. d.koy(3) derlenmez. 3 bir int'tir ve Java onu yalnız Integer'a kutulayabilir; Integer ise Double değildir. Doğrusu d.koy(3.0)'dır.

6. Kapasitesi 3 olan boş bir DiziYigin<Integer> üzerinde sırayla push(4), push(6), pop(), push(1), top(), pop(), push(2), push(8) çağrılıyor. Değer döndüren çağrılar ne döndürür? Sonda t ve veri nedir? Ardından push(5) çağrılırsa ne olur?

   Cevap

   Dönen değerler sırasıyla 6, 1, 1'dir: ilk pop 6'yı, top 1'i çıkarmadan, ikinci pop 1'i döndürür. Sonra 2 ve 8 eklenir. Son durum t = 2, veri = [4, 2, 8]'dir; dizi doludur. push(5)'te size() = 3 = veri.length olduğu için IllegalStateException fırlatılır.

7. Kuyruk, dizi, eşleme, bağlı liste, küme ve komşuluk matrisi kavramlarından hangileri soyut veri tipi, hangileri veri yapısıdır?

   Cevap

   Kuyruk, eşleme ve küme soyut veri tipleridir: hangi işlemlerin yapılacağını tarif ederler. Dizi, bağlı liste ve komşuluk matrisi veri yapılarıdır: verilerin bellekte nasıl tutulacağını belirlerler. Örneğin kuyruk ADT'si bir diziyle de bir bağlı listeyle de kurulabilir; çizge ADT'si bir komşuluk matrisiyle saklanabilir.

8. Aşağıdaki gereksinimler için hangi yapı uygundur? (a) Bir çağrı merkezinde bekleyen arayanlar, (b) bir şirketin örgüt şeması, (c) bir web sitesini ziyaret eden farklı kullanıcıların sayısı, (d) derslerin ön koşul ilişkileri.

   Cevap

   (a) Kuyruk: arayanlar geliş sırasıyla bağlanır (FIFO). (b) Ağaç: her çalışanın tek bir yöneticisi, her yöneticinin birçok çalışanı vardır (bire-birçok). (c) Küme: aynı kullanıcı birden çok kez ziyaret etse de bir kez sayılmalıdır; kümenin boyutu cevaptır. (d) Çizge: bir dersin birden çok ön koşulu, bir dersin de birden çok sonrakisi olabilir (birçoğa-birçok).

9. 10, 24, 3 ve 17 değerleri 7 hücreli bir tabloya h(k) = k mod 7 ile yerleştiriliyor. Hangi hücrelere düşerler? Aynı değerler 5 hücreli tabloya k mod 5 ile yerleştirilseydi ne olurdu?

   Cevap

   Mod 7'de dördü de 3 numaralı hücreye düşer: 10 = 7 + 3, 24 = 21 + 3, 3 = 0 + 3, 17 = 14 + 3. İlkinden sonraki her ekleme bir çakışmadır ve arama artık sabit sürede yapılamaz. Mod 5'te hücreler 0, 4, 3, 2 olur ve hiç çakışma yoktur. Hash fonksiyonunun değerleri hücrelere dengeli dağıtması, tablonun hızı için belirleyicidir.

10. Bir istemci Yigin<String> y = new DiziYigin<>(100); satırıyla başlayan 500 satırlık bir program yazmıştır. Yığının kapasite sınırından kurtulmak için bağlı düğümler kullanan BagliYigin sınıfına geçmek istiyor. Kaç satır değişir? Değişken DiziYigin<String> tipinde tanımlanmış olsaydı ne olurdu?

    Cevap

    Yalnız ilk satır değişir: new DiziYigin<>(100) yerine new BagliYigin<>() yazılır. Program yalnız arayüzdeki beş işlemi kullandığı için geri kalan satırlar olduğu gibi çalışır. Değişken sınıf tipinde tanımlansaydı en azından tip bildiriminin de değişmesi gerekirdi. Program DiziYigin'e özgü bir metot kullanmışsa o satırlar da yeniden yazılmak zorunda kalırdı.

1.14İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Bölüm 1 ve 2: Java'nın temel tiplerini, referanslarını, sınıf ve arayüzlerini ve jenerikleri bu nottaki yığın örneğine yakın kodlarla anlatır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 1.2 ve 1.3: veri soyutlamasını, API ile gerçekleme ayrımını ve jenerik yığın, kuyruk sınıflarını kısa, açık örneklerle işler.
• N. Wirth, Algorithms + Data Structures = Programs (1976): algoritma ile veri yapısının birlikte tasarlanması gerektiği fikrinin klasik kaynağıdır; ilk bölümü temel veri tiplerini ve yapılarını tarihsel bir bakışla anlatır.

1.15Kaynaklar

1. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
2. Oracle, Java SE 17 API Specification: java.lang.Integer, java.lang.String, java.util.ArrayList, java.util.HashMap ve java.util.HashSet belgeleri.
3. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.
4. N. Wirth, Algorithms + Data Structures = Programs, Prentice-Hall, 1976.

İlgili sayfalar: Bölüm 1 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.