in Veri Yapıları

Arrays – Diziler

 

Bu yazıda programlama dillerinde genelde ilk öğrendiğimiz yapı olan dizileri işleyeceğiz.

Diziler Nedir?

Diziler aynı türden verileri içeren yapılardır.Bir dizi oluşturduğumuzda, bellek kısmında ardışık olarak yer  tutarlar.Bu sayede art arda erişim kolaydır.Yani net bir tanım yapmak gerekirse; Diziler ardışık indis değerlerine sahip aynı tipte verilerin saklandığı veri yapısıdır.

Diğer veri yapılarına nazaran dizileri kullanmamızda çeşitli avantajlar bulunmaktadır.Diziler basit bir şekilde ifade edilirler,  bellekte fazla yer kaplamazlar ve kolay anlaşılırlar. Ayrıca indis değeriyle verilere erişimimiz daha kolay olmaktadır.Bu da daha büyük boyutlu dizilerde bizlere büyük kolaylık sağlamaktadır. Diziler birden fazla boyutlu olarak tanımlanabilir.Buna en iyi örnek matrislerin iki boyutlu dizi olarak tanımlanabilmesidir.

arr

Fakat ardışıklığın avantajlı olmadığı durumlarda olabilmektedir.Örneğin; Elimizde 1000 elemanlı bir sıralı dizi olsun ve ortasındaki indis değerine eleman ekleme işlemi yapacağımızı düşünelim.

Bu durumda 500 elemanı sağa kaydırmamız ve ortada bir elemanlık yer açmamız gerekir.Bu da veri yapılarının çeşitliliğinin temel nedenlerinden birisi aslında.Böyle bir işlem için dizileri kullanmak performans açısından pek mantıklı olmayacaktır.

Bir dizi tanımladığımızda dizinin kaç elemanlı olacağını başlangıçta belirleriz.Bu tür dizilere sabit diziler denmektedir.Eğer eklenecek eleman sayımız değişen bir değer olacaksa bu durumda dinamik dizilere başvurmalıyız.Dinamik diziler programlama dillerine göre tanımlama açısından farklılıklar göstermektedir.

  • C++ dilinde std::vector ile dinamik dizi ihtiyacımızı görebiliriz.
  • Java dilinde ise java.util paketi altında bulunan Vector sınıfı tarafından sağlanır.

Neden her işlem için dizileri kullanamayız?
Diziler işimizi hallediyor gibi görünüyor.O halde neden her veri için bunu kullanmayalım ki?
Dizilerin de bazı dezavantajları bulunuyor.Sıralı olmayan bir diziye yeni eleman ekleme işlemi O(1) sürede bitiyor.Bu olabilecek en hızlı işlem süresidir.Fakat dizi sıralı olmadığı için arama işlemi O(N) sürede bitirilecektir.Ayrıca hem sıralı hemde sıralı olmayan diziler içinde eleman silme işlemi O(N) sürede bitirilecektir.Çünkü silinen elemanın yerine diğer elemanlar birer birer kaydırılmalıdır.
Hem silme hem ekleme hem de arama işlemlerini mümkün olabilecek en hızlı O(1) sürede yapabilen bir veri yapısı işimizi en iyi görecek yapı olurdu. Fakat O(1) olmasa dahi O(log N) sürede işlemleri bitirebilmekte O(N) süreye kıyasla tabi ki daha verimlidir.Bu nedenle ileride diğer veri yapılarına da değinmiş olacağız.
Dizilerle ilgili bir diğer problem ise boyutlarının sabit bir şekilde tanımlanıyor olmasıdır.Genellikle program çalıştırıldıktan sonra ne kadar verinin saklanması gerektiğini bilemeyebiliyoruz. Eğer dizileri kullanmak istiyorsak önceden bunu ayarlamamız gerekiyor. Eğer yüksek bir alan ayırırsak çalışma zamanında ihtiyacımız olmayan bir alanı boşa harcamış olabiliriz.Aynı şekilde tahminimiz ihtiyaçtan az olursa da taşma(overflow) meydana geleceğinden hata ile karşılaşırız.Bu nedenle ihtiyaçlarıma göre diğer veri yapılarını da göz önünde bulundurmalıyız.
Bir ek olarak Java’da boyutu otomatik genişleyen ve temel yapısı dizi olan Vector sınıfına değinelim.Vector sınıfı bize ihtiyaca göre genişleyen bir dizi yapısı sunar.Fakat bu özellik tabiki performans açısından olumsuz bir etkiyle bize geri döner. Diziye ayrılan alan dolduğunda daha büyük boyutlu yeni bir dizi oluşturulur ve bu yeni diziye eski dizinin elemanları tek tek kopyalanır.

Bu tabloda diziler için yapılan işlemlerin Big O sürelerini görebilirsiniz.

Yöntem Big O Süresi
Linear Search O(N)
Binary Search O(log N)
Sıralı olmayan diziye eleman ekleme O(1)
Sıralı diziye eleman ekleme O(N)
Sıralı olmayan diziden eleman silme O(N)
Sıralı diziden eleman silme O(N)

Okuduğunuz için teşekkürler.Görüşmek üzere…

 

Yorum yaz

Comment