c programlama dilinde linked list (bağlı listeler)

Bir zaman önce C dilinde yapılar ve kullanımları (structures in C) başlıklı bir yazı yazmıştım. Eğer struct konusuna hakim değilseniz bir göz gezdirmenizi öneririm.

Bu yazımda, C programlama dilindeki linked listlerin ne olduğundan, neden ihtiyaç duyduğumuzdan bahsedeceğim. Ardından da kod parçacıkları ile örnek vereceğim.

Linked List nedir?

Düğüm (node) adı verilen ve göstericiler (pointer) sayesinde birbirine bağlanan kendine dönüşlü yapıların doğrusal bir şeklidir.

Bu noktada kendine dönüşlü yapının ne demek olduğuna örnek vermek gerekirse;

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

Buradaki Node ismindeki struct, içerisinde data isminde int türünde bir değişken ve kendi tipinde bir struct gösteren pointer’a sahiptir. Buna kendine dönüşlü yapı denmektedir. Bu tanım şu an hafızamızda pek yer etmemiş olabilir, yazının devamında neden böyle birşey yaptığımızı daha iyi anlayabiliriz.

Linked list tanımını yaparken bir de doğrusal diye bir terim kullandık. Bunun anlamı esasında fiziksel olarak değildir. Hafızada, her node farklı bir yerde olur, ancak biz çalışmamız sırasında işlerimizi rahat ilerletebilmek için buna doğrusal deriz. Çünkü kağıda kalemle çizdiğimizde, linked listlerde her node birbirinin ardından gelir. Yazının devamında göreceğiz.

Bir linked liste, listin ilk düğümünü gösteren gösterici sayesinde erişilir. Ve genellikle son düğümdeki pointer, listin sonu olduğunu belirtmek amacıyla NULL değere eşitlenir.

Linked listlerde veriler dinamik olarak tutulur. Yani her düğüm ihtiyaç olduğunda silinir veya oluşturulur. Yukarıda kendine dönüşlü yapılardan bahsetmiştim. Bir linked list içerisinde sadece kendi tipinden değil, başka türden structlar da olabilir. Yani sadece kendi tipinden structlar olacak diye bir kural yoktur.

Linked list oluştururken ilk olarak yapmamız gereken malloc ve sizeof işlemlerini kullanmaktır. sizeof ile elimizdeki structın boyutunu alırız, ve malloc fonksiyonu ile hafızada o kadar alanlık bir yer ayırırız.

Linked listlere yeni bir düğüm ekleme işlemini 3 farklı yere yapabiliriz. Listenin en başına, listenin en sonuna, ve herhangi iki düğüm arasına.

Şöyle bir yapı oluşturduğumuzu düşünelim;

typedef struct linked_list {
    int data;
    struct linked_list *next;
} NODE;

Bu şekilde bir yapıya art arda yeni düğümler eklemek için aşağıdaki kod parçacığını kullanabiliriz.

void insert(int value){

    if(head==NULL){ /// ilk düğüm oluşturulmadıysa önce onu oluşturuyoruz.
        head = (NODE *)malloc(sizeof(NODE));
        head->data = value;
        head->next = NULL;
        tail = head; /// Sadece ilk düğüm için, head = tail
    } else {
        NODE *temp = (NODE *)malloc(sizeof(NODE)); /// Eklenecek düğümler için memory allocation
        temp->data = value;
        temp->next = NULL;
        tail->next = temp;
        tail = tail->next;
    }
    printf("Eklenen data %d\n", value);
}

Listeye başından ekleme yapmak için şu kod parçacığını kullanabiliriz;

void head_insert(int value){

    if(head==NULL){ /// İlk düğüm oluşturulmadıysa..
        head = (LL *)malloc(sizeof(NODE));
        head->data = value;
        head->next = NULL;
        tail = head; /// Sadece ilk düğüm için, head = tail
    } else {
        NODE *temp = (NODE *)malloc(sizeof(NODE)); /// Eklenecek düğümler için memory allocation
        temp->data = value;
        temp->next = head;
        head = temp; /// Listenin başına yeni düğüm ekledik.
    }
    printf("Listenin başına eklendi --> %d\n", value);
}

Herhangi bir elemandan önce veya sonra ekleme yapmayı da aynı yukarıdaki mantıkla yapabiliriz. while döngüsü ile listeyi dolaşırız. Oluşturduğumuz yeni düğümü veri kaybı olmadan iki düğüm arasına yerleştiririz.

void insert_after(int insert, int foo){ ///insert değerini foo değerinden sonrasına ekliyoruz
    LL *curr, *temp; /// gerekli işlemleri yapabilmek için 2 pointera ihtiyacımız var
    if(head!=NULL){ /// tabi ki bu işlemi liste boş değilse yapabiliriz
    
        curr = head; /// listenin en başından başlayacağız.

        while(curr!=NULL){ /// next değeri NULL olan elemana kadar listeyi dolaşıyoruz (yani listenin sonuna kadar)        
            if(curr->data==foo){ /// aradığımızı bulduk
            
                temp = (NODE *)malloc(sizeof(NODE));
                temp->data = insert; 
                temp->next = curr->next;
                if(curr->next==NULL){
                    tail = temp; 
                }
                curr->next = temp;
                curr = curr->next; 
            }
            curr = curr->next; /// aradığımızı bulamadıysak bulunduğumuz düğümden bir sonrakine geçiyoruz
        }
    }
}

Daha sonraki yazılarımda linked listler ile ilgili farklı örnekler de vereceğim.

C dilinde yapılar ve kullanımları (structures in C)

Struct nedir?

Struct(yapılar), birbirleriyle ilişkili olan değişkenlerin bir arada tutulması, tek bir isim altında toplanmasıdır.
Kabaca bir örnek vermek gerekirse; bir öğrenci struct‘ımız olsun (ismine ogrenci diyelim). Bir öğrenciye ait hangi bilgileri tutabiliriz? Öğrenci ismi, okul numarası, cinsiyet, okul ismi, vs.

Peki bu structı nasıl oluştururuz?

struct ogrenci{
	char *isim[30];
	char cinsiyet;
	int okulNumarasi;
	char *okul[30];
};

Önemli: Struct tanımladıktan sonra noktalı virgülü unutmak hataya yol açar.

Görüldüğü gibi, bir yapının içerisinde birden fazla türde değişken tanımlayabildik. Bu yapı içerisinde isim ve okul için karakter dizisi elemanı, okul numarası için int tipinde bir eleman, cinsiyet için de E ve ya K içerebilecek bir char tanımladık.

Yaptığımız işlem sadece yeni bir değişken türü tanımlamak oldu, hafızada bu işlem için bir yer ayrılmadı! Yani int ya da char nasıl bir değişken türüyse, şu an ogrenci de bizim için yeni bir değişken türü oldu.

Dolayısıyla biz oluşturduğumuz yapı türünden istediğimiz sayıda değişken bildirebiliriz. Ama nasıl?

3 adet öğrenci olsun elimizde, bunlara gokhan, emre, ahmet diyelim.
Biz bunların ne olmasını istiyoruz? struct ogrenci tipinde birer değişken olmalarını istiyoruz. Öyleyse bu değişkenleri bildirmeliyiz;

struct ogrenci gokhan, emre, ahmet;

Şimdi sıra geldi bunları kullanmaya. Tanımladığımız her değişken, yani gokhan, emre ve ahmet ayrı ayrı, birbirinden bağımsız olarak, her biri, struct ogrenci içinde tanımladığımız değişkenlere sahiptir. Biraz daha açık yazmak gerekirse, gokhan için kullanacağımız char okul[30] ile ahmet için kullanacağımız char okul[30] birbirinden bağımsızdır. Bunların içlerinde aynı şeyler olabilir, ama birbirleriyle bir alakaları yoktur.

Öyleyse, struct ogrenci tipinde tanımladığımız değişkenlerimiz için değer atamaya başlayalım.

Burada kullanacağımız 2 adet operatör var. Biri yapı elemanı operatörü olan nokta (.), diğeri de yapı gösterici operatörü olan ok (->)[arasında boşluk olmadan eksi işareti ve büyüktür işareti].

Mesela, gokhan değişkenine okul numarası atayalım her iki yolla da.
Yapı elemanı operatörü’nü yani noktayı kullanırken işimiz çok kolay.

gokhan.okulNumarasi = 5210010;

Aslında yapı gösterici operatörü kullanmak da bir o kadar kolay.
gokhan için bir adet gösterici bildirelim, gPtr olsun adı. Burda önemli olan, bu göstericimizin türünün de struct ogrenci olacağı.

struct ogrenci *gPtr;
gPtr = &gokhan;

Görüldüğü gibi gokhan‘ın adresini gPtr‘ye atadık. Şimdi de ok (->) nasıl kullanılır ona bakalım.

gPtr->okulNumarasi = 5210010;

Mesela emre‘ye isim atayalım;

struct ogrenci emre;
struct ogrenci *ePtr;
ePtr = &emre;

ePtr->isim[30] = "Emre";

Bunların printf içerisindeki kullanımları da aynı şekildedir.

printf("%s", ePtr->isim[30]);

diyebiliriz mesela.

typedef nedir?

typedef anahtar kelimesini kullandığımızda, yapımız için yeni değişken tanımlarken struct kullanmak zorunda kalmayız.

struct ogrenci{
	char *isim[30];
	char cinsiyet;
	int okulNumarasi;
	char *okul[30];
};

struct ogrenci gokhan;

Bunu typedef kullarak şu şekilde yaparız;

typedef struct{
	char *isim[30];
	char cinsiyet;
	int okulNumarasi;
	char *okul[30];
}Ogrenci;

Ogrenci gokhan;

Önemli: ogrenci ve Ogrenci birbirinden farklıdır!

Görüldüğü gibi değişken tanımlarken tekrar struct yazmıyoruz, typedef sayesinde bir bakıma takma isim kullanmış oluyoruz.

Ayrıca gokhan, emre, ahmet gibi struct ogrenci tipinden değişken tanımlamasını şu şekil de yapabiliriz;

struct ogrenci{
	char *isim[30];
	char cinsiyet;
	int okulNumarasi;
	char *okul[30];
};

typedef struct ogrenci Ogrenci;
Ogrenci gokhan, emre, ahmet;

Yapılarla kullanılan geçerli işlemler, yapı değişkenlerini aynı tipte yapı değişkenlerine atamak, bir yapı değişkeninin adresini almak, yapı değişkenlerine erişmek, ve yapı değişkeninin boyutunu belirtmek için sizeof kullanmaktır.

sizeof kullanımına örnek verecek olursak;

printf("%ld", (long) sizeof(struct ogrenci));

Bunun çıktısı bize, struct ogrenci tipinden bir değişkenin hafızada kaç byte tutacağını gösterir.