Bağlı Listeler

  • 13-06-2020 06:34
  • 13457

Bağlı listeler (linked list) bilgisayar programlarında kullanılan bir tür veri yapısıdır. Bağlı listeler bir zincirin halkaları gibi birbirine bağlı düğümlerden oluşur. Her düğüm iki kısımdan oluşur ilk kısım istenilen verinin kaydedileceği değişkenlerdir ikinci kısım ise bir sonraki ve tipine bağlı olarak bir önceki düğümün adresini içeren işaretçidir (pointer). Bağlı listedeki verilere sıra ile erişilebilir, ilk düğümden başlanarak önce veri okunur sonra işaretçinin gösterdiği adresteki bir sonraki düğüme geçilir, veri okunur ve sonraki düğüme geçlir bu işlem bütün düğümler tamamlana kadar devam eder.

Bağlı listelerin kullanım amacı sıralı verilerilerin bellekte erişilebilir bir düzende tutulmasıdır. Dizilerden (array) farklı olarak verilere erişim sıralıdır. Dizilerde iki elaman arasına bir başka eleman eklemek için dizinin yeniden düzenlenmesi gerekir bu işlem dizideki veri miktarına bağlı olarak belirli bir zaman alır, büyük dizilerde bu işlemi yapmak programın performansını önemli ölçüde düşürür. Bu gibi durumlarda bağlı listeler kullanılabilir. Sık güncellenen sıralı verilerin kullanıldığı her yerde bağlı listeler kullanılabilir. Dezavantajı ise verilere sıralı erişildiği için belirli bir veriye erişimin dizilerden daha çok zaman almasıdır. Liste uzunluğu arttıkça bu zaman da artar. Ama genelde kullanımı özel bir veriye erişim değil, listedeki tüm verilere sıralı erişim şeklindedir. Örneğin sabit diskte veriler sektör adı verilen bloklar halinde saklanır. Dosyalara ait veriler bağlı liste olarak saklanabilir. Bir dosyaya erişildiği zaman bağlı listedeki tüm verilere sırası ile erişilir ve dosya diskten okunmuş olur. Bu şekilde dosyanın ortasında bir değişiklik yapıldığında yalnızca değişiklik yapılan kısım güncellenir, veri eklenmişse bağlı listeyi yeni bir sektörü geösteren yeni bir düğüm eklenir, veri silinmişse o sektöre ait düğüm silinir.
Bağlı listelerin tek yönlü, çift yönlü ve dairesel olarak 3 türü vardır.

Tek Yönlü Bağlı Listeler

Her düğüm yalnızca bir sonraki düğümün adresi barındırır bunun sonucu olarak tek yönde okuma yapılabilir, bir düğümden önceki düğüme erişilemez. Düğüm yapısı C programlama dilinde struct kullanılarak yapılır.

C'de tek yönlü bağlı liste örneği. Bu kod derlendiğinde oluşan program klavyeden girilen tam sayı değerleri düğüme veri olarak kaydeder ve bu veri ile yeni bir düğüm oluşturur, oluşan yeni düğümü bağlı listeye ekler. Her eklemeden sonra tüm bağlı liste elemanları ekrana yazdırılır.

	
/*
Tek yönlü bağlı liste örneği.
Program klavyeden girilen tam sayı değerleri bağlı liste olarak kaydeder.
Her sayısal değerden sonra bağlı liste ekrana yazdırılır. Kalvyeden 0 değeri girildiğinde program sonlanır. https://notpast.com */ #include <stdio.h> #include <stdlib.h> //Tek yönlü bağlı liste düğümü. typedef struct NODE{ //Düğüme ait veri. //Farklı tipte değişkenler burada tanımlanabilir. int x; //Bir sonraki düğümün adresi. struct NODE * next; }NODE; //Tek yönlü bağlı listede yeni bir düğüm oluşuturan fonksiyon. NODE * CreateNode(int x){ NODE * node; //Yeni düğüm için bellekten yer ayrılıyor. node=(NODE *)malloc(sizeof(NODE)); if(node){ //Yeni düğüme veri kaydediliyor. node->x=x; //NULL anlamı sonrasında düğüm olmadığıdır. node->next=NULL; } return node; } //Tek yönlü bağlı listede düğüm silme fonksiyonu. //ilk düğümü silmek için fonkiyon RemoveNode(NULL,ilk_düğüm); şeklinde çağrılmalı. void RemoveNode(NODE *previous,NODE *node){ //Düğümün adresinin geçerli bir adres olduğu kontrol ediliyor. if(!node){ return; } //Bir önceki düğümün varlığı kontrol ediliyor. if(previous){ //Bir önceki düğümün sonraki düğüm adresine //silinecek düğümden sonraki düğümün adresi kaydediliyor. previous->next=node->next; } //Düğüm siliniyor. free(node); return; } //Bağlı listyi ekrana yazdıran fonksiyon. void PrintList(NODE * root){ NODE * tmp=root; while(tmp){ printf("%d,",tmp->x); //Bir sonraki düğüm tmp değişkenine aktarılıyor. tmp=tmp->next; } return; } //Ana fonksiyon. int main(void){ NODE * tmp=NULL; NODE * node=NULL; NODE * root=NULL; int x=0; //İlk düğüm oluşturuluyor. root=CreateNode(0); node=root; do{ printf("\nx:"); //Klavyeden yeni düğüm için tam sayı bir değer okunuyor. scanf("%d",&x); //Okunan değerle yenir düğüm oluşturuluyor. tmp=CreateNode(x); if(tmp){ //Oluşturulan düğümün adresi bir önceki düğüme kaydediliyor. node->next=tmp; node=node->next; } //Bağlı liste ekrana yazdırılıyor. PrintList(root); }while(x!=0); return 0; }

 

Tek yönlü bağlı listeden eleman silen örnek program. Programda önce bir dögü ile bağlı liste oluşturuluyor ve ekrana yazdırılıyor. Sonraki döngüde ise klavyeden silinmek istenen düğümün numarası yazılıyor ve o numarılı düğüm siliniyor bu şekilde döngü tüm düğümler silinene kadar devam ediyor.

/*
	Tek yönü bağlı listeden düğüm silen program.
Program bir döngü ile oluşturumuş 10 düğümlü tek yönlü bağlı liste içinden
istenilen düğümü siler. Program döngüsü bütün düğümler silinene kadar devam eder. https://notpast.com */ #include <stdio.h> #include <stdlib.h> //Tek yönlü bağlı liste düğümü. typedef struct NODE{ //Düğüme ait veri. //Farklı tipte değişkenler burada tanımlanabilir. int x; //Bir sonraki düğümün adresi. struct NODE * next; }NODE; //Tek yönlü bağlı listede yeni bir düğüm oluşuturan fonksiyon. NODE * CreateNode(int x){ NODE * node; //Yeni düğüm için bellekten yer ayrılıyor. node=(NODE *)malloc(sizeof(NODE)); if(node){ //Yeni düğüme veri kaydediliyor. node->x=x; //NULL anlamı sonrasında düğüm olmadığıdır. node->next=NULL; } return node; } //Tek yönlü bağlı listede düğüm silme fonksiyonu. //ilk düğümü silmek için fonkiyon RemoveNode(NULL,ilk_düğüm); şeklinde çağrılmalı. void RemoveNode(NODE *previous,NODE *node){ //Düğümün adresinin geçerli bir adres olduğu kontrol ediliyor. if(!node){ return; } //Bir önceki düğümün varlığı kontrol ediliyor. if(previous){ //Bir önceki düğümün sonraki düğüm adresine //silinecek düğümden sonraki düğümün adresi kaydediliyor. previous->next=node->next; } //Düğüm siliniyor. free(node); return; } //Bağlı listyi ekrana yazdıran fonksiyon. void PrintList(NODE * root){ NODE * tmp=root; while(tmp){ printf("%d,",tmp->x); //Bir sonraki düğüm tmp değişkenine aktarılıyor. tmp=tmp->next; } return; } //Ana fonksiyon. int main(void){ NODE * tmp=NULL; NODE * node=NULL; NODE * root=NULL; int x=0; int i=0; //İlk düğüm oluşturuluyor. root=CreateNode(0); node=root; //Bağlı listeye 10 düğüm ekleniyor. for(i=0;i<10;i++){ tmp=CreateNode(i+1); if(tmp){ //Oluşturulan düğümün adresi bir önceki düğüme kaydediliyor. node->next=tmp; node=node->next; } } //Bağlı liste yazdırılıyor. PrintList(root); //Bütün düğümler silinene kadar döngü devam eder. do{ printf("\nSilinecek dugumun numsrasi:"); //Klavyeden silinecek düğüm değeri okunuyor. scanf("%d",&x); node=root; tmp=NULL; //Klavyeden okunan değer bağlı listede aranıyor. while(node){ if(node->x==x){ if(tmp==NULL){ //Silinen düğüm ilk düğümse sonraki düğüm //ilk düğüme kaydediliyor. root=node->next; } //Düğüm siliniyor. RemoveNode(tmp,node); break; } tmp=node; //Bir sonraki düğüme geçiliyor. node=node->next; } //Bağlı liste yazdırılıyor. PrintList(root); }while(root); return 0; }

 

 


Çift Yönlü Bağlı Listeler

Çift yönlü bağlı listelerde her düğümde hem bir sonraki hem de bir önceki düğümün adresi tutulur. Bu sayede iki yöndeki düğümlere de erişilebilir.
C'de çift yönlü bağlı liste örneği. Programa yeni düğüm kaydı için bir numara girip enter tuşuna basın.

/*
	Çift yönlü bağlı liste örnek programı.
	Program klavyeden girilen tam sayı değerleri bağlı liste olarak kaydeder.
	Her sayısal değerden sonra bağlı liste ekrana yazdırılır. Kalvyeden
	0 değeri girildiğinde program sonlanır. https://notpast.com
*/

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

//Çift yönlü bağlı liste düğümü.
typedef struct NODE{
	//Düğüme ait veri.
	//Farklı tipte değişkenler burada tanımlanabilir.	
	int x;
	//Bir sonraki düğümün adresi.
	struct NODE * next;
	//Bir önceki düğümün adresi.
	struct NODE * previous;
}NODE;


NODE * CreateNode(NODE * previous,int x){
	NODE * node;
	//Yeni düğüm için bellekten yer ayrılıyor.
	node=(NODE *)malloc(sizeof(NODE));
	if(node){
		//Yeni düğüme veri kaydediliyor.
		node->x=x; 
		//NULL anlamı sonrasında düğüm olmadığıdır.
		node->next=NULL;
		//Bir önceki düğümün adresi yeni oluşturulan 
		//düğümün bir önceki düğüm adresine kaydediliyor.
		if(previous){
			node->previous=previous;
			previous->next=node;
		}else{
			//root ise önceki düğümü yok.
			node->previous=NULL;
		}
	}
	return node;
}


//Çift yönlü bağlı listede düğüm silme fonksiyonu.
void RemoveNode(NODE *node){
	NODE *tmp;
	if(!node->previous){
		return;
	}

	//Bir önceki düğümün sonraki düğüm adresine 
	//silinecek düğümden sonraki düğümün adresi kaydediliyor.
	tmp=node->previous;
	tmp->next=node->next;

	//Düğüm siliniyor.
	free(node);
	return;
}

//Bağlı listyi sondan başlayarak ekrana yazdıran fonksiyon.
//last parametresi bağlı listenin son düğümü.
void PrintListLeft(NODE * last){
	NODE * tmp=last;
	while(tmp){
		printf("%d,",tmp->x);
		//Bir önceki düğüm tmp değişkenine aktarılıyor.
		tmp=tmp->previous;
	}
	return;
}


//Bağlı listyi baştan başlayarak ekrana yazdıran fonksiyon.
//root parametresi bağlı listenin ilk düğümğü.
void PrintListRight(NODE * root){
	NODE * tmp=root;
	while(tmp){
		printf("%d,",tmp->x);
		//Bir sonraki düğüm tmp değişkenine aktarılıyor.
		tmp=tmp->next;
	}
	return;
}



//Ana fonksiyon.
int main(void){
	NODE * tmp=NULL;
	NODE * last=NULL;
	NODE * root=NULL;
	int x=0;

	//İlk düğüm oluşturuluyor.
	root=CreateNode(NULL,0);
	last=root;

	do{
		printf("\nx:");
		//Klavyeden yeni düğüm için tam sayı bir değer okunuyor.
		scanf("%d",&x);
		//Okunan değerle yenir düğüm oluşturuluyor.
		tmp=CreateNode(last,x);
		if(tmp){
			//Oluşturulan düğümün adresi bir önceki düğüme kaydediliyor.
			last->next=tmp;
			last=last->next;
		}
		//Bağlı listeyi sondan başlayarak ekrana yazdırılıyor.
		PrintListLeft(last);
	}while(x!=0);

	return 0;
}

 

Çift yönlü bağlı listeden elaman silme. Bağlı listeden aradan bir düğüm silindiğinde, bir önceki düğümün sonraki adresi, silinen düğümden sonraki düğümün adresi olur. Bir sonraki düğümün bir önceki adresi, silinen düğümden önceki düğümün adresi olur.

C programlama dilinde çift yönlü bağlı listeden eleman silen program örneği. Kodlar derlendiğinde çalışan bir program oluşturur.

Program çalıştığında ekranda gördüğünüz bağlı liste düğümlerinde silmek istediğiniz düğümün numarasını yazıp enter tuşuna basın. Tüm düğümler silinene kadar program devam eder.

/*
	Çift yönlü bağlı listeden eleman silen program.
	Program bir döngü ile oluşturumuş 10 düğümlü çift yönlü bağlı liste içinden 
	istenilen düğümü siler. Program döngüsü bütün düğümler silinene kadar
	devam eder. https://notpast.com
*/

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

//Çift yönlü bağlı liste düğümü.
typedef struct NODE{
	//Düğüme ait veri.
	//Farklı tipte değişkenler burada tanımlanabilir.	
	int x;
	//Bir sonraki düğümün adresi.
	struct NODE * next;
	//Bir önceki düğümün adresi.
	struct NODE * previous;
}NODE;


NODE * CreateNode(NODE * previous,int x){
	NODE * node;
	//Yeni düğüm için bellekten yer ayrılıyor.
	node=(NODE *)malloc(sizeof(NODE));
	if(node){
		//Yeni düğüme veri kaydediliyor.
		node->x=x; 
		//NULL anlamı sonrasında düğüm olmadığıdır.
		node->next=NULL;
		//Bir önceki düğümün adresi yeni oluşturulan 
		//düğümün bir önceki düğüm adresine kaydediliyor.
		if(previous){
			node->previous=previous;
			previous->next=node;
		}else{
			//root ise önceki düğümü yok.
			node->previous=NULL;
		}
	}
	return node;
}


//Tek yönlü bağlı listede düğüm silme fonksiyonu.
void RemoveNode(NODE *node){
	NODE *tmp;
	if(node->previous){
		//Bir önceki düğümün sonraki düğüm adresine 
		//silinecek düğümden sonraki düğümün adresi kaydediliyor.
		tmp=node->previous;
		tmp->next=node->next;
	}
	if(node->next){
		tmp=node->next;
		tmp->previous=node->previous;		
	}
	//Düğüm siliniyor.
	free(node);
	return;
}

//Bağlı listyi sondan başlayarak ekrana yazdıran fonksiyon.
void PrintListLeft(NODE * last){
	NODE * tmp=last;
	while(tmp){
		printf("%d,",tmp->x);
		//Bir önceki düğüm tmp değişkenine aktarılıyor.
		tmp=tmp->previous;
	}
	return;
}


//Bağlı listyi baştan başlayarak ekrana yazdıran fonksiyon.
void PrintListRight(NODE * root){
	NODE * tmp=root;
	while(tmp){
		printf("%d,",tmp->x);
		//Bir sonraki düğüm tmp değişkenine aktarılıyor.
		tmp=tmp->next;
	}
	return;
}



//Ana fonksiyon.
int main(void){
	NODE * tmp=NULL;
	NODE * node=NULL;
	NODE * root=NULL;
	int x=0;
	int i=0;

	//İlk düğüm oluşturuluyor.
	root=CreateNode(NULL,0);
	node=root;

	//Bağlı listeye 10 düğüm ekleniyor.
	for(i=0;i<10;i++){
		tmp=CreateNode(node,i+1);
		node->next=tmp;	
		node=tmp;	
	}	

	//Bağlı liste yazdırılıyor.
	PrintListLeft(tmp);

	//Bütün düğümler silinene kadar döngü devam eder.
	do{
		printf("\nSilinecek dugum:");
		//Klavyeden silinecek düğüm değeri okunuyor.
		scanf("%d",&x);
		node=root;
		tmp=NULL;
		//Klavyeden okunan değer bağlı listede aranıyor.
		while(node){
			if(node->x==x){
				if(tmp==NULL){
					//Silinen düğüm ilk düğümse sonraki düğüm 
					//ilk düğüme kaydediliyor.					
					root=node->next;
				}
				//Düğüm siliniyor.				
				RemoveNode(node);
				break;
			}

			tmp=node;
			//Bir sonraki düğüme geçiliyor.
			node=node->next;
		}
		//Bağlı liste yazdırılıyor.
		PrintListRight(root);	
	}while(root);

	return 0;
}

 

Dairesel Bağlı Listeler

Dairesel bağlı listelerde son düğümün adresi ilk düğümün önceki düğüm adresine, son düğümün soraki adresine ise ilk düğümün adresi kaydedilir. Böylece listenin başı ile listenin sonu bağlanmış olur.

Dairesel çift yönlü bağlı liste örnek C  kodu. Kodlar derlendiğinde çalışabilir bir program oluşur.

/*
	Dairesel çift yönlü bağlı liste.
	Program klavyeden girilen tam sayı değerleri bağlı liste olarak kaydeder.
	Her sayısal değerden sonra bağlı liste ekrana yazdırılır. Kalvyeden
	0 değeri girildiğinde program sonlanır. https://notpast.com
*/

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

//Çift yönlü bağlı liste düğümü.
typedef struct NODE{
	//Düğüme ait veri.
	//Farklı tipte değişkenler burada tanımlanabilir.	
	int x;
	//Bir sonraki düğümün adresi.
	struct NODE * next;
	//Bir önceki düğümün adresi.
	struct NODE * previous;
}NODE;


NODE * CreateNode(NODE * previous,int x){
	NODE * node;
	NODE * tmp;
	//Yeni düğüm için bellekten yer ayrılıyor.
	node=(NODE *)malloc(sizeof(NODE));
	if(node){
		//Yeni düğüme veri kaydediliyor.
		node->x=x; 

		if(previous){
			//Bir önceki düğümün adresi yeni düğümün bir önceki adresine kaydediliyor.
			node->previous=previous;

			//Bir sonraki düğümün adresi yeni düğüme kaydediliyor.						
			node->next=previous->next;	

			//Bir önceki düğümün bir sonraki adresine yeni düğüm kaydediliyor.		
			previous->next=node;

			//Bir sonraki düğümün bir önceki adresine yeni düğüm kaydediliyor;
			tmp=node->next;
			if(tmp->previous){
				tmp->previous=node;
			}

		}else{
			//Düğüm ilk düğüm ise sonraki ve önceki düğüm adresine 
			//düğümün adresi kaydediliyor.
			node->next=node;
			node->previous=node;
		}

	}
	return node;
}


//Bağlı listyi sondan başlayarak ekrana yazdıran fonksiyon.
void PrintListLeft(NODE * last){
	NODE * tmp=last;
	if(!tmp){
		return;
	}

	do{
		printf("%d,",tmp->x);
		//Bir önceki düğüm tmp değişkenine aktarılıyor.
		tmp=tmp->previous;
	}while(tmp!=last && tmp);

	return;
}


//Bağlı listyi baştan başlayarak ekrana yazdıran fonksiyon.
void PrintListRight(NODE * root){
	NODE * tmp=root;
	if(!tmp){
		return;
	}
	do{
		printf("%d,",tmp->x);
		//Bir sonraki düğüm tmp değişkenine aktarılıyor.
		tmp=tmp->next;
	}while(tmp!=root && tmp);
	
	return;
}

//Ana fonksiyon.
int main(void){
	NODE * tmp=NULL;
	NODE * last=NULL;
	NODE * root=NULL;
	int x=0;

	do{
		printf("\nx:");
		//Klavyeden yeni düğüm için tam sayı bir değer okunuyor.
		scanf("%d",&x);
		//Okunan değerle yen bir düğüm oluşturuluyor.
		tmp=CreateNode(last,x);
		last=tmp;
		//Bağlı liste sondan başlayarak ekrana yazdırılıyor.
		PrintListLeft(last);
	}while(x!=0);

	return 0;
}