C# (Linked List)

BAĞLAÇLI LİSTELER

LINKED LIST

LİSTELER

Günlük yaşamda listeler pek çok yerde kullanılmaktadır. Alışveriş listeleri, adres listeleri, davetli listeleri gibi. Bilgisayar programlarında da listeler yararlı ve yaygın olarak kullanılan veri yapılarındandır. Programlama açısından liste, aralarında doğrusal ilişki olan veriler topluluğu olarak görülebilir.

BAĞLAÇLI LİSTELER

Kendi tipindeki bir yapıyı gösteren bir işaretçi üyesine sahip yapılara self-referential structes adı verilir. Örnek olarak:

Class Dugum //node

{

Private string veri,//info

Private DUgum sonraki;//next

……

}

yapısı, veri adlı string tipli bilgi elemanının yanında, bir düğüm yapısında bir bellek bölgesine işaret eden sonraki (next) işaretçisine sahiptir. Bu tür yapıların arka arkaya birbirine bağlanması mantığı listelerde oldukça yararlıdır.

Listedeki her düğümde bir sonraki düğümün adresinin tutulduğu veri yapısı (doğrusal) bağlı liste olarak adlandırılır. Listenin her bir elemanına düğüm (node) adı verilir. Düğümler, bilgi ve bağ (adres) sahalarından oluşmaktadırlar. Bağ sahalarında referanslar kullanılmaktadır. Listenin ilk elemanına dışarıdan bir referans (list) ile erişilmektedir. Diğer düğümlere de bağlar yardımı ile ulaşılabilmektedir. Son düğümün sonraki adres (sonraki) sahası NULL değerini içerir. NULL bağlı, liste sonunu belirtir. Elemanı olmayan liste boş liste olarak adlandırılır.

Sıralı bellek kullanımının (dizi) en büyük dezavantajı, hiç kullanılmasa veya az kullanılsa bile sabit miktardaki belleğin bu yapılara ayrılmış olarak tutulmasıdır. Ayrıca sabit bellek miktarı aşıldığında da taşma oluşması ve eleman ekleme işleminin yapılamamasıdır. Bağlaçlı listeler üzerinde gerçekleştirildiklerinde ise bu problemler ortadan kalkmaktadır. Bellekten sadece gerektiği kadar yer ayrılmakta ve bellek boyutu bitene kadar bu yapılara ekleme işlemi yapılabilmektedir.

Bağlaçlı listeler, başka veri yapılarının gerçekleştiriminde kullanılabildikleri gibi kendileri de veri yapısıdırlar. Bağlaçlı listelerde elemanların ekleme ve çıkarılmasında bir sınırlama yoktur. Başa ve sona olduğu gibi araya da eleman eklenebilir; baştan ve sondan olduğu gibi ortadan da eleman çıkarılabilir. Bağlaçlı liste dolaşılarak herhangi bir elemanına erişilebilir. Bir bağı listenin n. elemanına erişmek için n tane işlem yapmak yani kendinden önceki (n-1) eleman üzerinden geçmek gerekmektedir. Elemanların bellekteki yerleri dizilerdeki gibi sıralı olmadığından elemanlar ve sıraları ile yerleştikleri bellek bölgeleri arasında bir ilişki yoktur.

Bağlaçlı listelerin diziler üzerine avantajı, bir grup eleman arasına eleman eklemede ve bir grup eleman çıkarmada ortaya çıkar.

Dizilerde bir eleman silerken arada boşluk kalmasını engellemek için ilerisindeki (sağındaki) tüm elemanları bir geriye (sola) kaydırmak gerekir. Eleman eklemede de yer açmak için konulacağı yerdeki ve ilerisindeki elemanları bir ileriye (sağa) kaydırmak gerekecektir. Kaç tane elemanın yer değiştireceği (birer kaydırılacağı) dizi boyutuna bağlı olarak ve eklenecek elemanın yerine bağlı olarak değişecektir. Bağlaçlı listelerde ise eleman ekleme ve çıkarma için yapılan iş liste boyutundan bağımsızdır.

Bağlaçlı Listede Kullanılan Sınıflar:

Dugum                 : Tek düğüme ilişkin veriler ve işlemler

Liste                      : Listeye ilişkin veri ve işlemler

ListeTest             : Listenin test edilmesi