in Veri Yapıları

Lists – Listeler

 

Dizilerde, verilerimizin bellekteki  sıralı hali tanımlanma esnasında belirlenir. Ardışık dizi elemanlarımız aynı zamanda bellekte de ardışık bir şekilde yer tutar.Bu nedenle silme ve ekleme gibi işlemlerin, dizi elemanlarının yerlerinin kaydırılmasına sebep olacağına diziler  isimli yazımda değinmiştim.

Bu tür bir sorunla karşılaşmamak için “listeler” adında bir veri yapısına sahibiz.Listeler, farklı bellek bölgelerinde bulunan verilerin adres bağlantılarıyla birbirine bağlandığı veri yapılarıdır.Bu yapıda her bir eleman bir değer ve işaretçiye(pointer) sahiptir.

linked_list

 

Resimde de gördüğünüz gibi her bir verimize ait işaretçi diğer verinin değerine bağlıdır. Bu resimdeki her veriyi bellekte dağınık yapıda hayal edelim.Oklar(işaretçi) ile de verilerin birbirine bağlandığını görebilirsiniz.Sonuçta veriler fiziksel olarak ayrı konumlardadır.Fakat sıralı bir şekilde algılanıp işlem görmektedir.

Veri yapısı olarak listeleri tercih etmemiz durumunda dizilerde yaşadığımız veri eklemesi sonrası elemanları kaydırma sorunumuz olmayacaktır.Bunun sebebi, listelerdeki verilerin bellek bölgesinde zaten dağınık yapıda olup birbirlerine işaretçiler ile bağlı olmalarıdır.Yani listelere yeni bir veri eklememiz gerekirse, bu durumda işaretçinin sadece göstereceği değeri değiştiririz.Eklediğimiz verininde işaretçisini değiştirmeden önceki gösterilen yere bağlarız.Sanırım görsel açıdan daha anlaşılır olacaktır.

insertlist.svg

 

Ekleme işleminden bahsettiğimizde 3 durum elde ederiz:

  • Verinin öne eklenmesi
  • Verinin sona eklenmesi
  • Verinin istenilen bir yere eklenmesi

Bu 3 durumda da belirtilen şekilde birbirine bağlama işlemi yapılır. Son verimizin işaretçisi null değer alır.Yani bir yeri göstermemektedir.İlk verinin değerine ise dışarıdan bir işaretçi ile erişilir.

Bağlı listelerin(Linked Lists) avantajlarını sayacak olursak;

  • Boylarının sabit değil dinamik olarak büyüyüp küçülebilmesi,
  • Birden çok veri yapısını barındırabilmesi,
  • Liste elemanlarının yer değiştirmesinin çok daha kolay olması

olarak söyleyebiliriz.

Listelerin boylarının dinamik bir şekilde büyüyüp küçülmesine burada değinmek istiyorum.Bildiğiniz gibi dizilerde tanımlama yaparken dizi boyunu sabit giriyoruz.Bu da şöyle bir sorun getiriyor.Kullanılmayan indis değerleri bellekte yinede yer kaplamaktadır.Bu nedenle listeler yapısını kullanarak dinamik bir yapı elde edebiliriz.Yani eleman ihtiyacı oldukça yapımız büyür ve ona göre bellekte yer açılır.

Bağlı listelerin(Linked Lists) dezavantajlarını sayacak olursak;

  • Dizilerde elemanlara erişim ardışıklık sebebiyle kolay iken listelerde bellek bölgesinde ardışıklık olmadığında erişim daha karmaşıktır.
  • İşaretçi de bellek bölgesinde yer tutar.

 

Diğer bazı liste yapıları ise şunlardır;

Dairesel Bağlı Listeler(Circular Linked Lists) : Verilerin her biri bir sonraki veriyi işaret eder.Ancak son verinin işaretçisi ilk veriyi gösterir ve null değildir. Böylelikle dairesel bir yapı sağlanmış olur.

circList

Çift Bağlı Listeler (Doubly Linked Lists) : Bu liste yapısında her veri iki adet işaretçi içerir.İlk işaretçi kendinden önceki veriyi gösterirken ikinciside kendisinden sonrakini gösterir.Bu yapı ile tek bağlı listelerdeki ileri ve geriye doğru dolaşmadaki zorluklar ortadan kalkar.

ciftList

Dairesel Çift Bağlı Listeler (Circular Doubly Linked Lists) : Hem dairesellik hem de çift bağlılık özelliği taşır.

ciftcircList

 

 

Evet, listeleri detaylıca işledik.Bir sonraki yazıda görüşmek üzere…

Yorum yaz

Comment