Diziler ve bağlı listeler birbirlerine benzeseler de aralarında büyük farklar vardır. Öncelikle diziyi tanımlayalım. Bellekte (Ram) ard arda yer kaplayan yapılardır. 5 elemanlık tamsayı (integer) bir dizimiz olsun (arrDizi). Ve ilk elemanın bellekteki yeri 0 olsun. 1. elamanın yeri 0 adresi, 2. elamanın yeri 4 adresi (integer türü 4 baytlık yer kapladığı için) olup bu şekilde devam edecektir. Oluşturduğumuz dizi bellekte yaklaşık olarak aşağıdaki gibi bir yer kaplayacaktır.
Bu yapının bize çok büyük avantajları var. Mesela dizinin 3. elemanına (2. indis) ulaşmak istediğimizde 0 adresinden (Dizinin başlangıç adresi) 8 bayt ilerlediğimizde bulabiliriz ((3-1) * 4). Eğer başlangıçta kaç elemana ihtiyacınız olduğunu biliyorsanız dizi sizin için biçilmiş kaftandır. Fakat ne kadar eleman olduğunu bilmiyorsanız veya belirli bir kurala göre eleman ekleyip çıkartıyorsanız bu sefer bağlı liste işinize daha çok yarayacaktır.
Bağlı listenin bir başlangıç düğümü (Node) vardır. Düğümler kendi içinde elemanın değerini ve sonraki düğümün adresini tutarlar. Bağlı listeye eleman eklemek için (herhangi bir kural olmadan) başlangıç düğümünden başlayıp son düğüme kadar ilerlemek ve sondaki düğümün sonraki düğüm adresine yeni oluşturulacak düğümün adresini vermek gerekir.
Bağlı listeden bir eleman silmek için ise silinecek eleman bulunana kadar düğümler dolaşılır (Önceki düğümü başka bir değişkende tutularak). Önceki düğümün sonraki düğüm adresine silinecek düğümün sonraki düğüm adresi atanır. Ama başlangıçtaki düğüm silinmek isteniyorsa başlangıç düğümünün sonraki düğümü başlangıç olarak atanır. Eğer index değerine göre silmek istiyorsanız aynı şey geçerli sadece bir değişkende hangi düğümde olduğunu tutmanız gerekiyor.
Dizi ile Bağlı Liste Arasındaki Farklar
| Dizi (Array) | Bağlı Liste (Linked List) |
|---|---|
| Dizilerin belirli bir kapasitesi vardır. (Program başladığında belirlenir) | Bağlı listelerin bir kapasitesi yoktur belleğin izin verdiği miktarda büyüyebilirler. |
| Diziler birbirinin arkasına sıralı bir şekilde gelir. (Dizi[0], Dizi[1] den 4 bayt (integer dizi için) sonradır) | Bağlı listedeki elemanlar bellekte herhangi bir yerde olabilirler. |
| Bir diziye eleman eklemek ve çıkartmak çok maliyetlidir. (5 elemanlık bir diziye 6. elemanı eklemek isterseniz ilk önce önceki 5 elemanlık diziyi bellekte başka bir yere taşımamız gerekir) | Bağlı listelerde eleman eklemek ve çıkarmak nispeten daha kolaydır. (Sadece en son düğümü veya silinecek düğümü bulmak gerekir) |
| Dizilerde arama çok daha kolaydır. Çünkü bellekte ardışık yer kaplarlar. (Algoritma Karmaşıklığı O(1)) | Bağlı listelerde arama yapmak zordur çünkü bir düğüme ulaşmak için önceki düğümlerden gelmeniz gerekir. ( Algoritma Karmaşıklığı O(n)) |
| Diziler bellekte daha az yer kaplar (Sadece değerleri tutarlar) | Bağlı listeler bellekte daha fazla yer kaplar (Hem değerleri hem de sonraki düğümün adresini tutarlar) |
Aşağıda da kendi yazdığım bağlı liste sınıfını görebilirsiniz. İstediğini gibi değiştirip işinize yarayan bir şekle getirebilirsiniz.
static void Main(string[] args)
{
BagliListe liste = new BagliListe();
liste.SonaEkle(5);
liste.SonaEkle(10);
liste.SonaEkle(15);
liste.SonaEkle(20);
liste.IndexdenSil(1);
liste.Yazdir();
Console.ReadKey();
}
public class BagliListe
{
public Dugum baslangic;
public BagliListe()
{
baslangic = null;
}
public BagliListe(int Deger)
{
baslangic = new Dugum(Deger);
}
public void SonaEkle(int Deger)
{
Dugum eklenecekDugum = new Dugum(Deger);
// Eğer daha önce hiç eleman eklenmemişse başlangıç düğümüne ekle
if (baslangic == null)
{
baslangic = eklenecekDugum;
return;
}
// Son düğümü bulup onun sonuna ekle
Dugum tmp = baslangic;
while (tmp.SonrakiDugum != null)
tmp = tmp.SonrakiDugum;
tmp.SonrakiDugum = eklenecekDugum;
}
public void BasaEkle(int Deger)
{
Dugum eklenecekDugum = new Dugum(Deger);
eklenecekDugum.SonrakiDugum = baslangic;
baslangic = eklenecekDugum;
}
public void Sil(int Deger)
{
// Başlangıç düğümü bir değişkene atanıyor
Dugum tmp = baslangic;
Dugum oncekiDugum = null;
// Eğer aranan değer başlangıç düğümü ise başlangıç
// düğümünden sonraki düğüm başlangıç düğümü oluyor
if (tmp != null && tmp.Veri == Deger)
{
this.baslangic = tmp.SonrakiDugum;
return;
}
// Aranan değeri bulana kadar veya listenin sonuna gelene kadar dön
while (tmp != null && tmp.Veri != Deger)
{
oncekiDugum = tmp;
tmp = tmp.SonrakiDugum;
}
// Eğer aranan değer dizide yoksa bir şey yapma
if (tmp == null)
return;
// Aranan değerinin önceki düğümünün sonraki düğüm
// adresini aranan değerin sonraki düğüm adresine eşitle
oncekiDugum.SonrakiDugum = tmp.SonrakiDugum;
}
public void IndexdenSil(int IndexDegeri)
{
// Eğer en baştaki düğümü silinmek istenirse
if (IndexDegeri == 0)
{
this.baslangic = baslangic.SonrakiDugum;
return;
}
Dugum tmp = baslangic;
Dugum oncekiDugum = tmp;
int simdikiIndex = 0;
// İstenen index değerine ulaşana kadar dön
while (tmp != null && IndexDegeri != simdikiIndex)
{
oncekiDugum = tmp;
tmp = tmp.SonrakiDugum;
simdikiIndex++;
}
// Eğer şimdiki index değeri istenen index değeriyse atamayı yap
if(IndexDegeri == simdikiIndex)
oncekiDugum.SonrakiDugum = tmp.SonrakiDugum;
}
public void Yazdir()
{
Dugum tmp = baslangic;
while (tmp != null)
{
Console.Write("{0} ->", tmp.Veri);
tmp = tmp.SonrakiDugum;
}
}
public class Dugum
{
public Dugum SonrakiDugum;
public int Veri;
public Dugum (int Deger)
{
SonrakiDugum = null;
Veri = Deger;
}
}
}