Linked Lists

LLler ucu bucağı olmayan arrayler gibidir fakat uygulamaları biraz karmaşıktır. LLler bir veri yapısı aracılığıyla tanımlanır ve veri yapısının içerisinde belli değişkenler tutulur. Bu değişkenlere ek olarak her bir itemı birbirine bağlamak için bir pointer tutulur. Bu sayede tüm itemlar birbirine bağlanarak bir liste yada bir array oluşturulur.

LLlerde ilk olarak yapmamız gereken şey bir data structure tanımlamaktır. Data structure ‘ın tanımı;

struct linkedList {

int studentID;

struct linkedList *next;

};

Burada struct linkedList diyerek linkedList adında veri yapısı tanımladık. Bu veri yapısının içerisinde öğrenci numaralarının tutulduğu bir değişken ve veri yapısının kendisinin bir pointerı var. Aslında daha fazla şey olabilir. Mesela char *studentName vb gibi.. daha bir çok değişkeni içeride tanımlamak mümkün ve normalde zaten bu kadar basit ya da sade olmaz. Genelde data structure içerisinde bir çok tipte değişken olur. Bu arada bu pointer da nereden çıktı demeyin. Bu linked list in oluşmasındaki temel öğelerden biridir. Burada pointer koymaktaki amaç ileride de daha iyi anlayacağınız gibi veri yapılarını bir birine bağlamak. Peki neden struct linkedList diyerek tanımladıkta int diyerek tanımlamadık derseniz şöyle bir açıklama sanıyorum mantıklı olur. Biz biliyoruz ki bir integer pointer tanımlarken int *degisken diyoruz. Yani int değişkenin türü. İşte aslında data yapılarıda bir değişken olduğundan ve biz de kendi oluşturduğumuz data structure için bir pointer oluşturmak istediğimizden next pointerının başına struct linkedList dedik. Ayrıca burada next in özel bir durumu yok dilersek subuti bile diyebilirdik yani yine mantıktan çıkartacağımız üzere eğer struct linkedList int gibi bir typesa o zmn *next de bir değişkendir. Bu açıklamalardan sonra gelelim bir sonraki adıma, bir sonraki adımda şunu yazacağız,

typedef struct linkedlist *list;

Bunu yazmakta ki amaç şu, biz biliyoruz ki typedefi kendi değişkenimizi oluşturmak için kullanırız. Fakat burada yeni bir type oluşturmuyoruz. Var olan typeın adını değiştiriyoruz. Ne gibi mesela typedef int ahmet dediğimizde ahmet artık int yerine kullanılabilen bir veri tipi oldu. ahmet numara=10; şeklinde bir kullanabiliriz. Biz yukarıda da söylediğim gibi biz az önce struct linkedList adında bir tip tanımladık. Bunu kullanırken nasıl ki int variable; diyorsak struct linkedList variable diyeceğiz ama bu, programı yazarken hem uzun hemde programı anlama açısından (başka bir kod yazıcısı için..) karmaşık bir şey. İşte bu uzun değişken tanımlamayı daha sade görünümlü ve anlaşılır yapabilmek için typedef komutunu kullandık. Artık struct linkedlist yerine sadece list yazsakta aynı şey olur veeee unutmuyoruz kii list artık bizim int gibi bir veri türümüz. Burada bir diğer ayrıntı yeni veri tipini *list olarak değiştirdik. Bunun nedeni şu; bildiğiniz gibi pointerlar memorydeki adresleri tutuyor. Burada memoryle direk ilişkili bir iş yapıyoruz (aslında herşey memoryle ilişkili bu söz biraz garip oldu ama anladınız sanıyorum anlatmak istediğimi) ve linked listin her elemanı memoryde bir yerde duruyor. Bu sebeple bizim onların adreslerini tutuyor olmamız gerekiyor. Tüm itemları birbirine bağlamak için ve her bir item bir pointer olarak tutulduğu için zaten bir next diye bir pointer tanımladık.

Şimdi sırada gerçek bir item oluşturma adımı var. Şimdi listenin en başını gösterecek olan head, o an nerede olduğumuzu gösteren bir head adında bir item oluşturuyoruz.

list head, save, temp;

Burada oluşturulan temp o an elimizde geçici olarak tutmak istediğimiz bir item için ve savei de daha başka işlerde kullanmak amacıyla tanımladık. Daha sonra ana programda head liste boş olduğu için NULLa eşitleyeceğiz. Bu eşitlik bize listenin sonuna geldiğimizi anlatacak. Bir item eklerken yada bir veriyi liste üzerinde arama yaparken listenin sonuna gelip gelmediğimizi işte bu NULL sayesinde anlayacağız.

Sıra listeyi doldurmaya geldi fakat buraya kadar olan şeyleri genel olarak toparlamak ve anlatılanları tek bir resimde görmek amacıyla bir kod olarak yazıyorum.

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

//veri yapısı

struct linkedList {

int studentID;

struct linkedList *next;

};

//tanımlar

typedef struct linkedList *list;
list head, temp, save;

//ana program

int main(){
head = NULL;
system(“pause”);
return 0;
}

 Arkadaşlar kod tam anlamıyla çalışmayabilir, kafadan yazdım test etmedim. Umarım neyin nerede olduğuna dikkat etmişsinizdir. Neyi nerede tanımlıyoruz, nasıl yapıyoruz ıdı ve bıdı …

Gelelim item eklemeye, bunun için bir fonksiyon yazacağız. Fonksiyon içerisine sadece studentID için bir veri alacak çünkü diğer head vsler globalde tanımlı ana programda tanımlanmadığından onlarıda fonksiyona göndermeye gerek yok. Şimdiiiii o zaman fonksiyon şöyle olacak,

void insertBeginning (int data){

temp=(list)malloc(sizeof(struct linkedList));

temp -> studentID = data;

if(head==NULL){

head=temp;

head -> next = NULL;

}

else{

temp -> next = head;

head=temp;

}

}

Yukarıdaki fonksiyonda hali hazırda temp diye yukarıda tanımladığımız item için hafızada yer ayırdık. malloc önündeki (list) kısmı cast için gerekli çünkü değişken tipi list. Burada mantık şu, temp diye bir item var ve biz hafızada bir yer ayırıyoruz buna sonra bu item içindeki değişkeni listeye eklenmek istenen değişkene ekliyoruz. Bu sayede elimizde listeye eklenmek üzere hazırlanmış içinde kullanıcının listeye eklemek istediği bir item var. Bu olay bir paketleme işlemi gibi, satılacak mal bir pakete konuyor ve paket içinde şampuan ve bir açıklama zıbıdığı var atıyorum. Sonra bir bu küçük paketi daha sonra dağıtıma gönderilecek kolilere koyacağız. Koliyide mm neydi heh liste olarak düşünün.. Çaktınız mı köfteyi?? Kullanıcı datası parfüm oluyor ve biz onu item içerisine koyuyoruz. Item aslında paket, daha sonra o paketi de koli içine koyacağız. Evet az önce paket hazırlamayı anlattım sıra koliye yerleştirmekte. Burada bir itemı listeye yerleştirmenin farklı yolları var. Ben her geleni en başa koydum. Burada mantık şu; head eğer NULL sa bu liste miste ortada yok demektir. O zmn gelen paketi (temp) head paketine eşitle bu sayede elimizde yani kolide bir paket oldu. head -> next = NULL satırı da bir sonra ki item ekleme işleminde kullanılmak için yazılmış bir kod. Bu kodun tek amacı bu değil. İlk başta da söylediğim gibi NULL sayesinde listenin sonuna geldiğimizi anlıyoruz. Bu nedenle bu NULL un iki işlevi var. Farz edelim ki head NULL değil yani listede boş değil.. Bu durumda alternatif bir yolumuz daha olmalı, bu durum için şöyle bir yol izliyoruz; hani yukarıda temp diye bir paket yaptık ya o paketi listenin başına getiriyoruz. Bu da şöyle oluyor hani head en baştaydı ya, daha sonra heade bir item bağlıydı ve o itema başka bir item sonra onada başka bir tane sonra onada onada onada … öyle gidiyor. İşte düşün şimdi headle başlayan bir liste var, kafanda hayal et böyle ipe dizilmiş boncuklar gibi, sonra sen bir tane boncuğu alıp ipe geçiriyorsun ve temp -> next = head diyerek geçirdiğin boncuğun bir sonraki gösterge zıbıdığını heade bağlıyorsun. Bu durumda temp aslında senin yeni headin oluyor. ama bu olmaz o yüzden bir o head=temp diyerek headi başa almış oluyoruz. Burada eşitlemede kafanız karışmasın. Head göstermelik bir şey gibi böyle bir etiket o. Pointer olduğundan sen neye eşitlersen onun özelliklerini alır. Sen şimdi burada head=temp diyorsun ya hani temp baş olmuştu işte headde böylelikle yenilenen baş oluyor.

LLlerde ekleme bu şekilde fakat tüm işler bununla sınırlı değil bir veriyi arama silme vb işlemlerde mevcuttur. Ben onları burada anlatmayacağım çünkü o kadar zamanım yok ne yazık ki.. Eğer vakit bulursam on işlemlerin anlatımlarınıda buraya eklerim.

sadican


Yorum Gönderin

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir