Linked-List Data Structure(Singly)

Veri yapıları bilindiği üzere verilerin belirli düzen içinde saklanma, yönetilme ve erişim sağlanmasında kullanılmaktadır. Düzen dediğimiz bu verilere erişimin daha verimli şekilde yapılabilmesini sağlamaktır. Erişilen bu verilerin boyutu büyük olduğunda da bunları saklayabilmek için veri yapıları avantaj sağlayabilmektedir. Özellikle bazı veri yapıları bu verilerin aranması veya sıralanmasında etkili olmaktadır.

Genel olarak farklı veri yapıları problemlere göre özelleştirilerek kullanılabilmekte ve verim açısından farklı etkileri olabilmektedir. Bu yazımızla veri yapılarının genel şemasını göstererek içerisinden hepimizin oldukça sık duyduğu ve kullandığı linked list data structure incelemesine başlayacağız.

Yukarıdaki tabloda veri yapıları temelde iki ana kategori ve onlarında altında alt başlıklarda sınıflandırılmıştır.

• Veri yapılarından ilk olarak seçtiğimiz linked list üç ana kategoride ele alınmaktadır. Linked list içerisindeki elemanların bitişik bellek konumlarında(contiguous memory locations) saklanmadığı linear bir veri yapısıdır. Her düğümün bir data alanı ve listedeki sonraki düğüme bir referans(link) içerdiği düğümlerden(nodes) oluşur.

• İlk olarak bu üç linked list veri yapısı yöntemlerinden singly yani tek yönlü bağlı liste incelenecektir. Bu yöntemde elemanlar bellekte ardışık olarak yerleştirilmemektedir. Her hücre kendisinden sonra gelen hücrenin adresini tutmaktadır. Burada kullandığımız düğüm; her bir hücrenin adı diyebiliriz. Tutulan veri ve sonraki hücrenin adresini tutan bir işaretçiden(pointer) oluşmaktadır. Buradaki veri bir sınıf türünden ya da primitive türlerden biri olabilmektedir.

• Konuyu anlayabilmek için liste için bir Node sınıfı ile içerisine düğümlerle ilgili data ve sonraki düğümün adresini tutacak işaretçi ve üye fonksiyonlar yazıldı. Düğümler oluşturulup içerisine veri atanıp liste birbirine bağlanmaktadır.

#include <iostream>

using namespace std;

struct Node { 
    Node() {} 

    ~Node() 
    {
        delete p_next;
    }

    int data{};
    Node* p_next{};
};

int main() 
{
    Node* p1 = new Node(); 
    Node* p2 = new Node(); 
    Node* p3 = new Node(); 
     
    p1->data = 5; 
    p2->data = 7; 
    p3->data = 9;
 
    p1->p_next = p2; 
    p2->p_next = p3; 

    Node* p_temp = p1;

    while (p_temp != nullptr) 
    {
        cout << p_temp->data << " ";
        p_temp = p_temp->p_next;
    }
    
    delete p1;
}
*****************************
AÇIKLAMA: 
*****************************
CEVAP:  5 7 9
*****************************

İlk örneğimiz tek yönlü bağlı liste olacaktır yani single-linked bir liste oluşturma yöntemidir. Her düğüm içerisinde yalnızca sonraki(next) düğümü gösteren bir işaretçi vardır.

• İlk örneğimizde LinkedList sınıfı ile listeye eleman ekleme ve listeden eleman çıkarma işlemleri yapılabilmektedir.

#include <iostream>
#include <string>
#include <memory>

using namespace std;

// Node class
template <typename T>
struct Node {
    T data;
    shared_ptr<Node> next;

    Node(T val) : data{ val }, next{ nullptr } {}
};

// LinkedList class 
template <typename T>
class LinkedList {
private:
    shared_ptr<Node<T>> m_head;

public:
    LinkedList() : m_head{ nullptr } {}

    void insert(T val)
    {
        auto temp{ make_shared<Node<T>>(val) };

        if (m_head == nullptr)
        {
                // Liste boşsa, yeni eleman başa eklenir.
            m_head = temp;
        }
        else
        {
               // Doluysa yeni elemanın next'i mevcut başı gösterir ve head yeni elemana kaydırılır.
            auto last{ m_head };
            
            while (last->next != nullptr)
            {
                last = last->next;
            }
            
            last->next = temp;
        }
    }

    void show_list()
    {
        auto temp{ m_head };

        while (temp != nullptr)
        {
            cout << temp->data << "->";
            temp = temp->next;
        }

        cout << endl;
    }

    void remove_in_list(T val)
    {
        auto temp{ m_head };
        shared_ptr<Node<T>> prev{ nullptr };

        while ((temp != nullptr) && (temp->data != val))
        {
            prev = temp;
            temp = temp->next;
        }

        if (temp == nullptr)
        {
            cout << "Eleman listede yok!" << endl;
            
            return;
        }

        if (prev != nullptr)
        {
                // Silinen datanın konumuna sonraki atanıyor.
            prev->next = temp->next;
        }
        else
        {
            m_head = temp->next;
        }
        
           // Kaldırılan node bellek alanı serbest bırakılır.
        temp.reset(); 
    }
};

int main()
{
    LinkedList<string> slist;

    slist.insert("Mercury");
    slist.insert("Venus");
    slist.insert("Earth");
    slist.insert("Mars");

    std::cout << "Planet List         : ";
    slist.show_list();

    slist.remove_in_list("Venus");

    std::cout << "Removed Planet List : ";
    slist.show_list();

    return 0;
}
*****************************
AÇIKLAMA: 
bu örnekte bir Node sınıfı oluşturup içerisine düğüm içerisindeki data ve sonraki düğümün adresini tutacak olan next işaretçisi bulunmaktadır.  
Diğer sınıfımız LinkedList ise, içerisinde ekleme yapan, bu listeden ilgili elemanı parametre alarak listeden çıkarma işlemi yapan ve listeyi çıkış akımına vererek gösteren fonksiyonlar yer almaktadır. 

->son düğümün adresi boş ve çıktıda -> gösterimini silebilirsiniz. C++ ile bunun farklı yöntemleri mevcuttur. :)
*****************************
CEVAP:  
Planet List         : Mercury->Venus->Earth->Mars->
Removed Planet List : Mercury->Earth->Mars->
*****************************

• Bu örneğimizde LinkedList sınıfı ile listede araya eleman ekleme işlevi yapılabilmektedir.

#include <iostream>
#include <string>
#include <memory>

using namespace std;

// Node class
template <typename T>
struct Node {
    T data;
    shared_ptr<Node> next;

    Node(T val) : data{ val }, next{ nullptr } {}
};

// LinkedList class 
template <typename T>
class LinkedList {
private:
    shared_ptr<Node<T>> m_head;

public:
    LinkedList() : m_head{ nullptr } {}

    void insert(T val)
    {
        auto temp{ make_shared<Node<T>>(val) };

        if (m_head == nullptr)
        {
                 // Liste boşsa, yeni eleman başa eklenir.
            m_head = temp;
        }
        else
        {
            // Doluysa yeni elemanın next'i mevcut başı gösterir ve head yeni elemana kaydırılır.
            auto last{ m_head };
            
            while (last->next != nullptr)
            {
                last = last->next;
            }
            
            last->next = temp;
        }
    }

    void add_element_to_list(T val, size_t pos)
    {
        if (pos == 0) 
        {
            insert(val);
            
            return;
        }
        
        auto new_node{ make_shared<Node<T>>(val) };
        auto temp{ m_head };
        shared_ptr<Node<T>> prev{ nullptr };
        size_t idx{};
        
        while ((temp != nullptr) && (idx < pos))
        {
            prev = temp;
            temp = temp->next;
            idx++;
        }
        
        if (idx < pos)
        {
            cout << "pos mevcut eleman sayısından büyük" << endl;
            return;
        }
        
        prev->next = new_node;
        new_node->next = temp;
    }
    
    void show_list()
    {
        auto temp{ m_head };

        while (temp != nullptr)
        {
            cout << temp->data << "->";
            temp = temp->next;
        }

        cout << endl;
    }

    void remove_in_list(T val)
    {
        auto temp{ m_head };
        shared_ptr<Node<T>> prev{ nullptr };

        while ((temp != nullptr) && (temp->data != val))
        {
            prev = temp;
            temp = temp->next;
        }

        if (temp == nullptr)
        {
            cout << "Eleman listede yok!" << endl;
            
            return;
        }

        if (prev != nullptr)
        {
                // Silinen datanın konumuna sonraki atanıyor.
            prev->next = temp->next;
        }
        else
        {
            m_head = temp->next;
        }
        
           // Kaldırılan node bellek alanı serbest bırakılır.
        temp.reset(); 
    }
};

int main()
{
    LinkedList<string> slist;

    slist.insert("Mercury");
    slist.insert("Venus");
    slist.insert("Earth");
    slist.insert("Mars");

    std::cout << "Planet List          : ";
    slist.show_list();

    slist.remove_in_list("Venus");
    std::cout << "Removed Planet List  : ";
    slist.show_list();
    
    slist.add_element_to_list("Uranus", 2); 
    std::cout << "Inserted Planet List : ";
    slist.show_list();
    
    return 0;
}
*****************************
AÇIKLAMA: 
*****************************
CEVAP:  
Planet List          : Mercury->Venus->Earth->Mars->
Removed Planet List  : Mercury->Earth->Mars->
Inserted Planet List : Mercury->Earth->Uranus->Mars->
*****************************

• Bu örneğimizde LinkedList sınıfına listenin başına ekleme yapan bir fonksiyon ekledik.

#include <iostream>
#include <string>
#include <memory>

using namespace std;

// Node class
template <typename T>
struct Node {
    T data;
    shared_ptr<Node> next;

    Node(T val) : data{ val }, next{ nullptr } {}
};

// LinkedList class 
template <typename T>
class LinkedList {
private:
    shared_ptr<Node<T>> m_head;

public:
    LinkedList() : m_head{ nullptr } {}

    void insert(T val)
    {
        auto temp{ make_shared<Node<T>>(val) };

        if (m_head == nullptr)
        {
                 // Liste boşsa, yeni eleman başa eklenir.
            m_head = temp;
        }
        else
        {
            // Doluysa yeni elemanın next'i mevcut başı gösterir ve head yeni elemana kaydırılır.
            auto last{ m_head };
            
            while (last->next != nullptr)
            {
                last = last->next;
            }
            
            last->next = temp;
        }
    }

    void add_element_to_list(T val, size_t pos)
    {
        if (pos == 0) 
        {
            insert(val);
            
            return;
        }
        
        auto new_node{ make_shared<Node<T>>(val) };
        auto temp{ m_head };
        shared_ptr<Node<T>> prev{ nullptr };
        size_t idx{};
        
        while ((temp != nullptr) && (idx < pos))
        {
            prev = temp;
            temp = temp->next;
            idx++;
        }
        
        if (idx < pos)
        {
            cout << "pos mevcut eleman sayısından büyük" << endl;
            return;
        }
        
        prev->next = new_node;
        new_node->next = temp;
    }
    
    void add_to_begin(T val)
    {
        auto new_node{ make_shared<Node<T>>(val) };
        
        new_node->next = m_head;
        m_head = new_node;
    }
    
    void show_list()
    {
        auto temp{ m_head };

        while (temp != nullptr)
        {
            cout << temp->data << "->";
            temp = temp->next;
        }

        cout << endl;
    }

    void remove_in_list(T val)
    {
        auto temp{ m_head };
        shared_ptr<Node<T>> prev{ nullptr };

        while ((temp != nullptr) && (temp->data != val))
        {
            prev = temp;
            temp = temp->next;
        }

        if (temp == nullptr)
        {
            cout << "Eleman listede yok!" << endl;
            
            return;
        }

        if (prev != nullptr)
        {
                // Silinen datanın konumuna sonraki atanıyor.
            prev->next = temp->next;
        }
        else
        {
            m_head = temp->next;
        }
        
           // Kaldırılan node bellek alanı serbest bırakılır.
        temp.reset(); 
    }
};

int main()
{
    LinkedList<string> slist;

    slist.insert("Mercury");
    slist.insert("Venus");
    slist.insert("Earth");
    slist.insert("Mars");

    std::cout << "Planet List             : ";
    slist.show_list();

    slist.remove_in_list("Venus");
    std::cout << "Removed Planet List     : ";
    slist.show_list();
    
    slist.add_element_to_list("Uranus", 2); 
    std::cout << "Inserted Planet List    : ";
    slist.show_list();
    
    slist.add_to_begin("Saturn"); 
    std::cout << "PreInserted Planet List : ";
    slist.show_list();
    
    return 0;
}
*****************************
AÇIKLAMA: 
*****************************
CEVAP:  
Planet List          : Mercury->Venus->Earth->Mars->
Removed Planet List  : Mercury->Earth->Mars->
Inserted Planet List : Mercury->Earth->Uranus->Mars->
Removed Planet List  : Saturn->Mercury->Earth->Uranus->Mars->
*****************************