Dairesel Bağlı Liste - Sonsuz Döngü
Dairesel Bağlı Listede son node'un next işaretçisi NULL yerine ilk node'a (head) işaret eder. Bu sayede liste bir halka oluşturur ve sonsuza kadar dönebilirsiniz.
A → B → C → D → A → B → C → D → A → ... ∞
Bu soruyu cevaplamak için önce şu senaryoyu düşünelim: Bir müzik çalar uygulaması yazıyorsunuz ve kullanıcı "tekrar modu"nu (repeat) açtığında son şarkı bitince otomatik olarak ilk şarkıya dönmesini istiyorsunuz. Ya da bir oyun yapıyorsunuz ve 4 oyuncu sırayla oynuyor — 4. oyuncudan sonra tekrar 1. oyuncuya geçmesi gerekiyor.
Diyelim ki 4 şarkılık bir playlist'imiz var: A → B → C → D → NULL
Şarkıları sırayla çalmak için şöyle bir kod yazarız:
current = head # A'dan başla
while current != None:
play(current.song) # Şarkıyı çal
current = current.next # Sonraki şarkıya geçBu kod D şarkısını çaldıktan sonra current = None olur ve döngü biter. Peki ya kullanıcı "tekrar modu" açtıysa? O zaman başa dönmemiz gerekiyor:
current = head
while repeat_mode:
play(current.song)
current = current.next
# ⚠️ SORUN: Liste bitti mi kontrol et!
if current == None:
current = head # Başa dön - ama HEAD'i ayrıca saklamak zorundayız!Burada birkaç sorun var:
Birincisi, her adımda "liste bitti mi?" diye kontrol etmek zorundayız. Bu ekstra bir if kontrolü demek ve kodun karmaşıklığını artırıyor. İkincisi, head değişkenini ayrıca saklamak ve erişilebilir tutmak zorundayız. Eğer fonksiyonlar arasında geçiş yapıyorsak veya sadece current pointer'ını parametre olarak geçiriyorsak, head'e nasıl ulaşacağız? Üçüncüsü, bu yaklaşım hata yapmaya çok açık. Geliştirici if current == None kontrolünü unutursa program çöker.
Şimdi aynı playlist'i Circular Linked List olarak düşünelim: A → B → C → D → A → B → ...
Son node (D), NULL yerine ilk node'a (A) işaret ediyor. Kod şöyle basitleşiyor:
current = head
while repeat_mode:
play(current.song)
current = current.next # Otomatik olarak başa döner!Fark ettiniz mi?
Hiçbir if kontrolü yok! D'den sonra current.next zaten A'yı gösteriyor, dolayısıyla otomatik olarak başa dönüyoruz. HEAD'i ayrıca saklamaya gerek yok çünkü liste hiç bitmiyor — sonsuza kadar dönüyor. Kod çok daha temiz, okunabilir ve hata yapma ihtimali çok daha düşük.
Bu, Circular Linked List'in temel avantajı: döngüsel işlemleri doğal olarak modelliyor. NULL kontrolü yapmak yerine, veri yapısının kendisi döngüyü sağlıyor.
İşletim sistemleri, birden fazla programın (process) aynı anda çalışıyormuş gibi görünmesini sağlamak için Round Robin algoritmasını kullanır. Her process'e sırayla küçük bir zaman dilimi (time quantum) verilir ve süre dolunca sıradaki process'e geçilir.
Diyelim ki 3 process var: P1, P2, P3. Her birine 10ms zaman verilecek:
P1(10ms) → P2(10ms) → P3(10ms) → P1(10ms) → P2(10ms) → P3(10ms) → ...
Bu tam olarak circular bir yapı! Eğer normal linked list kullansaydık, P3'ten sonra "liste bitti, başa dön" mantığı yazmak zorunda kalacaktık. Ama circular linked list ile scheduler kodu şöyle basit oluyor:
current_process = process_list.head
while True:
run_for(current_process, time_quantum=10) # 10ms çalıştır
current_process = current_process.next # Sonraki process (otomatik döngü!)Hiçbir process sonsuza kadar beklemez, hepsi eşit şekilde CPU zamanı alır ve kod son derece temiz kalır.
Sadece ileri yönde döner.
Tek pointer (next)
İki yönde de döner.
İki pointer (prev, next)
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
"""Dairesel Tek Yönlü Bağlı Liste"""
def __init__(self):
self.head = None
self.size = 0
def append(self, data):
"""Sona ekle"""
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = self.head # Kendine döner
else:
# Son node'u bul
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head # Başa bağla
self.size += 1
print(f"✅ Eklendi: {data}")
def prepend(self, data):
"""Başa ekle"""
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = self.head
else:
# Son node'u bul
current = self.head
while current.next != self.head:
current = current.next
new_node.next = self.head
current.next = new_node # Son node yeni başı göstersin
self.head = new_node
self.size += 1
print(f"✅ Başa eklendi: {data}")
def delete(self, data):
"""Değeri sil"""
if not self.head:
return
# Silinecek head ise
if self.head.data == data:
if self.head.next == self.head: # Tek eleman
self.head = None
else:
# Son node'u bul
current = self.head
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
self.size -= 1
print(f"🗑️ Silindi: {data}")
return
# Ara ve sil
current = self.head
while current.next != self.head:
if current.next.data == data:
current.next = current.next.next
self.size -= 1
print(f"🗑️ Silindi: {data}")
return
current = current.next
def traverse(self, rounds=1):
"""Listeyi dolaş (kaç tur?)"""
if not self.head:
print("Liste boş!")
return
print(f"🔄 {rounds} tur dolaşılıyor:")
current = self.head
count = 0
for _ in range(rounds * self.size):
print(f" → {current.data}", end="")
current = current.next
count += 1
if count % self.size == 0:
print(" (tur tamamlandı)")
def display(self):
"""Listeyi göster"""
if not self.head:
print("Liste: [BOŞ]")
return
elements = []
current = self.head
while True:
elements.append(str(current.data))
current = current.next
if current == self.head:
break
print(f"Liste: {' → '.join(elements)} → [HEAD'e döner] 🔄")
# Test
print("🔄 Circular Linked List Demo\n")
cll = CircularLinkedList()
cll.append("A")
cll.append("B")
cll.append("C")
cll.append("D")
cll.display()
print()
cll.traverse(2) # 2 tur
print()
cll.delete("B")
cll.display()
print()
cll.prepend("X")
cll.display()Son şarkıdan sonra başa dön (repeat mode)
CPU zaman paylaşımı (işlemler sırayla)
Oyuncular sırayla oynasın (Monopoly gibi)
Sonsuz dönen resim galerisi
Josephus Flavius ve 40 Yahudi asker Romalılar tarafından kuşatıldı. Teslim olmak yerine toplu intihar kararı aldılar: Daire şeklinde durup her k. kişi öldürülecekti. Josephus matematiği kullanarak kendini doğru konuma yerleştirdi ve hayatta kaldı!
Her k. kişi elenir. Parametreleri değiştirip simülasyonu izleyin!
class Node:
def __init__(self, data):
self.data = data
self.next = None
def josephus_circular(players, k):
"""
Josephus Problemi - Circular Linked List ile
Her k. kişi elenir, son kalan kazanır.
"""
if not players:
return None
# Circular liste oluştur
head = Node(players[0])
current = head
for player in players[1:]:
current.next = Node(player)
current = current.next
current.next = head # Daireyi kapat
print(f"🎮 Oyun Başlıyor! k={k}")
print(f"Oyuncular: {players}\n")
# Son bir kişi kalana kadar
prev = current # Son node
current = head
while current.next != current: # Tek eleman kalana kadar
# k-1 adım ilerle
for _ in range(k - 1):
prev = current
current = current.next
# current'ı elen
print(f"❌ {current.data} elendi!")
prev.next = current.next
current = current.next
print(f"\n🏆 KAZANAN: {current.data}")
return current.data
# Test
players = ["Ali", "Veli", "Ayşe", "Fatma", "Can", "Zeynep"]
josephus_circular(players, k=3)Josephus probleminin kapalı formül çözümü de vardır (k=2 için):
Örnek: n=6 için: 6 = 4 + 2 = 2² + 2, yani L=2 → J(6) = 2×2 + 1 = 5 ✅
Circular LL ile simülasyon, bu formülü anlamak ve doğrulamak için mükemmel!
Çocuklar daire şeklinde oturur. Müzik çalarken bir top (veya patates) elden ele geçer. Müzik durduğunda topu elinde tutan kişi elenir. Son kalan kazanır!
Josephus ile farkı: Josephus'ta sayı sabit (her k. kişi), Hot Potato'da rastgele (müzik ne zaman durursa).
Müzik rastgele durur. Her turda 1-5 arası geçiş yapılır!
Müzik 3. geçişte durdu → Can elendi, oyun 4 kişiyle devam eder
import random
class Node:
def __init__(self, data):
self.data = data
self.next = None
def hot_potato(players):
"""
Sıcak Patates Oyunu - Circular Linked List ile
Her turda rastgele sayıda geçiş yapılır.
"""
if not players:
return None
# Circular liste oluştur
head = Node(players[0])
current = head
for player in players[1:]:
current.next = Node(player)
current = current.next
current.next = head # Daireyi kapat
print("🥔 SICAK PATATES OYUNU!")
print(f"Oyuncular: {players}\n")
# Son bir kişi kalana kadar
prev = current
current = head
round_num = 1
while current.next != current:
# Rastgele sayıda geçiş (müzik rastgele durur)
passes = random.randint(1, 5)
print(f"🎵 Tur {round_num}: Patates {passes} kez geçiyor...")
for i in range(passes):
print(f" {current.data}", end="")
prev = current
current = current.next
if i < passes - 1:
print(" →", end="")
print(f"\n🔇 Müzik durdu! {current.data} elendi!\n")
# current'ı elen
prev.next = current.next
current = current.next
round_num += 1
print(f"🏆 KAZANAN: {current.data}")
return current.data
# Oyunu oyna
players = ["Ali", "Bea", "Can", "Def", "Ela"]
hot_potato(players)