1. Linked List (Bağlı Listeler)

 1. LINKED LIST KAVRAMI
 Şimdi öncelikle , nedir bu linked list’i bizim bildiğimiz sıradan arraylerden ayıran özellik,en temel olanıyla başlayalım.

   1. Bizim sıradan arraylerin boyutu STATIKTİR.bir kere boyut tanımlarsınız ve değiştiremezsiniz.  mesela yukarıdaki sayilar dizimizin boyutu dizi oluşturulurken tanımlanmış ve 10 integer sayi alıcak şekilde belirtilmiş. Bu artık değiştirilemez, ister kullan ister kullanma sana bellekten 10 intlik yer ayrılmıştır.bu dizinin boyutu 10dur. E tahmin edersiniz ki bu çoğu zaman bellek israflarina bazen de yetersizliklerine sebep oluyor.Örneğin sizin bellekten ayırdıgınız 10 intlik alanın tamamını kullanmıyor olabilirsiniz veya o an için  daha fazla alana ihtiyacınız olabilir. iste böyle durumlarda statik boyutlu diziler yetersiz kalıyor ve dinamik boyutlu yapılara ihtiyacimiz oluyor. Linked List de böyle bir yapıya sahip, boyutu dinamik olarak değişir.

  2. Linked listler farklı tiplerden eleman tutabilirler

  3. Bir diğer bir farkı ise elemanlarin bellekte sıralanış şekli. Sıradan arraylerde daha array tanımlanırken boyutu belirttiğimizden bellekte elemanlar arka arkaya sıralanırlar. Ancak Listlerde elemanlarin bellekteki yerinin arka arkaya olması gerekmiyor. O zaman hemen aklımızda şöyle bir soru oluşuyor. Bu list elemanlarinin her birine nasıl ulaşıyoruz. Bu sorudan sonra linked listle arrayleri karşılaştırmayı birakip linked list konusunu anlatmaya başlayabiliriz.


 2. LINKED LIST’IN YAPISI 

2.1 Node kavramı
  Linked list birbirine bağlı node’lardan oluşur. Node’lar temelde 2 bilgiyi barındırır. Bunlar;

  1. Tutulacak olan veri -> Data
  2. Kendinden bir sonraki node’ın adresi -> Next

Bizim linked listte tek bildiğimiz şey ilk elemanın yani head’in adresi, diğer elemanların yerlerini hiç bir şekilde bilmiyoruz. E o zaman diğer elemanlara nasıl ulaşıyoruz. Head üzerinden…

ilk eleman  : head
ikinci eleman : head.next
üçüncü eleman : head.next.next      şeklinde tüm elemanlar üzerinde dolaşabiliriz.

C# ile linked list node implementasyonu

class ListNode
 {
   private object data;
   private ListNode next;

   public ListNode(object dataValue) : this(dataValue, null) //son node'u gösterir onun da next nodu yoktur
   {   }

   public ListNode(object dataValue, ListNode nextNode) //diger nodu gösteren next node
   {
      data = dataValue;
      next = nextNode;
   }

   public ListNode Next 
   {
    get { return next; }
    set { next = value;}
   }

   public object Data 
   {
    get { return data;}
   }
}

2.2 LINKED LIST OPERASYONLARI
  Linked list veri yapısında bazı temel operasyonlar söz konusudur. Bunlar;
     – Listenin sonuna eleman ekleme (tail’a)  : eski tail normal bir ara eleman olur. Yeni eklenen ise tail olur.

     – Listenin sonundan eleman silme (tail’dan) : eski tail silinir. Onun bir gerisindeki tail olur.
 

– Listenin başına eleman ekleme (head kısmına) 
Eski head normal bir ara eleman olur. Yeni eklenen ise head olur.

    public void InsertAtFront(object InsertItem)
    {
     lock (this)
     {
       if (IsEmpty())
         firstNode = lastNode = new ListNode(InsertItem);
       else
         firstNode = new ListNode(InsertItem, firstNode);
      }
    }

     – Listenin başında eleman silme (head’i silme) : eski head silinir. Onun bir önündeki head olur.