Dairesel Bağlı Liste Nedir?
Dairesel bağlı liste (circular linked list), son düğümün next pointer'ının NULL yerine ilk düğümü (head) gösterdiği bir bağlı liste çeşididir. Bu yapıda listenin "sonu" yoktur; herhangi bir düğümden başlayıp ilerlediğinizde sonunda başladığınız düğüme geri dönersiniz. Sonsuz bir halka gibi düşünebilirsiniz.
Gerçek hayattan en bilindik örneği yuvarlak masada oturan insanlardır: sırayla herkesin konuşma hakkı vardır ve son kişi konuştuktan sonra sıra tekrar ilk kişiye döner. Bu tam olarak round-robin zamanlama algoritmasının mantığıdır ve dairesel bağlı listelerle modellenir.
Tek Yönlü Dairesel Bağlı Liste
↓ son düğümün next'ini head'e bağla ↓
Dairesel (Circular) Liste
Son düğümün next'i = head → Sonsuz döngü
Temel Kavramlar
NULL Yok
Dairesel listede hiçbir düğümün next pointer'ı NULL değildir (tek yönlü dairesel) veya hiçbir düğümün prev/next'i NULL değildir (çift yönlü dairesel). Bu, traverse sırasında durma koşulunun değişmesi anlamına gelir: artık temp != NULL yerine temp != head (veya başlangıç noktası) kontrolü yapılır.
Head mi, Tail mi?
Dairesel listede "başlangıç" kavramı görecelidir çünkü liste bir halkadır. Ancak pratikte yine bir head pointer tutulur. İlginç bir optimizasyon ise head yerine tail pointer tutmaktır: tail'i biliyorsanız head'e tail->next ile O(1)'de ulaşabilirsiniz. Böylece hem başa hem sona O(1)'de ekleme yapabilirsiniz.
İki Çeşit Dairesel Liste
Tek Yönlü Dairesel
Her düğüm: data + next. Son düğümün next'i → head. Sadece ileri yön. Daha az bellek.
Çift Yönlü Dairesel
Her düğüm: prev + data + next. Son→next = head, head→prev = son. İki yön. En esnek.
Sonsuz Döngü Riski
Dairesel listede while (temp != NULL) yazarsanız döngü asla bitmez çünkü hiçbir düğüm NULL değildir. Traverse döngüsü her zaman başlangıç noktasını kontrol etmelidir. Bu, dairesel listelerle çalışırken en kritik farktır ve unutulması programın donmasına yol açar.
Tek Yönlü Dairesel Liste Oluşturma
Tek yönlü dairesel liste, normal singly linked list ile aynı node yapısını kullanır. Tek fark: son düğümün next pointer'ı NULL yerine head'i gösterir. Tek elemanlı bir dairesel listede düğümün next'i kendisini gösterir.
Tek Elemanlı Dairesel Liste
next → kendisi (tek elemanlı halka)
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* yeniDugum(int deger) {
Node* dugum = (Node*)malloc(sizeof(Node));
if (!dugum) { printf("Bellek hatası!\n"); exit(1); }
dugum->data = deger;
dugum->next = dugum; // ← kendisine bağla (dairesel başlangıç)
return dugum;
}
// Tek yönlü dairesel liste oluşturma
Node* daireselOlustur(int degerler[], int n) {
if (n == 0) return NULL;
Node* head = yeniDugum(degerler[0]);
Node* tail = head;
for (int i = 1; i < n; i++) {
Node* yeni = yeniDugum(degerler[i]);
tail->next = yeni;
yeni->next = head; // her zaman head'e bağla
tail = yeni;
}
return head;
}
// Kullanım:
int arr[] = {10, 20, 30, 40};
Node* head = daireselOlustur(arr, 4);
// 10 → 20 → 30 → 40 → (head'e geri: 10)Tail pointer avantajı: Dairesel listede tail pointer tutmak çok güçlüdür. tail->next zaten head olduğu için tail'den hem başa (O(1)) hem sona (O(1)) erişebilirsiniz. Bu yüzden bazı implementasyonlar head yerine sadece tail tutar.
Çift Yönlü Dairesel Liste Oluşturma
Çift yönlü dairesel liste, bağlı listelerin en esnek çeşididir. Her düğüm hem ileri hem geri bağlantıya sahiptir ve son düğüm head'e, head ise son düğüme bağlıdır. Bu yapıda herhangi bir düğümden başlayarak her iki yöne de sonsuz dolaşabilirsiniz.
Çift Yönlü Dairesel Bağlı Liste
head→prev = son düğüm | son→next = head → İki yönlü halka
typedef struct DNode {
int data;
struct DNode* prev;
struct DNode* next;
} DNode;
DNode* yeniDDugum(int deger) {
DNode* d = (DNode*)malloc(sizeof(DNode));
if (!d) { printf("Bellek hatası!\n"); exit(1); }
d->data = deger;
d->prev = d; // kendisine bağla
d->next = d; // kendisine bağla
return d;
}
DNode* daireselCiftOlustur(int degerler[], int n) {
if (n == 0) return NULL;
DNode* head = yeniDDugum(degerler[0]);
for (int i = 1; i < n; i++) {
DNode* yeni = yeniDDugum(degerler[i]);
DNode* tail = head->prev; // ← son düğüm her zaman head→prev
// Yeni düğümü sona ekle (4 bağlantı)
tail->next = yeni;
yeni->prev = tail;
yeni->next = head;
head->prev = yeni;
}
return head;
}
// Kullanım:
int arr[] = {10, 20, 30};
DNode* head = daireselCiftOlustur(arr, 3);
// ↻ 10 ⇄ 20 ⇄ 30 ↻
// head→prev = 30, 30→next = head(10)head→prev = tail: Çift yönlü dairesel listenin güzel tarafı şudur: ayrı bir tail pointer tutmanıza gerek yoktur. head->prev her zaman son düğümdür. Bu, hem sona eklemeyi hem de sondan silmeyi O(1) yapar ve ekstra pointer yönetim yükünü ortadan kaldırır.
Traverse İşlemi (Dolaşma)
Dairesel listede traverse, normal listeden farklı bir durma koşulu gerektirir. NULL'a ulaşmak yerine başlangıç düğümüne geri dönüp dönmediğinizi kontrol edersiniz. do...while döngüsü bu iş için idealdir çünkü en az bir kez döngü gövdesi çalışmalıdır (head'i de işlemek için).
Dairesel Traverse — Durma Koşulu
Adım 1–3: Her düğümü ziyaret et
Adım 4: temp == head → DUR (bir tur tamamlandı)
// Tek yönlü dairesel traverse
void daireselYazdir(Node* head) {
if (head == NULL) {
printf("Liste boş!\n");
return;
}
Node* temp = head;
do {
printf("%d → ", temp->data);
temp = temp->next;
} while (temp != head); // ← başlangıca dönünce dur
printf("(head'e döndü)\n");
}
// Çıktı: 10 → 20 → 30 → (head'e döndü)
// Çift yönlü dairesel — ileri ve geri
void ileriYazdir(DNode* head) {
if (head == NULL) return;
DNode* temp = head;
do {
printf("%d ⇄ ", temp->data);
temp = temp->next;
} while (temp != head);
printf("↻\n");
}
void geriYazdir(DNode* head) {
if (head == NULL) return;
DNode* temp = head->prev; // son düğümden başla
do {
printf("%d ⇄ ", temp->data);
temp = temp->prev;
} while (temp != head->prev);
printf("↻\n");
}
// İleri: 10 ⇄ 20 ⇄ 30 ⇄ ↻
// Geri: 30 ⇄ 20 ⇄ 10 ⇄ ↻Sonsuz döngü tuzağı: Dairesel listede asla while (temp != NULL) yazmayın. NULL olmadığı için döngü sonsuza kadar çalışır. Her zaman do...while (temp != başlangıç) kullanın veya bir sayaç ile döngü sayısını sınırlayın.
Eleman Ekleme
Başa Ekleme
Dairesel listede başa ekleme, yeni düğümü head'in önüne koymak ve son düğümün next'ini yeni düğüme güncellemek demektir. Normal listeden farkı: son düğümü bulup onun next'ini de değiştirmek zorundasınız, aksi halde halka bozulur.
Başa 5 Ekleme (Tek Yönlü Dairesel)
2
Yeni düğüm ekle, son düğümü güncelle:
yeni→next = head, son→next = yeni, head = yeni
void basaEkle(Node** head, int deger) {
Node* yeni = yeniDugum(deger);
if (*head == NULL) {
*head = yeni;
return; // tek elemanlı halka (next → kendisi)
}
// Son düğümü bul (next'i head olan)
Node* tail = *head;
while (tail->next != *head) {
tail = tail->next;
}
yeni->next = *head; // yeninin next'i → eski head
tail->next = yeni; // son düğüm → yeni head'e bağla
*head = yeni; // head'i güncelle
}Sona Ekleme
void sonaEkle(Node** head, int deger) {
Node* yeni = yeniDugum(deger);
if (*head == NULL) {
*head = yeni;
return;
}
// Son düğümü bul
Node* tail = *head;
while (tail->next != *head) {
tail = tail->next;
}
tail->next = yeni; // eski son → yeni
yeni->next = *head; // yeni son → head (halkayı koru)
}Tail Pointer ile O(1) Ekleme
Hem başa hem sona eklemede son düğümü bulmak O(n) sürer. Tail pointer tutarak bu maliyeti O(1)'e düşürebilirsiniz. Tail pointer'lı yapıda head'e tail->next ile erişilir.
// Tail pointer ile sona ekleme — O(1)
void sonaEkleTail(Node** tail, int deger) {
Node* yeni = yeniDugum(deger);
if (*tail == NULL) {
*tail = yeni;
return;
}
yeni->next = (*tail)->next; // yeni → head
(*tail)->next = yeni; // eski tail → yeni
*tail = yeni; // tail güncelle
}
// Tail pointer ile başa ekleme — O(1)
void basaEkleTail(Node** tail, int deger) {
Node* yeni = yeniDugum(deger);
if (*tail == NULL) {
*tail = yeni;
return;
}
yeni->next = (*tail)->next; // yeni → eski head
(*tail)->next = yeni; // tail → yeni (yeni head olur)
// tail değişmez! head = tail->next artık yeni düğüm
}Çift Yönlü Dairesel — Araya Ekleme
void sonrasinaEkle(DNode* hedef, int deger) {
if (hedef == NULL) return;
DNode* yeni = yeniDDugum(deger);
DNode* sonraki = hedef->next;
// 4 bağlantı (çift yönlü dairesel kuralı)
yeni->next = sonraki; // ❶
yeni->prev = hedef; // ❷
sonraki->prev = yeni; // ❸
hedef->next = yeni; // ❹
}
// NULL kontrolüne gerek yok! Dairesel listede
// sonraki hiçbir zaman NULL değildir.Dairesel listenin güzel tarafı: Normal listede araya ekleme sırasında "sonraki düğüm NULL mı?" kontrolü yapmak zorundasınız. Dairesel listede hiçbir next/prev NULL olamaz, bu yüzden NULL kontrol ifadelerine gerek kalmaz. Kod daha temiz ve hata yapma olasılığı daha düşüktür.
Eleman Silme
Baştan Silme
Baştan Silme (Tek Yönlü Dairesel)
1
Head silinecek, tail'in bağlantısı güncellenecek:
2
head = head→next, tail→next = yeni head, free():
// Tek yönlü dairesel — baştan silme
void bastanSil(Node** head) {
if (*head == NULL) return;
// Tek eleman varsa
if ((*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
// Tail'i bul
Node* tail = *head;
while (tail->next != *head) {
tail = tail->next;
}
Node* silinecek = *head;
*head = (*head)->next; // head ilerle
tail->next = *head; // tail → yeni head
free(silinecek);
}
// Tek yönlü dairesel — belirli değeri silme
void degerSil(Node** head, int deger) {
if (*head == NULL) return;
// Head silinecekse
if ((*head)->data == deger) {
bastanSil(head);
return;
}
Node* temp = *head;
while (temp->next != *head && temp->next->data != deger) {
temp = temp->next;
}
if (temp->next == *head) {
printf("%d bulunamadı!\n", deger);
return;
}
Node* silinecek = temp->next;
temp->next = silinecek->next; // atlayarak bağla
free(silinecek);
}Çift Yönlü Dairesel — Düğüm Silme
Çift yönlü dairesel listede düğüm silmek en temiz halidir. NULL kontrolü gerekmez, önceki ve sonraki her zaman mevcuttur. Sadece iki bağlantıyı güncelleyip free() çağrısı yaparsınız.
void dugumSilCD(DNode** head, DNode* silinecek) {
if (*head == NULL || silinecek == NULL) return;
// Tek eleman varsa
if (silinecek->next == silinecek) {
*head = NULL;
free(silinecek);
return;
}
// Bağlantıları güncelle — NULL kontrolü gerekmez!
silinecek->prev->next = silinecek->next;
silinecek->next->prev = silinecek->prev;
// Head siliniyorsa head'i güncelle
if (silinecek == *head) {
*head = silinecek->next;
}
free(silinecek);
}
// Karşılaştırma:
// Normal doubly: if (sil->prev) sil->prev->next = sil->next;
// if (sil->next) sil->next->prev = sil->prev;
// Circular doubly: sil->prev->next = sil->next; ← her zaman geçerli
// sil->next->prev = sil->prev; ← her zaman geçerliDöngü Tespiti — Floyd Algoritması
Dairesel listeler kasıtlı olarak döngüsel tasarlanmış yapılardır. Ancak bazen normal bir bağlı listede yanlışlıkla döngü oluşur (bir düğümün next'i listenin önceki bir düğümüne bağlanır). Bu durumu tespit etmek için kullanılan en zarif algoritma Floyd'un Tortoise and Hare (Kaplumbağa ve Tavşan) algoritmasıdır.
Problem Tanımı
Verilen bir bağlı listede döngü var mı? Yani herhangi bir düğümün next pointer'ı listenin önceki bir düğümüne mi bağlı?
Döngülü Liste Örneği
5'in next'i → 3 (döngü!) | Normal sonlanma (NULL) yok
Algoritmanın Mantığı
İki pointer kullanılır: slow (kaplumbağa) her adımda 1 düğüm ilerler, fast (tavşan) her adımda 2 düğüm ilerler. Eğer döngü varsa fast sonunda slow'u yakalar ve ikisi aynı düğümde buluşur. Eğer döngü yoksa fast NULL'a ulaşır ve algoritma biter.
Neden buluşurlar? Düşünün: dairesel bir pistte koşan iki koşucu. Hızlı olan her turda yavaş olana 1 birim daha yaklaşır. Sonunda onu yakalar. Bu kaçınılmazdır.
Floyd Algoritması — Adım Adım
0
Başlangıç: slow = head, fast = head
1
Adım 1: slow+1 → 2, fast+2 → 3
2
Adım 2: slow+1 → 3, fast+2 → 5
3
Adım 3: slow+1 → 4, fast+2 → 4 → BULUŞTU!
slow == fast → Döngü tespit edildi!
// Floyd'un Kaplumbağa ve Tavşan Algoritması
int donguVarMi(Node* head) {
if (head == NULL) return 0;
Node* slow = head; // kaplumbağa: 1 adım
Node* fast = head; // tavşan: 2 adım
while (fast != NULL && fast->next != NULL) {
slow = slow->next; // 1 adım ilerle
fast = fast->next->next; // 2 adım ilerle
if (slow == fast) {
return 1; // döngü var!
}
}
return 0; // fast NULL'a ulaştı → döngü yok
}Karmaşıklık: Zaman: O(n) — her düğüm en fazla iki kez ziyaret edilir. Alan: O(1) — sadece 2 pointer kullanılır. Bu, döngü tespitinin en verimli yöntemidir. Alternatif yöntemler (hash set ile ziyaret edilen düğümleri tutmak) O(n) ekstra bellek kullanır.
Döngünün Başlangıç Noktasını Bulma
Floyd algoritmasının ikinci aşaması, döngünün nerede başladığını bulur. Slow ve fast buluştuktan sonra, slow'u head'e geri koyun ve her ikisini birer adım ilerletin. Tekrar buluştukları yer döngünün başlangıç noktasıdır.
Node* donguBaslangici(Node* head) {
if (head == NULL) return NULL;
Node* slow = head;
Node* fast = head;
// Aşama 1: Buluşma noktasını bul
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
// Döngü yoksa
if (fast == NULL || fast->next == NULL)
return NULL;
// Aşama 2: slow'u head'e koy, her ikisi birer adım
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // döngünün başlangıç düğümü
}
// Örnek: 1 → 2 → 3 → 4 → 5 → 3 (döngü)
// Sonuç: Düğüm 3 (döngünün başlangıcı)Neden Çalışır? — Matematiksel Kanıt Özeti
L = döngü öncesi düğüm sayısı
C = döngü uzunluğu
Buluşma anında:
slow: L + k adım atmış (k = döngü içinde kat edilen)
fast: L + k + n×C adım atmış (n tur fark)
fast = 2 × slow → L + k + nC = 2(L + k)
→ nC = L + k → L = nC - k
Bu demek ki: head'den L adım ilerlemek =
buluşma noktasından (C - k) adım ilerlemek.
Her ikisi de döngünün başında buluşur.
Döngüyü Kırma (Fixing the Loop)
void donguKir(Node* head) {
Node* slow = head;
Node* fast = head;
// Buluşma noktasını bul
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (fast == NULL || fast->next == NULL) return;
// Döngü başlangıcını bul
slow = head;
while (slow->next != fast->next) {
slow = slow->next;
fast = fast->next;
}
// fast şimdi döngünün son düğümünde
fast->next = NULL; // döngüyü kır
}Karşılaştırma Tablosu
| İşlem | Linear Singly | Circular Singly | Circular Doubly |
|---|
| Başa ekleme | O(1) | O(n)* | O(1) |
| Sona ekleme (tail yok) | O(n) | O(n) | O(1) |
| Sona ekleme (tail var) | O(1) | O(1) | O(1) |
| Baştan silme | O(1) | O(n)* | O(1) |
| Sondan silme | O(n) | O(n) | O(1) |
| Düğüm silme (pointer var) | O(n) | O(n) | O(1) |
| Geri traverse | — | — | O(n) |
| NULL kontrol gereksinimi | Her yerde | Azaltılmış | Hiç gerekmez |
* Tail pointer ile O(1): Tek yönlü dairesel listede başa ekleme ve baştan silme normalde O(n)'dir (tail'i bulmak için). Ancak tail pointer tutuluyorsa hem başa hem sona ekleme O(1) olur. Çift yönlü dairesel ise tail pointer gerektirmez çünkü head->prev zaten tail'dir.
Dairesel Listeler Nerelerde Kullanılır?
Round-Robin Zamanlama
İşletim sistemlerinde CPU zamanını processlere eşit dağıtmak için round-robin algoritması kullanılır. Her process bir dairesel liste düğümüdür. CPU sırayla her process'e belirli bir zaman dilimi (time quantum) verir ve zaman dolunca sıradaki process'e geçer. Listenin sonuna gelince otomatik olarak başa döner.
Josephus Problemi
Klasik bir bilgisayar bilimi problemidir: n kişi dairesel olarak oturur ve her k. kişi elenecektir. Son kalan kim olur? Bu problem dairesel bağlı listeyle doğal olarak modellenir ve her silme operasyonu k adım ilerleyip düğümü silmektir.
Multiplayer Oyun Döngüsü
Sıra tabanlı çok oyunculu oyunlarda (satranç, kart oyunları) oyuncular bir dairesel listede tutulur. Bir oyuncu hamle yaptıktan sonra sıra otomatik olarak sonrakine geçer ve son oyuncudan sonra ilk oyuncuya döner.
Müzik Çalar — Repeat All
Müzik uygulamalarında "Tümünü Tekrarla" modu dairesel listedir. Son şarkı bittiğinde pointer head'e döner ve çalma listesi baştan başlar. "Tekrarlama Kapalı" ise normal linear listedir (NULL'da durur).
Dönen Tampon (Circular Buffer / Ring Buffer)
Ağ programlama ve gömülü sistemlerde çok kullanılan circular buffer, sabit boyutlu bir dizinin dairesel olarak kullanılmasıdır. Yazma pointer'ı sonuna gelince başa döner ve eski verilerin üzerine yazar. Veri akışı, log tutma ve producer-consumer senaryolarında temeldir.
Sonuç
Dairesel bağlı listeler, "son" kavramını ortadan kaldırarak döngüsel doğaya sahip problemlere doğal ve verimli çözümler sunar. Round-robin zamanlama, oyun döngüleri, circular buffer gibi yapılar doğrudan dairesel listelere dayanır. Floyd algoritması ise hem dairesel listelerin hem de döngü tespitinin temelini oluşturur ve mülakatlarda en çok sorulan sorulardan biridir.
Bağlı listeler serisini burada tamamlıyoruz: tek yönlü, çift yönlü ve dairesel listelerin tüm varyasyonlarını ele aldık. Bu üç yapıyı iyi kavramak, bir sonraki konumuz olan stack (yığın) ve queue (kuyruk) veri yapılarını anlamak için güçlü bir temel oluşturur. Stack ve queue aslında bağlı listelerin üzerine kurulu soyut veri yapılarıdır ve pratikte çoğunlukla linked list ile gerçeklenir.