Veri Yapıları Tek Yönlü Bağlı Liste (Linked List)
Bağlı listeler aynı türden verileri tutmaya yarar işlev olarak dizilere benzeler ancak çalışma prensipleri biraz farklıdır. Bağlı listeler düğüm(node) lardan oluşur ve bir sonraki düğüm’ü göstermek amacıyla işaretci barındırır. oluşturulan her düğüm birbirinin kopyasıdır ve birbirlerini işaret ederek ilerlerler.
Dizilere göre avantajları :
1-Dizilerin boyutları tanımlanırken belirlenmelidir, belirlendiklerinde direk ramden yer ayrılır ve boyutları sabittir. Bağlı listelerde boyut sınırı yoktur sistem nekadar veriye imkan sağlarsa okadar veri tutulabilir.
2- Dizlerde araya eleman eklemek zahmetlidir. Bağlılistelerde basit birşekilde araya ekleme yapılabilir.
Dizilere göre dezavantajları :
1-Rasgele veya direk erişim sağlanamıyor.ilk eleman(head) dan tek tek ilerleyerek erişim sağlanır.Dolayısıyla dizilere göre daha yavaş ve zahmetlidir.
2-Bağlı listeleri oluşturan her düğümde birsonraki düğümü gösteren pointer(next) kullanılır. Dolayısıyla dahafazla bellek kullanırlar.
Yapımızı oluşturalım :
|
1 2 3 4 5 6 |
struct node {// node isminde bir yapı oluşturuyoruz. int data;//yapımızda verileri tutacagımız değişkenimizi belirliyoruz. struct node*next; //bir sonraki düğümü tutacak pointer ımızı tanımlıyoruz. !!Dikkat edelim yapımızla pointer tanımlıyoruz. }; |
Yapımızdaki elemanları ekrana basmak için bir fonksiyon yazıyoruz :
|
1 2 3 4 5 6 7 8 9 |
void printList(struct node* q){//parametre olarak head ı verilen listenin elenmanlarını ekrana basar. while (q!=NULL)//verilen parametremiz NULL olasıyakadar döngümüz dönüyor. { printf("%d - ", q->data);//ekrana basıyoruz. q = q->next;//birsonraki düğümü q değişkenine atıyoruz. } } |
Yapımızı Main imizde kullanalım :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
int main() { //ağagıda oluşturduğumuz yapımızdan düğümler oluşturup isimlerini veriyoruz. ve bellekten yer açıyoruz. struct node *head = (struct node*)malloc(sizeof(struct node)); struct node *second = (struct node*)malloc(sizeof(struct node)); struct node *third = (struct node*)malloc(sizeof(struct node)); head->next = second;//head düğümünün nexti second u gösteriyoruz. second->next = third;//secod un nexti third i gösteriyor third->next = NULL;//thirdden sonra şimdilik düğüm olmadıgı için next ine null atıyoruz. // yapımız head->next(second)->next(third)->next(null) şeklinde oluyor. parantez içleri anlamanız içim kod yazarken kullanılmıyor. head->data = 2;//head düğümümüze veri ataması yapıyoruz. second->data = 5; third->data = 10; printList(head);//head düğümünü oluşturduğumuz fonksiyona gönderip ekrana bastırıyoruz. getchar();//konsol ekranının kapanmaması için yazdığımız kod. return 0; } |
Temel olarak kullanım şekli yukardaki gibi ancak tabi buşekilde veri eklemek oldukça kullanışsız ve yorucu.İşlemleri kolaylaştırmak ve işlevli bir hale getirmek amacıyla bikaç ekleme fonksiyonu yazıcaz.
İlk olarak başa eleman ekleme fonksiyonumumuzu oluşturuyoruz:
|
1 2 3 4 5 6 7 8 9 10 |
void insertHead(struct node **q, int RefData)//parametre olarak aldığımız q yapısı ** ile çağırlıyor çünkü head değişicek. { struct node *tmp = (struct node*)malloc(sizeof(struct node));//bir düğüm oluşturuyoruz. tmp->next = *q;//oluşturduğumuz düğümün next ine parametre olarak gelen q yu atıyoruz. tmp->data = RefData;//parametre olarak gelen datayı oluşturduğumuz tmp düğümüne atıyoruz. (*q) = tmp;//temp imizi head olarak tanımlıyoruz. artık head tmp imiz. } |
Sona eleman ekleme fonksiyonumumuzu oluşturuyoruz :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void insertLast(struct node *q, int RefData)//head ımızı tek * ile çagırıyoruz head değişmeyeceği için ** a gerek yok. { struct node *tmp = (struct note*)malloc(sizeof(struct node));//Ekliyeceğimiz eleman için düğüm oluşturuyoruz. tmp->data = RefData;//oluşturdugumuz düğüme parametre olarak gelen veriyi atıyoruz. struct node *last = (struct note*)malloc(sizeof(struct node));// sonuncu düğümü bulmak için yeni bir düğüm oluşturuyoruz. last = q;//oluşturdugumuz düğüme parametre olarak gelen q yu atıyoruz. while (last->next!=NULL)//last düğümümüz next i null olan yani sonuncu düğüme kadar dönücek ve sonuncu düğümü elde etmiş olucaz. { last=last->next;//her döngü döndüğünde bi sonraki düğüme geçiyor. } last->next = tmp;//son düğümün next ine yukarda oluşturduğumuz düğümü atıyoruz. tmp->next = NULL;//oluşturdugumuz düğümün next ini null olarak atıyoruz. } |
Araya eleman ekleme fonksiyonumumuzu oluşturuyoruz :
|
1 2 3 4 5 6 7 8 |
void insertBetween(struct node **q, int RefData)//parametre olarak gelen düğümün sağ tarafına ekleme yapar. { struct node *tmp = (struct node*)malloc(sizeof(struct node));//yeni ekliyeceğimiz eleman için düğüm oluşturup ram den yer ayırıyoruz. tmp->next = (*q)->next;//parametre olarak gelen düğümün nextini oluşturdugumuz düğümün nextine atıyoruz. (*q)->next = tmp;//parametre olarak gelen düğümün next ine oluşturduğumuz düğümü atıyoruz. tmp->data = RefData;//oluşturdugumuz düğüme parametre olarak gelen datayı atıyoruz. } |
Farklı ekleme metotları yazdık şimdide silmek için bi fonksion yazalım :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
void deleteNode(struct node **head_ref, int key)//head de silinebileceği için head ımızı ** ile alıyoruz.ve silinicek veriyi parametere olarak alıyoruz. { struct node* tmp = *head_ref;//silmek için bir düğüm oluşturup parametre olarak gelen düğümü atıyoruz. struct node*prev = *head_ref; if (tmp != NULL && tmp->data == key)//eğer temp boş değilse ve datası parametere olarak gelen key ile uyuşuyorsa silme işlemi yapıcaz. { *head_ref = tmp->next; //head değiştiriliyor. free(tmp);//temp imizi ramden temizliyoruz. return;//fonksiyondan çıkıyoruz. } while (tmp != NULL && tmp->data != key)//temp null oluncaya kadar veya key i elmanlar arasında bulasıya kadar döngümüz dönüyor. { prev = tmp; tmp = tmp->next; } if (tmp == NULL) return;//temp null ise verilen key e uygun key elemanı yok demek oluyor ve fonksiyondan çıkıyor. prev->next = tmp->next;//aradan elemansildiğimizde bağlantı kopmaması için sileceiğimiz elemandan önceki elemanın next ine sildiğimiz elemanın next ini atıyoruz. free(tmp); //elemanımızı siliyoruz. } |
Son olarak yazdığımız fonksiyonları mainimizde çalıştıralım.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
int main() { //ağagıda oluşturduğumuz yapımızdan düğümler oluşturup isimlerini veriyoruz. ve bellekten yer açıyoruz. struct node *head = (struct node*)malloc(sizeof(struct node)); struct node *second = (struct node*)malloc(sizeof(struct node)); struct node *third = (struct node*)malloc(sizeof(struct node)); head->next = second;//head düğümünün nexti second u gösteriyoruz. second->next = third;//secod un nexti third i gösteriyor third->next = NULL;//thirdden sonra şimdilik düğüm olmadıgı için next ine null atıyoruz. // yapımız head->next(second)->next(third)->next(null) şeklinde oluyor. parantez içleri anlamanız içim kod yazarken kullanılmıyor. head->data = 2;//head düğümümüze veri ataması yapıyoruz. second->data = 5; third->data = 10; insertHead(&head, 4);//eklenicek listenin head ı ve parametreyi veriyoruz. insertBetween(&head->next, 6); insertLast(head, 31); deleteNode(&head, 31); printList(head);//head düğümünü oluşturduğumuz fonksiyona gönderip ekrana bastırıyoruz. getchar();//konsol ekranının kapanmaması için yazdığımız kod. return 0; } |
Eksik veya yanlış buldugunuz nokadar varsa iletişim bölümünden bana ulaşbilirsiniz.
İndirmek için Github : https://github.com/ibrahim-ekinci/Linked-List