Veri Yapılarına Dair #3

Herkese merhaba Veri Yapılarına Dair #3 yazısında çift yönlü baÄŸlı liste ve dairesel listeler hakkında bilgi vermeyi düşünüyorum. Veri Yapılarına Dair #3 yazısıyla baÄŸlı listeler konusunu bitirip yeni konumuz olan kuyruk veri yapısına geçmiÅŸ bulunuyoruz. Herkese iyi okumalar dilerim….

Çift-Yönlü BaÄŸlı Liste (Doubly Linked List)

Çift bağlı listede düğümler arası bağlantı hem ileri hem de geriye doğru olacak şekilde yapılır.

Çift bağlı listede araya ekleme ve aradan silme işlemleri tek bağlı listeye göre daha kolaydır. Tek bağlı listeden ayıran farkı hem önceki işaretçisi hem de sonraki işaretçisi vardır.

Çift bağlı listeler sayesinde liste üzerinde ileri ve geri gitmek mümkündür.

Eleman Ekleme

Eleman ekleme işlemlerini yapmak için ilk olarak liste tanımlıyoruz. önceki ve sonraki düğüm adreslerini tamamladıktan sonra yeni düğüm için bellekten yer ayırıyoruz. aşağıdaki kodları temel mantığı anlatmak amacıyla koydum. void ekle kısmı ile listemize yeni eleman ekleme işlemini yapıyoruz.

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

typedef struct list {
    int sayi;
    struct list *onceki;
    struct list *sonraki;
} liste;

liste *ilk = NULL, *yeni = NULL, *son = NULL;
void ekle(int veri) {
    yeni = (liste *) malloc(sizeof (liste));
    yeni->sayi = veri;
    yeni->sonraki = NULL;

    if (ilk == NULL) {
        ilk = yeni;
        son = ilk;
        ilk->onceki = NULL;
    } else {
        son ->sonraki = yeni;
        yeni->onceki = son;
        son = son->sonraki;
        }
    }
}

Eleman Silme

Yine aynı şekilde önceki düğüm ve sonraki düğümü oluşturuyoruz. NODE ile yeni düğüm için bellekten yer ayırıyoruz. NULL boş demek yani orada düğüm yok.

Yeni düğüme veri kaydediliyor. node->x=x;

Bir önceki düğümün sonraki düğüm adresine silinen düğümden sonraki düğümün adresi kaydedilir.

tmp=node->previous; tmp->next=node->next;

#include <stdio.h>
#include <stdlib.h>
typedef struct NODE{
	int x;
	struct NODE * next;
	struct NODE * previous;
}NODE;


NODE * CreateNode(NODE * previous,int x){
	NODE * node;
	node=(NODE *)malloc(sizeof(NODE));
	if(node){
		node->x=x;
		node->next=NULL;
		if(previous){
			node->previous=previous;
			previous->next=node;
		}else{
			node->previous=NULL;
		}
	}
	return node;
}
void RemoveNode(NODE *node){
	NODE *tmp;
	if(node->previous){
		tmp=node->previous;
		tmp->next=node->next;
	}
	if(node->next){
		tmp=node->next;
		tmp->previous=node->previous;
	}

	free(node);
	return;
}
void PrintListLeft(NODE * last){
	NODE * tmp=last;
	while(tmp){
		printf("%d,",tmp->x);

		tmp=tmp->previous;
	}
	return;
}
void PrintListRight(NODE * root){
	NODE * tmp=root;
	while(tmp){
		printf("%d,",tmp->x);
		tmp=tmp->next;
	}
	return;
}
int main(void){
	NODE * tmp=NULL;
	NODE * node=NULL;
	NODE * root=NULL;
	int x=0;
	int i=0;
	root=CreateNode(NULL,0);
	node=root;
	for(i=0;i<20;i++){
		tmp=CreateNode(node,i+1);
		node->next=tmp;
		node=tmp;
	}
	PrintListLeft(tmp);
	do{
		printf("\nSilinecek dugum:");
		scanf("%d",&x);
		node=root;
		tmp=NULL;
		while(node){
			if(node->x==x){
				if(tmp==NULL){
					root=node->next;
				}
				RemoveNode(node);
				break;
			}
			tmp=node;
			node=node->next;
		}
		PrintListRight(root);
	}while(root);

	return 0;
}

Dairesel Listeler

Dairesel listeler tek yönlü ve çift yönlü bağlı listelerde en sondaki düğüm ile en baştaki düğüm arasında bir bağlantı sağlar. Listenin başı ile listenin sonu bağlanmış olur.

İki bağlı dairesel listelerde listenin birinci düğümünün prev değeri sonuncu
düğümü, sonuncu düğümünün next değeri de listenin başını göstermektedir.

#include <stdio.h>
#include <stdlib.h>
typedef struct NODE{
	int x;
	struct NODE * next;
	struct NODE * previous;
}NODE;

NODE * CreateNode(NODE * previous,int x){
	NODE * node;
	NODE * tmp;
	node=(NODE *)malloc(sizeof(NODE));
	if(node){
		node->x=x;

		if(previous){
			node->previous=previous;
			node->next=previous->next;
			previous->next=node;
			tmp=node->next;
			if(tmp->previous){
				tmp->previous=node;
			}
		}else{
			node->next=node;
			node->previous=node;
		}
	}
	return node;
}
void PrintListLeft(NODE * last){
	NODE * tmp=last;
	if(!tmp){
		return;
	}

	do{
		printf("%d,",tmp->x);
		tmp=tmp->previous;
	}while(tmp!=last && tmp);

	return;
}
void PrintListRight(NODE * root){
	NODE * tmp=root;
	if(!tmp){
		return;
	}
	do{
		printf("%d,",tmp->x);
		tmp=tmp->next;
	}while(tmp!=root && tmp);

	return;
}
int main(void){
	NODE * tmp=NULL;
	NODE * last=NULL;
	NODE * root=NULL;
	int x=0;

	do{
		printf("\nx:");
		scanf("%d",&x);
		tmp=CreateNode(last,x);
		last=tmp;
		PrintListLeft(last);
	}while(x!=0);
	return 0;
}

Genel olarak bağlı listeler bellek alanlarının birbirine tutuşturulmasıyla oluşur. Her elemanın başka elemanla bağlantısı vardır. Dizilerden farkı elemanlarının dizilerde olduğu gibi bellekte sıralı olma zorunluluğu olmamasıdır. Dizilerde her eleman bellekte art arda gelen adreslerde tutulur. Bu haftalık yazımızın sonuna gelmiş bulunuyoruz.

Veri Yapılarına Dair#2 yazımızı okuyarak genel bilgiye sahip olabilirsiniz.

Yazılarımı okumak isterseniz buraya tıklayınız.