Bağlantılı Listeler (Linked Lists)
01 Ocak 2009 – 22:46
Bağlantılı listeler aynı türden verileri birbirine bağlamamıza yarayan bir veri yapısı türüdür. Veriler sanal olarak birbirine bir sırayla bağlanır. Ancak bu veriler bellekte art arda dizilmezler, belleğin değişik yerlerindedirler. Bu nedenle bağlantılı liste yapısı veri kısmı ve bağlantı kısmı olarak iki farklı kısımdan oluşur. Listedeki veriler bu bağlantı kısmı sayesinde birbirine bağlanırlar. Bağlantılı listelerde araya veri ekleme, çıkarma gibi temel işlemler kolayca yapılır bu yüzden çok kullanılan bir veri yapısı türüdür. Bağlantılı listelerde bir veriyi aramak için, listedeki tüm elemanlara bakılması gerekir. Bu nedenle bağlantılı listelerde arama yapmanın karmaşıklığı n elemanlı bir listede O(n)dir.
Bağlantılı listeler iki farklı şekilde oluşturulabilir. Pointerlar (göstericiler) veya dizilerle. Göstericilerle liste oluşturmak daha çok kullanılan bir yöntemdir. Göstericilerle oluşturulan bir listede; ilk düğüm bir göstericiyle işaretlenir ve o gösterici ne işlem yapılırsa yapılsın hep listenin başını gösterir. Çünkü bir işlem yapılacagında işlem listenin başından başlar, bu yüzden bellekte listeyi bulabilmek için başını tutan bir göstericiye mutlaka gerek vardır. Bir de listenin sonunu gösteren bi gösterici tanımlanır. Yani listenin başı ve sonunu hiçbir zaman kaybetmemek gerekir. Eğer kaybedilirse listede ekleme veya arama gibi bir işlem yaparken listenin başını bulamazsak veya sonunu kayberdersek bu başımıza büyük sorunlar açabilir. Bağlantılı liste eğer göstericilerle oluşturulacaksa, o düğüm için veri kısmı ve gösterici türünde bağlantı kısmı olan bir struct tanımlanır.
typedef struct baglantiliListe
{
int veri;
struct baglantiliListe *sonraki;
}dugum;
dugum *ilk=NULL, *son=NULL;
Dizilerle oluşturulacaksa;
typedef struct baglantiliListe
{
int veri;
struct baglantiliListe sonraki;
}dugum;
dugum veriler[30];
int ilk=-1, son=-1;
diye listenin başı ve sonu ilk(head) ve son(tail) adında iki sanal göstericiyle tutulur.
Göstericilerle oluşturulmuş bir bağlantılı listede eleman ekleme ve silme işlemlerini algoritmik olarak nasıl yapacağımıza bakalım. Diyelim ki listemizin herhangi bi bölümü asagıdaki gibi olsun. İki elemanı p ve q göstericileriyle tutalım.
Bu durumda araya veri eklerken şöyle bir yol izlenir:
q.sonraki=p.sonraki;
p.sonraki=q;
Dikkat edilirse eklenecek elmanı önce sonrakine bağlayıp sonra öncekine bağlıyoruz veri kaybını önlemek için.
Aradan eleman silmek istediğimizdeyse,
p.sonraki=q.sonraki;
dispose q;
işlemi uygulanır.
Bağlantılı liste çevrimsel yapıda da olabilir. Yani listenin sonundaki elemanın gösterici kısmı en baştaki elemanı gösterir. Bu durumda son isminde bir gösterici tanımlamaya gerek kalmaz. Ekleme ve silme işlemlerinde bir farklılık yoktur.
Şimdi bağlantılı liste veri yapısını kullanarak bir liste üzerindeki elemanları ekleme, silme ve listeleme işlemlerini yapan bir program yazalım. Bu kodda head ve tail adında listenin başını ve sonunu gösteren iki gösterici tanımlayacağız.
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
struct liste{
int data;
struct liste *next;
};
struct liste *head=NULL,*tail=NULL;
int i;
int main()
{
struct liste *yeni;
struct liste *p;
int secenek;
for (i=0;secenek!=3;i++)
{
printf(”Hangi islemi yapmak istiyorsunuz?\n\n”);
printf(”1- Ekleme\n”);
printf(”2- Listeleme\n”);
printf(”3- Cikis\n”);
scanf(”%d”,&secenek);
switch(secenek)
{
case 1:
printf(”Veri ekleme moduna geldiniz…\n”);
yeni=(struct liste *)malloc(sizeof(struct liste));
if(yeni==NULL)
return 0;
else
{
printf(”Veriyi giriniz:”);
scanf(”%d”,&(yeni->data));
if(yeni!=NULL)
{
if(head!=NULL)
{
tail->next=yeni;
tail=yeni;
tail->next=NULL;
}
else
{
head=yeni;
tail=head;
head->next=NULL;
}
}
else
{
printf(”Hafızada yer yok…\n”);
}
}
break;
case 2:
p=head;
if(p==NULL)
printf(”Liste bos…\n”);
else
{
while(p)
{
printf(”%d\n”,p->data);
p=p->next;
}
}
break;
case 3:
printf(”Tesekkurler”);
break;
default:
printf(”Yanlis tusa bastiniz.Programi tekrar calistiriniz”);
return 0;
}
}
return 0;
}
BAŞAK KOLDAŞ
