Listeler -1 (Linked List, Singly Linked List)

Programlamada listelere aralarında doğrusal ilişki bulunan veri toplulukları denebilir. Bu listelerin farklı biçimleri vardır. Bu yazımda diziler ve linked listleri açıklamaya çalışacağım.

Diziler (Doğrusal Listeler)

Arrayler aynı türden verileri bellekte sıralı bir şekilde tutan veri yapılarıdır.

Özellikleri

• Boyutları tanımlanırken belirlenmelidir.
• Dizinin başına veya ortasına eleman eklenirken elemanlar yer değiştirir.
• Çalışma zamanında eleman arttırılamaz veya azaltılamaz.
• Dizi boyutu tutacağı elemandan büyük tanımlandığında bellekte gereksiz alan kaplar
• Diziden bir elemanı çıkardığımızda ondan sonraki elemanların yerleri değişir. Bu durum zaman maliyetine neden olur.

package main

import "fmt"

func main() {

   array := [5]int{1, 2, 3, 4, 5}

   fmt.Println(array)
}

Burada Go dili ile bir dizi tanımladık ve onu ekrana yazdırdık.

Linked List (Bağlı Listeler)

Linked listler bellekte elemanları ardışık olarak tutmayan listelerdir.

• Linked listlerde her eleman kendinden sonraki elemanın bellekteki adresini tutar. İlk elemanın yeri ise bir değişkende tutulur. Böylece listedeki tüm elemanlara ulaşılabilir.
• Linked listlerin her elemanı bir yapı nesnesidir. Bu yapı nesnesinin bazıları liste elemanının değerini veya taşıyacağı bilgileri tutarken bazıları kendinden sonraki elemanın adresini tutar.
• Dizilerdeki gibi boyutunu önceden tanımlamaya gerek yoktur.
• Dinamiklerdir, listenin boyutu yetmediğinde boyutu arttırılabilir.

Linked Listler ile dizilerdeki şu sorunları çözebiliriz;

• Boyut değiştirme zordur.
• Yeni eleman ekleme zordur.
• Bir elemanı silme zordur.
• Dizinin tüm elemanları için hafızada yer ayrılır.

Linked Listlerde;

• Her eleman için ayrı hafıza alanı ayrılır.
• Bilgi kavramsal olarak sıralıdır fakat hafızada sıralı bir şekilde bulunmazlar
• Her eleman bir sonrakini gösterir.

Go Dilinde Linked List Örneği

type ListNode struct {
   data int
   next *ListNode
}

• Linked listlerde ilk elemanın adresi bir değişkende tutulur.
• Son elemanın göstericisi ise null olarak bırakılır.

Linked listlerdeki her eleman data ve link kısmından oluşur ;

• Data kısmı elemanın sakladığı değeri tutar.
• Link kısmı ise kendisinden sonraki elemanı işaret eder.

• Listede bir başlangıç (Head) elemanı (Listenin başlangıcını gösterir, Diğer düğümlere ulaşmak için bu düğümle başlamak mecburidir.) ve birde tail elemanı vardır
• Listede aktif (current) eleman şuan biligilerine ulaşabileceğimiz elemanlardır.

Linked Listlerde Yapılan İşlemler

Listeye Eleman Ekleme

• Başa
• Sıralı
• Sona

Listeden Eleman Silme

• Baştan
• Sondan
• Tümünü
• Belirlenen Bilgiye Sahip Elemanı
• İstenen Sıradaki Elemanı

Arama

Listeleme

Kontrol

Linked Liste Türleri

• Tek Yönlü Doğrusal
• Çift Yönlü Doğrusal
• Tek Yönlü Dairesel
• Çift Yönlü Dairesel

Tek Yönlü Doğrusal Liste (Singly Linked List)

Listedeki elemanlar arasında sadece tek bir bağ vardır. Hareket yönü baştan sonadır.

Tek Yönlü Listenin Başına Eleman Ekleme

Not: Head listenin başlangıç adresini tutan bir değişkendir.

Next: Nodun kendinden sonraki nodun adresini tuttuğu yer

• Listenin başlangıç (head) düğümünün adresi 8 ,data olarak A verisini tutuyor (A herhangi bir veri olabilir) ve sonraki düğümün adresi olan 1 adresini tutuyor.
• Biz head nodu olarak adresi 5 olan ve D (x=5) verisini tutan nodu eklemek istiyoruz.
• Öncelikle Head değişkenimizin tuttuğu adresi başa eklemek istediğimiz nodun kuyruğuna atıyoruz. Sonra Head değişkeninin tuttuğu adresi 5 olarak değiştiriyoruz. Hadi bunu go dili ile yazalım.

type ListNode struct {
   data int
   next *ListNode
}

type LinkedList struct {
   Head *ListNode
   len  int
}

func (l *LinkedList) AddNodeToFront(data int) {
   n := ListNode{}
   n.data = data

   if l.len == 0 {
      l.Head = &n
      l.len++
      return
   }
   n.next = l.Head
   l.Head = &n

   l.len++
   return
}

Tek Yönlü Listenin Sonuna Eleman Ekleme

Burada adresi 9 verisi olan bir nodu listemizin sonuna ekleyeceğiz.

• Öncelikle ilk noddan başlayarak son noda kadar gelmeliyiz.
• Sonra son nodumuzun kuyruğu (next) null değer taşıyordu.
• Bu değeri ekleyeceğimiz nodun adresi olarak değiştireceğiz.
• Hadi bunun kod yapısını görelim.

Not : ListNode ve LinkedList yapılarını yukarıda oluşturmuştuk.

func (l *LinkedList) AddNodeToBack(data int) {

   if l.len == 0 {
      n := ListNode{}
      n.data = data

      l.Head = &n
      l.len++

   } else {
      last := ListNode{data: data}
      current := l.Head
      for current.next != nil {
         current = current.next
      }
      current.next = &last

      l.len++
      return

   }

}

Tek Yönlü Listenin Ortasına Eleman Ekleme

Şimdi ise iki nodun ortasına bir node ekleyeceğiz.

• Bir tane n nodu tanımlıyoruz.
• C4 ve F0 nodlarımızın arasına yerleştireceğiz bu nodu
• Öncelikle head nodumuzdan başlayarak C4 nodumuza kadar geleceğiz.
• Bir tanede prev ve current olmak üzere iki node tanımlıyoruz.
• Döngüde prev nodumuzu current noduna eşitliyoruz.
• Buraya kadar gelmemiz için ve bu nodumuz kendisinin kuyruğuna eşitleyerek döngü içerisinde C4'e kadar getiriyoruz. Döngüde kaçıncı sıraya ekleneceğini dışarıdan alacağız.
• C4'e geldiğinde (current=c4 olduğında) döngüden çıkıp prev nodumuzun kuyrugunu (C4) n noduna eşitliyoruz.
• Sonra current nodumuzu n nodumuzun kuyruğuna eşitliyoruz.
• Kod yapısı ise şu şekilde;

func (l *LinkedList) AddNodeToBetween(data, num int) {
   n := ListNode{}

   if l.len == 0 {
      n.data = data
      l.Head = &n
      l.len++
   } else {
      current := l.Head
      prev := current
      for i := 0; i < num-1; i++ {
         prev = current
         current = current.next
      }
      n.data = data
      prev.next = &n
      n.next = current
      l.len++
      return
   }
}

Tek Yönlü Listenin Başından Eleman Çıkarma

Aslında ekleme ile aynı mantıktadır.

• Head nodumuzu head.next noduna eşitliyoruz ve listemizin boyutunu bir azaltıyoruz.

func (l *LinkedList) RemoveFromFront() {
   if l.len==0{
      fmt.Println("Don't have Node")
   }
   l.Head = l.Head.next
   l.len--
}

Tek Yönlü Listenin Sonundan Eleman Çıkarma

• Öncelikle listemizin sonundan eleman çıkartmak için current ve prev diye iki tane node oluşturuyoruz.
• Sonra current nodumuzu listemizin head noduna eşitliyoruz.
• Sonra bir for döngüsünde current nodumuzun kuyruğu null değer olana kadar currenti önce prev nodumuza eşitliyoruz sonra currentin kuyruğundaki noda eşitliyoruz.
• Döngü tamamlandığında prev nodumuz sondan bir önceki node oluyor. Prev nodumuzun kuyruğuna null değerini atıyoruz böylelilikle son nodumuz döngüden çıkmış oluyor.

func (l *LinkedList) RemoveFromBack() {
   if l.len == 0 {
      fmt.Println("Don't have Node")
   }
   var prev *ListNode
   current := l.Head
   for current.next != nil {
      prev = current
      current = current.next
   }
   if prev != nil {
      prev.next = nil
   } else {
      l.Head = nil
   }
   l.len--
   return
}

Tek Yönlü Listede Girilen Veriye Göre Listeden Çıkartma

• current ve prev nodlarımızı tanımlıyoruz.
• Daha sonra current nodumuzu listemizin head noduna eşitliyoruz.
• Listemizdeki node sayısı kadar dönecek bir for döngüsü oluşturuyoruz.
• For içinde eğer current nodumuzun datası alınan dataya eşit ise prev nodumuzun kuyruğunu current nodumuzun kuyruğuna eşitliyoruz ve listenin uzunluğunu bir azaltıp döngüden çıkıyoruz.
• Eğer current nodumuzun datası alınan dataya eşit değilse prev nodumuzu current nodumuza eşitliyoruz ve current nodumuzuda current nodumuzun kuyruğuna eşitleyip döngüye devam ediyoruz.
• Eğer çıkartılacak değer listede yoksa döngüden çıkıldığında değerin listede olmadığını yazdırıyoruz.

func (l *LinkedList) RemoveFromData(data int) {
   if l.Head == nil {
      fmt.Println("List is Empty")
   } else {
      var prev *ListNode
      current := l.Head
      for i := 0; i < l.len; i++ {
         
         prev = current
if current.data != data {
            current = current.next
         } else {
if current.next != nil {
               prev.next = current.next
            } else {
               prev.next = nil
            }
            fmt.Printf("Remove the %d", data)
            fmt.Println()
            l.len--
            break
            return
         }
      }
      fmt.Printf("%d not found in the list", data)
      fmt.Println()
   }
}

Tek Yönlü Listenin Tüm Elemanlarını Çıkarma

• Tüm elemanları çıkartmak için current ve prev olmak üzere iki tane node tanımlıyoruz.
• Sonra current nodumuza listemizin ilk elemanına eşitliyoruz.
• Daha sonra current nodumuzun kuyruğu null olana kadar dönecek bir for döngüsü oluşturuyoruz.
• Bu döngümüzde prev nodumuzu current nodumuza eşitliyoruz. Ardından current nodumuzu da kuyruğuna eşitliyoruz. Prev nodumuzun kuyruğunuda null olarak eşitliyoruz.
• Böylelikle döngü sonunda baştan itibaren tüm nodlar dongüden çıkartılmış oluyor.

func (l *LinkedList) RemoveAll() {
   var prev *ListNode
   if l.Head == nil {
      fmt.Println("List is Empty")
   }
   current := l.Head
   for current.next != nil {
      prev = current
      current = current.next
      prev.next = nil
   }
   l.len = 0
   return
}

Tek Yönlü Listenin Tüm Elemanlarını Gösterme

• Yine bir tane current nodu oluşturup bunu listemizin head döğümüne eşitliyoruz.
• Sonra bu nodun datasını ekrana yazdırıyoruz ve for döngüsünde current boş olana kadar kuyruğundaki noda eşitliyoruz.
• Bu kadar şimdi kodu gösterelim

func (l *LinkedList) ListOfAll() {
   if l.Head == nil {
      fmt.Println("List is Empty")
   }
   current := l.Head
   for current != nil {
      fmt.Println(current.data)
      current = current.next
   }

}

Tek Yönlü Listede Arama

• Bir tane current nodu ve count tanımlıyoruz.
• Bu current nodumuzu listenin head noduna eşitliyoruz.
• Daha sonra listedeki eleman sayısı kadar dönecek bir for yapısı oluşturuyoruz.
• Bu for yapımızda bir if ile current nodumuzdaki data aldığımız dataya eşitse count ile datamızın listede kaçıncı sırada olduğunu yazıyoruz.
• Eşit değilse current nodumuzu kuyruğuna eşitleyip count değerini bir artırıyoruz.
• Eğer aranan veri listede yoksa for döngüsünden çıktıktan sonra verini listemizde olmadığını belirtiyoruz.

func (l *LinkedList) SearchInList(data int) {

   if l.Head == nil {
      fmt.Println("List is empty")
   } else {
      count := 1
      current := l.Head
      
      for i := 0; i < l.len; i++ {
         
         if current.data == data {
            fmt.Printf("Your Data %d your data count : %d", current.data, count)
            fmt.Println()
            break
         }
         current = current.next
         count++
      }
      
      if current.data != data {
         fmt.Printf("%d not found in list", data)
         fmt.Println()
      }

   }
   return
}

Bu yazımız bu kadardı Doubly Linked List yapısını açıkladığım yazıma ise aşağıdaki linkten ulaşabilirsiniz.

Listeler -2 (Doubly Linked List)

Kaynakça:

Prof. Dr. Erkan Tanyıldızı Ders Notları

https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/

https://dev.to/divshekhar/golang-linked-list-data-structure-h20#:~:text=What%20is%20a%20Linked%20List,uses%20arrays%20under%20the%20hood.

inserting a node at the beginning of a linked list