Veri Yapıları 2 Bağlı Listeler
  1. Anasayfa
  2. Algoritmalar

Veri Yapıları 2 Bağlı Listeler

0

Önceki bölümde veri yapılarının tanım olarak ne olduğuna kısaca değinmiştik. Bu bölümde ise amacımız veri yapıları konularında başlangıç konusu olarak anlatılması alışılagelmiş olan Linked List yani Bağlı Liste veri yapısıdır.

Bağlı Listeler dinamik veri yapılarıdır bu yüzden klasik Array’lerden farklıdırlar. Buradan anlıyoruz ki bağlı listelerin boyutları dinamik olarak değişebilmektedir. Diziler gibi sabit değerli olmadıkları için de kullanılmadıkları durumlar için bellek israfına yol açmazlar.

Optimizasyon konularında vurgu yaptığımız konu hep algoritmanın zaman bakımından ve bellek bakımından performanslı olması gerektiği ve buna uygun algoritmaların tercih edilmesi konusuydu. Veri yapılarında da bilgisayar bilimleri üzerindeki optimizasyon gayemizden vazgeçmeyen bir strateji izliyor ve kullanacağımız veri yapılarının üzerinde çalıştığımız işleme uygun olarak seçilmesi gerekmektedir. Üzerinde çalıştığımız kodlama ortamına uygun veri yapısı seçmek zamandan ve en önemlisi bellek israfından kaçınmamızı sağlayacaktır.

Örneğin klasik dizi veri yapılarında dizinin boyutu önceden belli olduğu için hafızada ona göre yer açılır ve elemanlar da sırayla işleme alınır veya sıralanırlar. Bağlı listelerde bu iş böyle değildir. Elemanların bellekteki yerleri sıralı olmak zorunda değildir çünkü bağlı listeler elemanlarına ulaşabilmek için dizilerdeki gibi sıra indisi takip etmek yerine elemanların düğüm (node *) adreslerini kullanırlar.

İşte bu bilgiler ışığında artık diyebiliriz ki bağlı listeler herhangi bir tip node ile yine kendi tipindeki node’lara işaret etmesi ile oluşan zincirlemedir. Bu da demek oluyor ki her düğümde kendi tipinden bir pointer bulunacak ve bu pointer ile düğümler birbirlerine aşağıdaki görselde yer aldığı gibi bağlanacaktır.

 

Resim-1

Her bağlı listenin Root isminde kök bir göstericisi olmak zorundadır. Bağlı listede bir elemana erişmek istediğimizde ilk elemana erişmemiz gerekir. Bu ilk elemana da root üzerinden erişebiliriz. Diğer elemanlara ise Next işaretçisinin işaret ettiği düğüme erişecek şekilde erişim sağlanır.  Bağlı listeler tek-çift yönlü ve dairesel olarak iki kategoride incelenmektedir. Resim-1’de yer alan bağlı liste gösterimi tek yönlü bağlı listelere örnektir.

Tek yönlü bağlı listelerin ilk düğüm işaretçisi yine resimden de görüleceği üzere HEAD olarak adlandırılır.

Tek Yönlü Bağlı Listelerin Avantajları:

  • Dinamik hafıza kullanımı vardır
  • Ekleme silme gibi işlemler kolaydır.
  • Bir yönde hareket için kullanılacak en verimli veri yapısıdır.
  • Bellek ihtiyaç halinde temin edilir veya serbest bırakılabilir.

Tek Yönlü Bağlı Listelerin Dezavantajları:

  • Dizi veri yapılarına göre daha fazla bellek harcamaktadır.
  • Tek yönlü olduğu için ters yönde hareket edemeyecektir.
  • Elemanlar yani düğümler sıralı depolanmadığı için arama işlemlerinde daha fazla zaman harcanabilir.

Bağlı listeler bellekten malloc() fonksiyonu ile dinamik şekilde bellek alanı ayırarak bunları işaretçi değişkenlere bağlayarak tutulabilir.

struct bagliListe* DugumOlustur (int veri){

struct bagliListe* yeniDugum = (struct bagliListe*)malloc(sizeof(struct baligListe));

yeniDugum -> veri=veri;

yeniDugum -> sonrakiDugum=NULL;

return yeniDugum;

}

 

Resim-2

Bağlı listelerde bir düğüm kendisinden sonra gelen düğümün adres bilgisini ve kendisinden önceki düğümün adres bilgisini içeriyorsa buna çift yönlü (double) bağlı liste denilmektedir.

Çift Yönlü Bağlı Listelerin Avantajları:

  • Liste üzerinde çift yönlü hareket edebilmektedir.
  • Ekleme, silme gibi işlemler daha kolaydır.

Çift Yönlü Bağlı Listelerin Dezavantajları:

  • Önceki işaretçisi için bellekte fazladan yer kaplayacaktır.
  • Her düğümde önceki ve sonraki işaretçileri olduğu için listeleme işlemleri daha yavaştır.

 

struct BagliListe * Olustur(int veri1, int veri2){

struct BagliListe * yeniDugum=(struct BagliListe * )malloc(sizeof(struct BagliListe));

yeniDugum->veri1=veri1;

yeniDugum->veri2=veri2;

yeniDugum->onceki=NULL;

yeniDugum->sonraki=NULL;

return yeniDugum;

}

Resim-3

Tek yönlü bağlı listelerde listenin son düğümünün sonrakini işaret eden işaretçisi her zaman NULL değerini göstermektedir. Tek yönlü bağlı liste yapısına ilave bir özellik eklenmişçesine ortaya yeni bir bağlı liste türü çıkmıştır. Bu özellik listenin son elemanının sonraki yani NEXT işaretçisinin listenin ilk elemanını göstermesi şeklinde işlemektedir. Bu sayede bir döngü, daire elde edilmiş olur.  Dairesel bağlı listelerde son düğüm bulunmamaktadır. Çünkü dairesel tek yönlü listeler sonlanmayacak başa dönecektir.

Bu konuyla ilgili sorularınızı  alt kısımda bulunan yorumlar alanını kullanarak sorabilirsiniz.

Referanslar

www.mshowto.org

Algoritmalara Giriş Thomas H. CormenCharles E. LeisersonRonald L. RivestClifford Stein

TAGs: Bağlı liste, bağlı listeler, veri yapıları, linked list, linked list nedir, bağlı list nedir?

Bu İçeriğe Tepkin Ne Oldu?
  • 3
    harika_
    Harika!!
  • 1
    be_enmedim
    Beğenmedim
  • 1
    _ok_iyi
    Çok iyi
  • 3
    sevdim_
    Sevdim!
  • 1
    bilemedim_
    Bilemedim!
  • 2
    olmad_
    Olmadı!
  • 2
    k_zd_m_
    Kızdım!

Konya Teknik Üniversitesi Bilgisayar Mühendisliği Doktora programında tez dönemi öğrenciliğim devam etmektedir.İş hayatıma Vodafone'da Test Mühendisi olarak başladıktan sonra şuan bir üniversitede Sistem Uzmanı ve Siber Güvenlik Ofis Yöneticisi pozisyonunda çalışmaktayım.Başlıca uzmanlık alanlarım arasında Sistem yöneticiliği ve Siber Güvenlik gelmektedir.Asp.net ile Proje Geliştirme (2015), Bilgisayar Mühendisliğine Giriş (2020), Güvenlik Tasarım Desenleri (2022) kitaplarının yazarıyım.

Yazarın Profili
İlginizi Çekebilir

Bültenimize Katılın

Tıklayın, üyemiz olun ve yeni güncellemelerden haberdar olan ilk kişi siz olun.

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir