Veri Yapıları Çift Yönlü Bağlı Liste (Doubly Linked List)
Çift yönlü bağlı liste mantığını anlamak için tek yönlüyü iyi anlamış olmanız önemli tek yönlü bağlı liste konusu hakkındaki yazıma bakabilisiniz :
Çift yönlü bağlı listeler tek yönlü bağlı listelerden yapısal olarak bir pointer daha eklenmiş halidir.Yani tek yönlü bağlı listede pointer olarak next(sonraki) imiz vardi şimdi ise prev(önceki) pointer ımızda eklenicek böylece her düğüm önceki ve sonraki düğümü pointerlar vasıtasıyla tutarlar.
Yapımızı oluşturalım.Tek yönlüden farklı olarak yukarda bahsettiğim gibi fazladan bi pointer imiz daha olucak.
|
1 2 3 4 5 6 |
struct Node //Node ismide yapımızı oluşturuyoruz. { int data;//Tutulacak veri için değişken struct Node*next;//Sonraki düğüm için pointer struct Node*prev;//Önceki düğüm için pointer }; |
Yapımızı oluşturduk. Şimdide ekleme fonksiyonlarımızı yazıcaz. Farklı senaryo ve durumlar için bi kaç temel ekleme metodu yazıcaz.
İlk olarak başa ekleme :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
void basaEkle(struct Node** head_Ref, int yeni_data)//listeye başa veri ekleme { struct Node* new_Node = (struct Node*)malloc(sizeof(struct Node));// Yeni bir node oluşturuyoruz. new_Node->data = yeni_data;//Oluşturduğumuz node a paramtere olarak gelen datayı atıyoruz. new_Node->next = (*head_Ref); //verilen head ın referansını yeni node un next ine atıyoruz. new_Node->prev = NULL;//ilk başta olacagı için ondan önce bir node olmayacak o yüzden null if ((*head_Ref) != NULL) (*head_Ref)->prev = new_Node;//yeni oluşturdugumuz nodedan sonraki node un pref ine yenisinin ref. ini atıyoruz *head_Ref = new_Node; //yeni node umuzu başdaki olarak gösteriyoruz } |
Sona ekleme için fonksiyonumuz :
|
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 |
void sonaEkle(struct Node** head_Ref, int yeni_data)//LİSTEYE SONDAN VERİ EKLEME { struct Node* new_Node = (struct Node*)malloc(sizeof(struct Node));//YENİ NODE OLUŞTURUYORUZ. struct Node* last_Node = *head_Ref;//SON NODE TUTACAK YAPI OLUŞTURUYORUZ new_Node->data = yeni_data;//PARAMETRE OLARAK VERİLEN DATAYI YENİ NODE ATIYORUZ. new_Node->next = NULL;//SONA EKLENECEGİ İÇİN NEXT İNİ NULL YAPIYORUZ if (*head_Ref == NULL)//HEAD OLARAK VERİLEN YAPI BOŞ İSE DİREK EKLEYİP METOD DAN ÇIKIYORUZ. { *head_Ref = new_Node; new_Node->prev = NULL; return; } while (last_Node->next != NULL)//DÖNGÜYE ALIP SON ELEMANA KADAR DÖNDÜRÜP SON ELEMANI BULUP LAST A ATIYORUZ. { last_Node = last_Node->next; } last_Node->next = new_Node;//SON ELAMANIN NEXT İNİN YENİ NODE UMUZ YAPIYORUZ. new_Node->prev = last_Node;//YENİ ELEMANIMIZIN PREV YANİ ÖNCEKİ ELEMANINI SON ELEMAN YAPIYORUZ. return; } |
Verilen key(data) in sağına ekleme fonksiyonu:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void ortayaEkle(struct Node *q, int item, int key)// verilen keye göre ekleme yapar. { struct Node *ptr = (struct Node*)malloc(sizeof(struct Node));// yeni ekliyeceğimiz düğümü oluşturup ram den yer ayırıyoruz. ptr->data = item;// parametre olarak gelen item verisini datamıza tıyoruz. struct Node *tmp = q;//head ımızı tmp e atıyoruz. while (tmp->data!=key)//verilen keye kadar gidiyoruz. key e ait düğüme gelesiye kadar döngü döner { tmp = tmp->next; } //verilen keyin sağına ekleme yapıcaz. ptr->next = tmp->next;// key den bulunan düğügümün next ini yeni düğümümüzün next ine atıyoruz. ptr->prev = tmp;//öncesindeki eleman olarak ta verilen key i alıyoruz. tmp->next = ptr;//keyimizin next ine oluşturduğumuz düğümü atıyoruz. ptr->next->prev = ptr;//ptr mizin nexti yani önceden keyimizin next i olan düğümün prev ine ptr mizi atıyoruz. } |
Verilen Node(düğüm) ün sağına ekleme yapan fonksiyon :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void onceEkle(struct Node* prev_Node, int yeni_data)//listeye ortadan veya saondan ekleme { if (prev_Node == NULL)//eğer verilen node boş ise metod dan çık { printf("Verilen Düğüm Boş---(sonaEkle metodu)"); return;// direk metodu bitirir ve çıkar } struct Node* new_Node = (struct Node*)malloc(sizeof(struct Node));//yeni node oluşturuyoruz new_Node->next = NULL; new_Node->data = yeni_data;//parametre olarak verilen datayı oluşturulan noda aktarıyoruz new_Node->next = prev_Node->next;//yeni node un next ine parametre verilen node un next indeki node u veriyoruz. prev_Node->next = new_Node;//parametre verilen node un next ini yeni node u atıyoruz new_Node->prev = prev_Node; //yeni oluşturdugumuz node a önceki olarak paramertereden gelen node u atıyoruz // yeni oluşturdugumuz node un next ini parametrenin next ini atıyoruz. //eğer yeni oluştudugumuz node dan sonra node var ise prev yani önceki olarak new node u göster if (new_Node->next != NULL) { new_Node->next->prev = new_Node; } } |
Şimdi ise silme fonksiyonlarımızı yazalım yine ekmede olduğu gibi farklı senaryolar için farklı silme fonksiyonları yazıcaz.
İlk olarak baştan silme fonksiyonu :
|
1 2 3 4 5 6 7 |
void bastanSil(struct Node **q)//head değişeceği için ** kullanılmalıdır. { struct Node *tmp = *q;//headımız tmp düğümümüze atıyoruz. *q = tmp->next;//tmp in next i ini head yapıyoruz. tmp->next->prev = NULL;//yeni head ımızın prev ini boşaltıyoruz. free(tmp);//ilk gelen head ımızı siliyoruz.free kullanılmaz ise ramde şişme olur. } |
Sondan silme fonksiyonumuz :
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void sondanSil(struct Node *q)//Verilen struct ın son düğümünü siler. { struct Node* last_Node = q;//SON NODE TUTACAK YAPI OLUŞTURUYORUZ while (last_Node->next != NULL)//DÖNGÜYE ALIP SON ELEMANA KADAR DÖNDÜRÜP SON ELEMANI BULUP LAST A ATIYORUZ. { last_Node = last_Node->next; } last_Node->prev->next = NULL;//silinecek elemandan önceki eleamının next ini boşaltıyoruz. free(last_Node);//ramimizden sonuncu düğümü siliyoruz. } |
Ortadan silme fonksiyonumuz :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void ortaSil(struct Node *q,int key)//içerisineki dataya göre silme işlemi yapar { struct Node *tmp = q; while (tmp->data != key)//DÖNGÜYE ALIP -VERİLEN ELEMANA AYİT OLANI BULUR { tmp = tmp->next; } if (tmp->data ==key)//SİLME İŞLEMİ İÇİN SONKEZ KEY OLUŞUYORMU DİYEK ONTROL EDİYORUZ. { tmp->prev->next = tmp->next; tmp->next->prev = tmp->prev; tmp->next = tmp->prev = NULL; free(tmp); } } |
Listemizi yazdırmak için bi fonksiyon yazıyoruz :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void ListeyiYazdır(struct Node* node)//verilen node a göre listeye yazdırma { struct Node* last =node;//son node u için kaydırmada kullanılıcak yapı. printf("Bastan sona :"); while (node != NULL)// verilen node dan başlayarak sona kadar olan node ları yazdırıyor. { printf("%d,", node->data); last = node; //ters yazdırmak için node = node->next; } printf("Sondan basa :"); while (last != NULL)// yukardaki döngüden dolayı zaten sona gelen last ı başa doğru giderek listeyi testen yazdırıyorz { printf("%d,", last->data); last = last->prev; } } |
Son olarak main imizde fonksiyonlarımızı kullanalım :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
int main() { //NOT: EĞER METOD DA ÇİFT YILDIZ KULLANILDIYSA DÜĞÜM VERİLİRKEN '&' İLE KULLANILMALI. struct Node* head = NULL; basaEkle(&head, 7); basaEkle(&head, 1); basaEkle(&head, 4); //onceEkle(head->next, 8); ortayaEkle(head, 6, 1); //sondanSil(head); //bastanSil(&head); //ortaSil(head,1); printf("Olusturulan node lar : "); ListeyiYazdır(head); } |
indirmek için Github : https://github.com/ibrahim-ekinci/CiftYonluBagliListe