C İle Linked List Oluşturma

Eleman ekleme ve çıkarma işlemlerinin herhangi bir sıralama olmaksızın yapılabildiği, bellek ve zaman tasarrufu konusunda liste ve dizilere nazaran daha avantajlı, fakat kodlaması daha zor olarak görülen doğrusal veri yapısına Linked List (Bağlı Liste) denir.

4 çeşit linked list bulunmaktadır:

• Singly Linked List (Tek Yönlü)
• Doubly Linked List (Çift Yönlü)
• Circular Linked List (Dairesel)
• Doubly Circular Linked List (Çift Yönlü Dairesel)

Singly Linked List

Bir linked listteki her bir elemana node ismi verilir. Singly list için her bir node Data ve Next‘ten oluşur. “Data” veriyi tutarken “next” ise kendinden sonraki node’un adres bilgisini tutar. Eğer node, linked list’in son elemanı ise başka bir node’u işaret edemeyeceği için tutacağı değer NULL olur. Linked listteki ilk node’a head ismi verilir. Diğer tüm node’lara bu “head node”u üzerinden ile erişim sağlanır. Bir linked listteki head node’una erişim sağlanamazsa diğer node’larada erişim sağlamak mümkün değildir.

Aşağıdaki görsel bir singly linked listi temsil etmektedir.

C dili ile basit bir şekilde singly linked list yapısını oluşturabiliriz.

Öncelikle node isminde global olarak bir struct oluşturuyoruz. Bu node struct’ının içerisinde “integer” veri türünde data değişkeni ve bir sonraki node’un adresini tutan next değişkenini node struct’ı içerisinde tanımlıyoruz.

struct node {
    int data;
    struct node *next;
};

Sonrasında oluşturduğumuz “node structı”nı kullanarak, linked listin ilk elemanı olan “head”i bellekte yer kaplayacak şekilde “malloc” fonksiyonu kullanarak main fonksiyonunda tanımlıyoruz.

struct node *head = (struct node *)malloc(sizeof(struct node));

Yukarıdaki “(struct node *)malloc(sizeof(struct node))” ifadesi linked listte her yeni bir node ekleme işlemi yapılırken node’un bellekte yer kaplaması için kullanılması gerekiyor

Oluşturduğumuz head node’unun “data” ve “next” değerlerine atamayı artık yapabiliriz. Data değerine herhangi bir tamsayı değerini (örneğin 10), next değerine ise şimdilik NULL ifadesini atıyoruz. Çünkü head node’u linked listin ilk node’u iken aynı zamanda linked liste başka bir node yer almadığı için son node’u da olmuş oluyor.

head->data = 10;
head->next = NULL;

Linked liste ilk node’u yani head’i oluşturduk . Şimdi head’in işaret ettiği diğer node’u oluşturalım .

Sıradaki node’u “temp” isminde geçici bir değişkende “head node’unu” oluşturduğumuz şekilde oluşturuyoruz.

struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = 5;
temp->next = NULL;

Artık head ve temp isminde iki adet node’a sahibiz. Bu iki node’u birbirine bağlamak için head’in next’i NULL yerine temp’teki node’un adresini işaret etmesi gerekiyor. Bunun için head’in next değerine temp’i atıyoruz.

head->next = head->next = temp;

İki node’dan oluşan basit bir singly linked list oluşturduk. Linked List’e yeni bir node eklemek için yine aynı işlemleri yapabiliriz.

temp = (struct node *)malloc(sizeof(struct node));
temp->data = 15;
temp->next = NULL;

head->next->next = temp;

Head’in next’i bir node olduğu için (Head son node olmadığı için) head’in next’inin next’ine yeni node’u atıyoruz.

Böylelikle bir singly (tek yönlü) linked list oluşturmuş olduk.

Sayfadaki kodun tamamı:

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

void main() {
    struct node *head = (struct node *)malloc(sizeof(struct node));
    head->data = 5;
    head->next = NULL;

    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = 5;
    temp->next = NULL;

    head->next = temp;

    temp = (struct node *)malloc(sizeof(struct node));
    temp->data = 5;
    temp->next = NULL;

    head->next->next = temp;
}

Doubly Linked List

Doubly linked list aynen singly list gibi fakat kendinden sonraki node’u next ile işaret etmesinin yanı sıra kendinden önceki node’u da prev ile işaret etmektedir. İlk node olan head’den önce başka bir node olmadığı için head’in prev değeri NULL olacaktır.

Aşağıdaki görsel bir doubly linked listi temsil etmektedir.

C ile doubly linked listi, singly liste benzer şekilde struct yapısına prev işaretçisini ekleyerek oluşturabiliriz.

struct node {
    int data;
    struct node *next;
    struct node *prev;
};

Circular Linked List

Circular linked list, singly linked list gibi tek yönlü fakar son elemanı NULL yerine head’ı işaret ederek dairesel bir yapı oluşturur.

Aşağıdaki görsel bir circular linked listi temsil etmektedir.

Doubly Circular Linked List

Hem çift yönlü hem de dairesel olan linked list türüdür. Circular linked listten farklı olarak node’ların prev değerleri vardır.

Aşağıdaki görsel bir doubly circular linked listi temsil etmektedir.