Skip to content

C# Linked List (Singly Linked List) nedir?

Merhaba arkadaşlar, bu makalemde sizlerle veri yapılarının bir parçası ve mülakatların ise vazgeçilmez sorusu olan Linked List‘i ve en basiti olan Singly Linked List hakkında bahsedip custom bir örnek yapacağız. 🙂

Nedir bu Linked Lists (Bağlı Listeler)?

Linked List’ler hakkında dinamik veri yapılarıdır desek yanlış olmaz. Çünkü dizilerde olduğu gibi başta kaç adet elemanla çalışacağımızı bildirmek zorunda değiliz ve Linked List içerisinde bellek üzerinde tanımlanan elemanlar göstericiler yardımı ile birbirlerine bağlanarak tıpkı tren vagonları gibi bir liste yapısı oluştururlar.

.Net Framework 4 ile birlikte gelen collections ailesinde  LinkedList<T> generic sınıfı bulunmaktadır ama biz makalemizde custom bir Singly Linked List yapısını inceliyor olacağız mantığını daha iyi kavrayabilmek adına.

Linked List’in bir başlangıcı ve son elemanı vardır. Dizilerde olduğu gibi eleman ekleme, silme işlemleri uygulanabilir ve en güzel avantajı ise araya da yeni bir eleman katılabilir.

Bir başka avantajı ise dizilerde tanımlanmış fazla eleman sayıları örneğin 500 elemanlı bir dizi kullanmak bellek açısından bir maliyeti olacaktır oysa Linked List’te herhangi bir boyut belirtmek zorunda kalmayacağımız için ihtiyacımız olacak şekilde boyutu artacaktır ve bellek açısından daha az maliyetli olacaktır. Linked List’lere herhangi bir eleman ekleme limiti yoktur yada ram’inizin kaldırabileceği kadar desek daha doğru olur. 🙂

Bu kadar teorik bilgiden sonra şimdi biraz yapısına göz atalım:

c# singly linked listYukarıda 5 elemanlı bir LinkedList görmekteyiz. Teorik bilgiden bahsederken bir başlangıcı ve sonu vardır demiştik. 1. eleman (node) burada bize başlangıcı verirken 5. eleman ise sonu vermektedir ve son elemanın NextNode’un null olduğu unutulmamalıdır.

Tren vagonları gibi birbirlerine bağlı olarak giden bu listenin elemanları arasında gezmekte mümkündür. Her eleman kendinden bir önceki elemanı (PrevNode) (Doubly Linked List için geçerlidir bu yapı) ve kendinden bir sonraki elemanı (NextNode) (Doubly ve Singly içinde geçerlidir) tutmaktadır.

İncelemiş olduğumuz yapısından sonra Linked List’ler hakkında:

  • Yeni bir eleman için hafızada yer ayrılır
  • Her eleman kendinden bir önceki ve kendinden bir sonraki eleman bilgisini tutar
  • Dizlerde olduğu gibi bir boyut belirtmemize gerek yoktur

diyebiliriz.

Şimdi bir örnek pekiştirelim:

Örneğimizde telefon rehberi için olan Person sınıfında kişi bilgileri tutulurken LinkedList sınıfında ise bağlı listemiz bulunacaktır ve örneğimiz custom bir Linked List yapısını incelemektir.  Singly Linked List’ten biraz farklı olarak elemanlar arası iterasyon yapabilmek için PrevNode özelliğinde ekleyerek böylece Doubly Linked List mantığınada bakmış olacağız çift taraflı.

namespace SinglyLinkedListExample
{
    class Program
    {
        static void Main(string[] args)
        {
            LinkedList rehberList = new LinkedList(new Person("Gökhan", "Gökalp", "05554443322", null));

            // Yeni eleman eklenebileceğinden bahsetmiştik şimdi düğüm ekleme mantığına bir bakalım:
            // NextNode parametresini null bıraktığımız için sona ekleyecektir.
            Person secondNode = new Person("Ramazan", "Gökalp", "04443332211", rehberList.FirstNode);
            rehberList.AddNode(secondNode);

            Person thirdNode = new Person("Salih", "Gökalp", "03332221100", secondNode);
            rehberList.AddNode(thirdNode);

            while (rehberList.NextNode())
            {
                if (rehberList.CurrentNode.FirstName == "Ramazan")
                {
                    // Bu sayede 2. elemanımız olan Ramazan kişisinden sonra araya Kezban kişisini eklemiş oluyoruz.
                    Person fifthNode = new Person("Kezban", "Ilhan", "07773334422", rehberList.CurrentNode);
                    rehberList.AddNode(fifthNode);
                }
            }
        }
    }

    public class Person
    {
        public string FirstName { get; set; }
        public string LastName { get; set; }
        public string PhoneNumber { get; set; }

        // Kendinden önceki eleman bilgisini verir.
        public Person PrevNode { get; set; }

        // Kendinden sonraki eleman bilgisini verir.
        public Person NextNode { get; set; }

        public Person(string firstName, string lastName, string phoneNumber, Person prevNode)
        {
            FirstName = firstName;
            LastName = lastName;
            PhoneNumber = phoneNumber;

            // Kendinden önceki elemanı verir.
            PrevNode = prevNode;
        }
    }

    public class LinkedList
    {
        // İlk elemanı vermektedir.
        public Person FirstNode { get; set; }

        // Aktif elemanı vermektedir.
        public Person CurrentNode { get; set; }

        // Son elemanı vermektedir.
        public Person LastNode { get; set; }

        public bool _NextNodeFlag = false;

        public LinkedList(Person fistNode)
        {
            // Şuanki eleman ilk elemandır.
            FirstNode = fistNode;
            CurrentNode = fistNode;
            LastNode = fistNode;
        }

        public void AddNode(Person person)
        {
            // Eğer şimdiki elemanın kendinden sonraki elemanı null ise sona ekleyecektir.
            if (CurrentNode.NextNode == null)
            {
                CurrentNode = CurrentNode.NextNode = person;
                LastNode = person;
            }
            // Kendinden sonraki elemanı null değil ise araya ekleyecektir.
            else
            {
                Person tempNextNode = CurrentNode.NextNode;
                CurrentNode = person;
                CurrentNode.NextNode = tempNextNode;
            }
        }

        public bool NextNode()
        {
            if (!_NextNodeFlag)
                CurrentNode = FirstNode;

            if (CurrentNode.NextNode != null)
            {
                CurrentNode = CurrentNode.NextNode;

                _NextNodeFlag = true;
                return true;
            }

            _NextNodeFlag = false;
            return false;
        }
    }
}

Bu örneğimizde en basit anlamıyla custom Singly Linked List nasıl oluşturulur ve Doubly Linked List mantığı nedir, elemanları arasında nasıl dönülüp araya eleman eklenir görmüş olduk.

İleriki makalelerde görüşmek dileğiyle.

 

Published in.NET

8 Comments

  1. Akçay Akçay

    Dostum eline sağlık ama bir sorum olacak boyutunu belirlemiyoruz güzel de her eleman kendinden önceki ve sonraki elemanı tutuyorsa belleği sömürmez mi normalde kullanması gereken alanın n veri için 3n-2 kadar veri tutması gerekir bu da istenmeyen birşey değil mi?

    • Buradaki “bellek sömürmeyi” kendinden sonraki elemanı tutma şeklinde gibi kıyaslamamak gerek performans ölçütü olarak. Çünkü normal bir dizide default olarak atıyorum 1000 length belirtip belleği allocate ediyorsun. Hele ki 1000 length gereksiz ise o veri için. Oysa ki buradaki sormuş olduğun durum dikkat edersen LinkedList yapısı gereğince burdaki Doubly Linked List oluyor kendinden önceki ve sonrakini tutma işlemi zaten var olan eklenmiş elemanın referans’ını tutmakta. Yeni bir eleman daha değil. O yüzden belleği sömürme işlemi olmaz ve dolayısıyla gereksiz length’ler ile belleği allocate etmişde olmayacaksın. Bunun en güzel örneği linkedlist kullanımı streaming işlemlerinde görebilirsin bilinmeyen buffer’ın length belirleme işlemlerinde ve tekrardan sıfırlama vs.

  2. Merhaba, Generic List kullanarak da aynı sonucu elde edemez miydik? Bu kadar zahmete gerek var mıydı? (Ya da bir noktayı kaçırmış olabilirim.)

    • Merhaba, aslında bunun cevabını yukarıdaki cevabımda da vermiştim. Evet, iş her ne ise yapılabilir Generic List aracılığı ilede. Enterprise seviye de veya gerçekten hafıza yönetiminin önemli olduğu durumlar üzerinde bir uygulama geliştirirken, her nasılsa C programlamada her değişkenin boyutları hesaplanarak kullanıldığı gibi C#’dada gelişi güzel nesneler türetmemeliyiz. Bu gibi durumlarda değişken boyutlu diziler için sabit boyutlu bir dizi oluşturarak memory’i doldurmak pek de iyi olmayacaktır. Onun için Linked List yapıları aracılığı ile değişken yapılara ayak uydurabiliriz en kaba tabiri ile. Hafızanın önemli olduğu durumları Masaüstü cihazlar için düşünmeyin, örneğin windows mobile işletim sistemi kullanan el terminalleri için düşünün 200mb ram’leri bulunan… Saygılarımla.

  3. Gözde Gözde

    Peki bu listeyi nasıl yazdırabilirz listenin içindekileri görmek için

    • Merhaba, örnek kodu genişletebilirsiniz veya “while (rehberList.NextNode())” satırındaki her bir current node’u ekrana yazdırabilirsiniz.

  4. Zeynel Zeynel

    Peki ya bir eleman silmek istesek bunu nasıl sağlıyacaz?

    • Güzel soru, eminim bunuda challenge amaçlı kendiniz yapabilirsiniz. 🙂 Silmek istediğiniz mevcut node ile bir önceki node’un referansları ile oynayarak eminim kolay bir şekilde yapabilirsiniz.

Leave a Reply to Akçay Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.