İlginizi Çekebilir
  1. Ana Sayfa
  2. Algoritmalar
  3. Veri Yapıları 2 Bağlı Listeler

Veri Yapıları 2 Bağlı Listeler

Linkedlist mshowto

Ö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ı https://forum.mshowto.org linkini kullanarak ulaşacağınız forum sayfamızda 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?

Yorum Yap

Yazar Hakkında

Bilgisayar Mühendisliği Doktora programında öğrenciliğim devam etmektedir. Bir Vakıf üniversitesinde 2016 yılı itibariyle Bilgisayar Mühendisi 2020 yılı itibariyle ise Ofis Yöneticisi mühendis olarak çalışmaktayım.  Başlıca uzmanlık alanlarım arasında Asp.Net Web Forms, Asp.Net MVC, .Net Core, C# ve SQL Server gelmektedir. Bunların yanı sıra iş hayatımda sistem ve siber güvenlik konularında da çalışmalarım devam etmektedir. Çeşitli AB destek projelerinde yazılım sorumlusu olarak görev yapıyor ve çalışmalarımı Secure Design Pattern, Yazılım Güvenliği, Siber Güvenlik, Bilgi Güvenliği konularında sürdürüyorum. Asp.net ile Proje Geliştirme ve Bilgisayar Mühendisliğine Giriş isimli kitapların yazarıyım.

Yorum Yap