Listeler (Bellek – Diziler)
LİSTELER
Liste sözcüğü aralarında bir biçimde öncelik-sonralık ya da altlık-üstlük ilişkisi bulunan veri öğeleri arasında kurulur[4]. Yada Aynı kümeye ait verilerin bellek üzerinde bir gösterici (pointer) yardımı ile birbirine bağlanması sonucu oluşturulan veri yapısıdır. Bu veri yapısındaki bütün elemanların ortak noktası kendi içlerinde bağlantı bilgisi içeren kendi türünden bir ya da daha fazla göstericiye sahip olmasıdır. Veri yapısı, kümedeki herhangi bir elemanın, kendisinden önce ve kendisinden sonra hangi elemanın bulunduğu bilgisi bu göstericilere değer vererek kurulur[5]. Dizilerin önemli bir özelliği boyutlarının zaman içinde sabit kalmasıdır. İki veya daha çok boyutlu dizilerde ise tabloların satır ve sütün sayısı değişmez. Yani, tablolar dikdörtgen şeklindedir. Böyle olunca bir dizinin fiziksel belleğe eşlenmesi basit bir çevirme işlemi ile yapılabilir (Şekil 1 ve Şekil 2). Bunun tersine, dinamik veri yapılarının boyutu da, şekli de süreç içinde değişir. Pratik uygulamalarda uğraştığımız verilerin boyutu değişken olabilir[1].
Belleğin dinamik olarak yönetilmesine örnek olarak; bir dizi tanımlamak istiyoruz ve bu dizinin boyutunu programın çalışma anında değiştirmek istiyoruz.(NOT: Diziler derleyici tarafından derleme aşamasında ele alınır. Bu yüzden çalışma anında dizi boyutlarını değiştirmek mümkün değildir). İşte bunu yapabilmenin yolu belleğin dinamik olarak kullanılmasından geçer. Bir dizinin boyutunu dinamik olarak arttırıp azaltmak kodu daha verimli kılar, belleği daha verimli kullanmamızı sağlar. Örneğin C dilinde belleğin dinamik olarak kullanılmasını sağlayan standart fonksiyonlar: malloc, realloc, calloc ve free fonksiyonlarıdır[3].
Şöyle bir örneklerde verilebilir: Bir bölgede yaşayan 0-2 yaş bebeklerin sayısını bulmak ve bu bebeklerle ilgili çeşitli verileri işlemek isteyen bir program için dinamik bir veri yapısı gerekir. Ya da bir görüntü içinde dikdörtgen şeklinde olmayan bir nesneyi, değişen satır veya sütün sayıları ile saklamak gerekebilir. Bu gibi durumlarda, verinin bellekte saklanabilmesi için uygun bir veri yapısına ihtiyaç olmasının yanında, bu veriye daha sonra nasıl erişileceği konusunda da yöntemler geliştirmek gerekir. Aşağıda, önce dinamik veri yapısı oluşturmak için geliştirilen imleç (pointer) kavramını, daha sonra da yaygın olarak kullanılan dinamik veri yapılarından olan bitişik ve bağlı listeleri göreceğiz[1].
1. İmleçler (Pointerler)
Dinamik veri yapısı oluşturmanın en temel kavramlarından birisi imleçlerdir. Bilgisayarlarda birçok fiziksel yer, nümerik adreslerle belirlenir (Şekil 3).
Nümerik değerli bir adres bilgisayarın belleğinde çok rahat saklanabilir. Eğer, bir veri grubunun adresi biliniyorsa, veri gayet kolay bulunabilir. O halde, verinin kendisi bellekteki bir hücrede saklandıktan sonra, o hücrenin adresi sayısal bir değer ile başka bir hücrede saklanabilir. Bu veriye erişmek için, önce verinin adresini saklayan hücreye, daha sonra da bu adresin yönlendirmesi ile verinin saklandığı hücreye erişilir. Bir bakıma, verinin adresini saklayan hücre verinin kendisinin saklandığı hücreyi işaret etmektedir. Bu sebepten dolayı, nümerik adresi saklayan, bu hücreye İngilizcede “işaret eden” anlamına gelen pointer adı verilmiştir[1].
İşaretçi (pointer), bellek alanındaki bir gözün adresinin saklandığı değişkendir. İşaretçilere, veriler değil de, o verilerin bellekte saklı olduğu belek gözlerinin başlangıç adresleri atanır[2].
İmleçler bilgisayar bilimlerinde pek çok değişik amaç için kullanılırlar. Örneğin, internetteki üstün metin (hypertext) komutlarını saklayan URL adresleri imleçten başka bir şey değildir. Tabii, URL’ler bilgisayarın ana belleğindeki bir yeri değil internetteki bir yeri gösterirler[1].
Günümüzde birçok programlama dili imleçlerin bildirimine (decleration), atanmasına (allocation) ve işlenmesine (manipulation) olanak sağlamaktadır. Bu tür dilleri kıllanan bir programcı, bilgisayar belleği içinde karmaşık ağlardan oluşabilecek veri yapıları kullanan algoritmalar tasarımlayabilir[1].
2. Bitişik Listeler
Liste içinde bulunan elemanları bellekte saklamanın en kolay yöntemi, listenin elemanlarını sıra ile bilgisayarın hafızasında ayrılan tek bir bitişik bloğa yerleştirmektir. Listenin elemanlarındaki karakter sayısının belli bir değeri aşamayacağı varsayılarak, listedeki her eleman için blokta belli sayıda hücre ayrılır ve liste elemanları sıra sıra kendileri için ayrılan hücrelerin içine yerleştirilirler. Elemanların karakter sayısını 8 ile sınırlasak, bu liste için oluşturulan bitişik bloğun içinde her eleman için 8 hücrelik bir alt blok ayırırız. Listedeki elemanların karakterlerini ASCII kodu ile bu hücrelere sıra sıra yerleştiririz. Bu tür listelere Bitişik Listeler (Cotiguous Lists) denir[1].
Örnek:
Aşağıda verilen isim listesini belleğe yerleştirelim.
Bir ismin içinde bulunan karakter sayısı 8’den daha az ise geri kalan hücreler boşluğa karşı gelen ASCII kodu ile doldurulur. Şekil 4’te gösterilen bitişik listede 8 adet isim saklamak için gereken bellek alanı 64 bitişik bellek hücresidir[1].
Bitişik listeler basit oldukları için birçok uygulamada rahatlıkla kullanılabilirler. Fakat, bu tür veri yapılarında listeye ekleme yapmak veya çıkarma yapmak sorun olur. Zira, listeden bir isim çıkarmak istediğimiz zaman bu isimden kalan boşluğu ortadan kaldırmak üzere listedeki geri kalan isimleri bu boşluğa doğru kaydırmamız gerekir. Listeye isim eklemesi ise daha da büyük bir sorundur. Zira, ekleme yapmak için bellekte ayrılmış bir alan mevcut olmayabilir. Bu tür problemleri gidermek için her bir ismi bellekte bitişik olan tek bir bloğa değil ayrı ayrı alanlara koymak gerekir[1].