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:

Yukarı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.