Veri Yapıları - Singly Linked List

By Burak TUNGUT - 25.11.2012 - 3 Yorum - Kategori C / C++

Dün yazdığım makale ile Veri Yapılarına ve Struct tanımlanmasına ilişkin güzel bir örnek incelemiştik. Bugün ise sizlerle yeni bir yapıyı yanı Linked List yapısını inceliyor olacağız. Makaleye başlamadan önce şunu söylemeleyim ki ilk defa bu konuya başlayacak olanlar ve pointerlar ile arası iyi olmayanlar hatta olaya biraz eğlenceli bakmak isteyenler kesinlikle yapacağımız bu yapıda tren vagonlarını düşünsünler :) Umarım tren yolculuğundan hoşlanıyorsunuzdur çünkü yolculuğumuz başlamak üzere :)

Yazdığımız Struct İçin Bir Array Düşünelim

Yukarıda linkini verdiğim makaleyi şöyle bir göz önüne alalım. Hatırlarsanız Ogrenci adında bir struct tanımlayıp üzerinde çok küçük bir kaç işlem yapmıştık. Birde Ogrenci yapısından bir array tanımladığımızı. Bunu düşünmek hiçte zor değil nasıl int için bir array tanımlıyabiliyorsak, kendi yaptığımız bir yapı içinde tanımlayabiliriz.
Fakat ne yaparsak yapalım bu arrayin bir sınırı olmak zorunda. Hatta C# ve Java da olduğu gibi C++ da runtime anında belirleme şansımız olmayan bir sınır :)

Son cümlemi biraz açacak olursam ; C# ve Java da bir array tanımlarken, kodlama esnasında sınır bildirmek zorunda değilsiniz. Bu işi runtime yani uygulamanın çalışma esnasında da yapabilirsiniz. Fakat C++ da böyle bir imkanımız yok. Bu da demektirki öyle bir yapı tercih etseydik çalışma anında bile belirleyemediğimiz bir sınır dahilinde olacaktık.

Neden Linked List ?

Konu başlığımız linked list idi ama halen bu konuda fazla söz etmedik :) Aslında yukarıdaki senaryoya devam edelim. Bizim şu anda tek ihtiyacımız Mr.Muscle'ın reklamlarında olduğu gibi eski yapıyı silip, bizi kurtaracak yapıyı getirecek bir süper kahraman. İşte bu süper kahraman sizsiniz ve yeni yapımız ise Linked List.
Yukarıda dediğimiz gibi array bizim için bir yere kadar çözüm sonuçta sınırı var fakat linked listin böyle bir engeli yok. Tabiri caizse "Ekle Ekleyebildiğin Kadar". Tek bir engelimiz var o da bilgisayarımızın RAM'i. Sonuçta 8byte'lık bir yapı ile memory de sızma yapacak kadar da ekleme yapmayız herhalde :) . Sınırları zorlarım diyenleri duyar gibiyim :)

Linked List = Sonsuz Kayıt

Linked List'i anladık, peki Singly'de ne ?

Aslında şimdi söyleceklerim tamamiyle teoride ve haliyle aklımızda da bir bulut gibi havada kalacak. Hiç uzatmadan tıpkı ders kitaplarının bizlere herşeyi harika öğretiyormuş gibi (Umarım mesaj gitmiştir :) ) bende şunu söyleyebilirim ki, tek yönde hareket etme kabiliyetine sahip linked list'e, Singly Linked List denir.

Trenimizi dizayn edelim

Artık işimize geri dönelim ve senaryomuzdan bahsedelim. Bugün ki amacımız içersine int bir değer verebileceğimiz bir linked list yapısı tasarlamak. Kısacası ucu bucağı olmayan bir sayı listesi tasarlayıp, ekleme, silme, bulma gibi fonksiyonlar yazacağız.
Şimdi ise bir vagon düşünelim. Bu vagon sadece iki bölmeden oluşsun, bir bölmede sayımız (Data), diğer bölmede ise ondan sonra gelen vagonu gösterecek bir pointer (Next) olsun. Aslında burda yapacağımız struct içeriğinide belirlemiş olduk. Demek ki struct içeriğimizde bir adet int ve bir adet söz konusu struct yapısını gösteren bir pointer olacak.

Lokomotif nerede ?

Hemen şunu söylemeleyim ki artık lokomotif demiyor, ona Head diyoruz. Sonuçta yukarıdaki gibi biz her bir sayı eklediğimizde bizim bir vagonumuz olacak e haliyle bunlarıda çekecek en başta bir lokomotif, pardon Head olmalı. Çünkü biz eklediğimiz bu sayıları bir array içersinde tutmayacağız haliyle bize tüm işlemlerde hangi vagondan başlayacağımızı gösterecek bir yapıya ihtiyacımız var ki bu da bizim Head değişkenimiz olacak.

Teorik bilgimizi simülize edelim

Aşağıda gördüğünüz resimde içinde A,B,C,D yazan vagonlarımız iki bölmeden oluşup, sağ taraftaki bölmeden diğer vagona bağlanmışlar. First Node dediğimiz vagon ise bizim ilk vagonumuz yani Head burayı gösterecek, Last Node ise son vagonumuz ki bunu ayrıca tutmaya hiç gerek yok çünkü bir düşünelim tüm vagonlar bir sonrakini gösterecek fakat Last Node son vagon olduğu için sonraki vagonu gösteren pointerımız NULL olacak.

Singly Linked List

Linked List yapısında mutlaka ilk vagonu elimizde tutmalı, son vagonun ise Next kısmının NULL olduğunu unutmamalıyız!

Struct Tanımlamamız ve Method Implementasyon

Uygulamada kullanacağımız structımızın içeriğinde bir adet int ve bir adetde pointer olacağını tekrar hatırlayalım ve tüm methodlarımızı main methodunun altında yazacağımızdan dolayı main methodunun yazdığımız diğer methodlardan haberdar olması gerektiği için de bunları implemente edelim.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
struct Yapi{
	int Data;
	Yapi* Next;
};
typedef Yapi* ptrType;
ptrType Head;
void Baslat();
void BellekAl(ptrType*);
void BellekBosalt(ptrType);
void Listele();
void Ekle(int,int,bool);
void Bul(int,ptrType*,int*);
void Sil(int);

Yukarıda bulunan method imzaları ile artık uygulamamızda olması gereken tüm fonksiyonalitelerden bilgi sahibiyiz. Son olarakda bir type definitional bildiriminde bulunmuşuz. Burdaki tek amacımız uygulama içersinde sık sık Yapı* yazmaktansa ptrType yazarak aynı işlemi gerçekleştirebilmek.

Baslat, BellekAl ve BellekBosalt methodlarımız

void Baslat()
{
	Head=NULL;
}

void BellekAl(ptrType* veri)
{
	*veri=(ptrType)malloc(sizeof(Yapi));
}

void BellekBosalt(ptrType veri)
{
	free(veri);
}

Söz ettiğimiz ilk 3 methodumuz yukarıdaki gibi olmalıdır. main methodunda ilk çağıracağımız method Head'ın NULL olarak atanması için Baslat methodu olacaktır. Her bir kayıt eklediğimizde ise bellekden Yapı (int + Yapı) kadar yer alması için BellekAl methodunu ve silme işleminde ise bellekden temizlenme işlemini gerçekleştirecek BellekBosalt methodlarını kullanacağız.

Listele methodu

void Listele()
{
	ptrType temp = Head;
	while(temp!=NULL)
	{
		printf("\n%x adresindeki deger : %d\n",temp,temp->Data);
		temp=temp->Next;
	}
}

Yukarıdaki method ile tüm vagonlarımız üzerinde gezerek Listeleme işlemini gerçekleştireceğiz. Aslında izlememiz gereken yol son derece açık ve basit. Öncelikle ilk vagonumuzu tutan Head değişkenini kaybetmemek için başka bir değişken içersine aktarıyoruz. Amacımız ise bir vagon içersindeki sayıyı yazdırdıktan sonra diğer vagona geçmek bunu temp=temp->Next; işlemi ile gerçekleştiriyoruz. Döngümüz neden temp NULL olana kadar devam edecek dersek ise unutmalayalım ki son vagonumuzun Next değeri başka bir vagonu göstermediği için NULL olacaktı. Bu da demektir ki Next alanı NULL olana kadar her vagonun içeriğini yaz ve sonraki vagondan devam etmek için kontol değişkenini artık o anki vagonun gösterdiği yer ile değiştirmek olacaktır.

Bul methodu

void Bul(int sayi, ptrType* adres, int* sonuc)
{
	*sonuc=-1;
	ptrType temp=Head;
	while(temp!=NULL)
	{
		if(temp->Data == sayi)
		{
			*adres = temp;
			*sonuc=1;
			break;
		}
		temp=temp->Next;
	}
}

Eklediğimiz tüm sayılar içersinde arama yapmak içinde bir methodumuz olmalıdır ki bu da tıpkı yukarıdaki gibi olacaktır. Methodumuz parametre olarak aranan sayıyı ve bulunması halinde değerlerini değiştirmek üzere adres ve sonuc adında pointerlar alıyor.

Method ilk çağrıldığında aslında bize gönderilen sonuc pointerının içeriğini -1 yani bulunamadı yapıyoruz ve Listeleme de olduğu gibi ilk vagonu gösteren Head değişkenimizi başka bir değişkene aktarıp aynı döngüyü açıyor sadece içersinde bir kontrol bloğu yazıyoruz. Kontrol bloğumuz ise üzerinde gezinilen vagonun Data (sayıyı içeren bölme) bilgisinin aradığımız sayı ile aynı olup olmadığını kontrol ediyor, aynı olması halinde adres olarak bu vagonu ve sonuc olarakda 1 geriye döndürerek break; komutu ile döngüyü sona erdiriyoruz. 

İlk başta sonuc pointerını gösteren değişkenin içeriğini -1 yapmıştık ki bulunması halinde içerik 1 olarak değiştirilsin, bulunamazsa aynen kalsın.

Sil methodu

void Sil(int sayi)
{
	ptrType temp;
	int sonuc;
	Bul(sayi,&temp,&sonuc);
	
	ptrType onceki = Head;
	while(onceki!=NULL)
	{
		if(onceki->Next==temp)
			break;
		else
			onceki=onceki->Next;
	}
	onceki->Next = temp->Next;
	BellekBosalt(temp);
}

Sil methodumuz ne kadar da yardım sever, sadece bir parametre alıyor. Öncelikle silmek istediğimiz sayının daha önce eklenip eklenilmediğini kontrol etmemiz gerekiyor. Bunun içinde Bul methodu çağırmamız, e bunun içinde geri dönmesi için bir adet int ve bir adet de ptrType tipinde olacak değişkenler tanımlıyor ve Bul methodunu çağırıyoruz. Eğer bulunursa temp değişkenimiz silmek istediğimiz vagonumuz ve sonuc da 1 olarak geri dönecektir.

Burda dikkat etmemiz gereken çok önemli bir nokta var ! Biz bir vagonu sildiğimizde, bu vagondan bir önceki vagonun da Next kısmını değiştirmemiz gerekir. Şöyle ifade edelim ; X -> Y ->  Z bunlar bizim vagonlarımız olsun. Biz Y vagonunu silmek istiyorsak X artık Z yi göstermelidir!

Bunun içinde bir döngü açıyoruz. Amacımız öyle bir vagon bulalım ki bu vagonun Next kısmı bizim silmek istediğimiz vagon olsun yani silmek istediğimiz vagondan bir önceki vagonu bulalım. Listeleme ve Bulma işlemindeki gibi aynı mantıkla açtığımız döngü ile bir önceki vagona ulaşıp, bu vagonun Next alanını, silmek istediğimiz vagonun Next kısmına eşitliyor ve BellekBosalt methoduna silmek istediğimiz vagonu yolluyoruz. Artık vagonumuz aramızdan ayrıldı :)

Ekle methodu

void Ekle(int sayi, int nereye, bool sol)
{
	ptrType temp;
	int sonuc;
	Bul(sayi,&temp,&sonuc);
	if(nereye==-1)
	{
		BellekAl(&temp);
		temp->Next=Head;
		temp->Data=sayi;
		Head=temp;
	}
	else
	{
		Bul(nereye,&temp,&sonuc);
		if(sol)
		{
			ptrType soldaki=Head;
			while(soldaki!=NULL)
				if(soldaki->Next==temp)
					break;
				else
					soldaki=soldaki->Next;
			ptrType yeni;
			BellekAl(&yeni);
			yeni->Data=sayi;
			yeni->Next=temp;
			soldaki->Next=yeni;
		}
		else
		{
			if(temp->Next==NULL) //En sağdaki demektir
			{
				ptrType yeni;
				BellekAl(&yeni);
				yeni->Data=sayi;
				yeni->Next=NULL;
				temp->Next=yeni;
			}
			else
			{
				ptrType yeni;
				BellekAl(&yeni);
				yeni->Data = sayi;
				yeni->Next=temp->Next;
				temp->Next=yeni;
			}
		}
	}
}

Eminim bu methodu gören herkesin yüzünde bir ekşime olmuştur. Sınava Kemal arkadaşımla son gece hazırlanırken bizde bu methodu yazana kadar çok mutluyduk :) Gel gelelim diğer methodlardan sonra Ekleme methodu bariz bir farkla zorluğunu ortaya koyuyor. Aslında bunun bir nedenide bizim en kötüyü düşünerek tüm kombinasyonları fonksiyonalite haline getirmemiz oldu. Sınavda çıkan soruda sadece başa ekleme işleminin yapılması istenileceğini bilseydik, en başa, en sona, aradan bir sayının sağına ya da soluna gibi komplex işlemleri gerçekleştirecek bir method yazmak için uğraşmazdık :) Tabi sınav için hazırlanan arkadaşlara sesleniyorum ki kolaya kaçmayın :) Vaktinizi alsada problem çözme yetiniz oldukça artacaktır.

Tüm methodları anlatması kolaydı ama bu methodu anlatması cidden benim içinde zor :)
Ekle methodumuz parametre olarak eklenecek sayıyı, eğer araya ekleneceksede o sayıyı ve ekleneceği yönü bildireceğimiz bir değişken alıyor.
Başa eklemek için nereye -1 olmalı, araya ekleneceksede sola eklemek için son parametre true, sağ içinse false olmalı.

Methodumuz öncelikle araya eklenme durumu için nereye değişkeniyle bize gelen sayıyı buluyor. Hemen ardından en başa eklenmesi durumunda -1 yollayacağımız nereye değişkeninin durumunu kontrol ediyoruz ve en kolay ekleme işlemini gerçekleştiriyoruz. Bunun için eklenecek sayıyı BellekAl methodu ile öncelikle memory de bir yer sahibi yapıyor ve eklediğimiz vagonun Next alanını şu anki Head'i göstecek şekilde yapıyoruz. Hemen ardından içeriğini girip artık ilk vagonu gösteren Head pointerının göstereceği yeri en başa eklediğimiz vagon olarak değiştiriyoruz.

Araya eklenme durumunda ise else bloğu devreye giriyor. Sola eklenme için tipkı silme de olduğu gibi ekleyeceğimiz yerde bir solda kalan vagonu bulmamız gerekiyor. Çünkü bu vagonun Next kısmı artık ekleyeceğimiz vagonu göstermeli. Bulma işlemini gerçekleştirip, bulduğumuz vagonun Next alanını ekleyeceğimiz vagonu gösterecek şekilde ayarlıyor ve eklediğimiz vagonunda Next alanını nereye parametresinden gelen vagon olarak gösteriyoruz.

Sağa ekleme durumunda ise bu koşulun else bloğu devreye girecektir. Fakat burda da kontrol etmemiz gereken bir durum var! Eklemeye çalıştığımız vagon için yolladığımız nereye bilgisinin gösterdiği vagon ya enson vagonumuz ise ? Bu durumda yanına eklenecek olan vagonumuzun Next değeri son vagon olduğu için artık Next değil, ekleyeceğimiz vagon olmalı ve ekleyeceğimiz vagonda son vagon olacağı için Next alanı NULL olmalıdır.

Eğer son vagon değilse ki en kolay ekleme işlemini gerçekleştiriyor ve ekleyeceğimiz vagonun Next alanını, nereye bilgisinden gelen vagonun Next alanına eşitliyoruz.

Artık Ekle methodumuzda son derece tüm ihtimallere cevap verebilecek oldukça da karmaşık bir halde karşımızda :)

Main methodu

int main()
{
	int sonuc;
	ptrType temp;
	Bul(1,&temp,&sonuc);
	Baslat();

	Ekle(3,-1,false);
	Ekle(5,-1,false);
	Ekle(7,-1,false);
	Ekle(9,-1,false);
	Ekle(20,7,true);
	Ekle(30,5,false);

	Listele();
	system("PAUSE");
}

Main methodumuzda ise yukarıdaki gibi çeşitli Ekleme işlemlerini yapıp en sonda Listele methodunu çağırıyorum ve tüm araya ekleme işlemleri dahil tüm methodlarımız hatasız çalışıyor. Tüm bu uzun makale ve öğrendiğimiz harika bir yapının ardından sorunsuz çalışan uygulamamız umuyorum ki az önce yüzümüzü buruşturan tüm zorlukları birer mutluluğa çevirmiştir.

İlk defa bu yapıyı kullananlar için bol bol örnek yapmasını önerip, konu üzerinde fazlasıyla emeği geçen Sayın Dr.Habil Kalkan'a ve Ali Güneş'e teşekkür eder, herkese bir sonraki makalemde görüşmek üzere esenlikler dilerim.
H.Burak TUNGUT

c-c++ ile ilgileniyorum ve bu konuda yeniyim makalenizi gördüm .Çoğu karışık ama struct konusunda kafam karıştı mesela typedef Yapi* ptrType; ptrType Head; demişsiniz burda Yapi* değişken türü ptrType ise değişken adı olmuyor mu?? eğer ptrType değişken adı oluyorsa buna nasıl Head atıyabiliyoruz .. ptrType Head; den benim anladığım şey ptrType--->değişken türü Head--->ise değişken adı oluyor kafam çok karıştı yardımlarınızı bekliyorum başlangıcı anlamalıyım ki sonunu okuduğumda kafamda soru işaretleri kalmasın....
Çok yararlı bir makale, aynı zaman da ülkemizde ki çoğu üniversitede anlatılanlardan kat ve kat daha iyi.
Yorum Bırak

Facebook
Son Yorumlar