4.4: Circular Linked List (Dairesel Liste)

🤔 Circular Linked List Nedir?

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'ya geri döner] 🔄

🎮 İnteraktif Dairesel Liste

🔄

0 tur

📋 Circular Liste Türleri

🔵 Circular Singly

A → B → C → ↩ A

Sadece ileri yönde döner.
Tek pointer (next)

🟣 Circular Doubly

↪ A ⟷ B ⟷ C ↩

İki yönde de döner.
İki pointer (prev, next)

💻 Python Implementasyonu

Python Kodu

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()

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head
        self.size += 1
        print(f"✅ Eklendi: {data}")
    
    def traverse(self, rounds=1):
        if not self.head: return
        current = self.head
        for i in range(rounds * self.size):
            print(f"→ {current.data}", end=" ")
            current = current.next
            if (i + 1) % self.size == 0:
                print("🔄")
    
    def display(self):
        if not self.head:
            print("[BOŞ]")
            return
        elements = []
        current = self.head
        while True:
            elements.append(str(current.data))
            current = current.next
            if current == self.head:
                break
        print(f"{' → '.join(elements)} → [HEAD] 🔄")

cll = CircularLinkedList()
for x in ["A", "B", "C", "D"]:
    cll.append(x)
cll.display()
print()
cll.traverse(2)

Çıktı bekleniyor...

🎯 Kullanım Alanları

🎵

Müzik Playlist

Son şarkıdan sonra başa dön (repeat mode)

⏰

Round Robin Scheduler

CPU zaman paylaşımı (işlemler sırayla)

🎮

Oyun Sırası

Oyuncular sırayla oynasın (Monopoly gibi)

🖼️

Carousel / Slider

Sonsuz dönen resim galerisi

🔥 Josephus Problemi - Circular LL ile Çözüm

📜 Tarihsel Problem (MS 67)

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ı!

🔄 Neden Circular Linked List?

Daire yapısı: Son kişiden sonra otomatik başa döner
Silme O(1): prev.next = current.next ile anında silme
Doğal model: Oyuncuların daire şeklinde oturmasını tam olarak modeller
Queue alternatifi: Queue ile de çözülür ama Circular LL daha doğal

Adım Adım: 6 Kişi, k=3 (Her 3. kişi elenir)

Başlangıç

6 kişi hazır

Tur 1: 3❌

1→2→3

Tur 2: 6❌

4→5→6

Tur 3: 4❌

1→2→4

Tur 4: 2❌

5→1→2

Tur 5: 1❌

Kazanan: 5

Tur	Sayma	Elenen	Kalanlar
1	1 → 2 → 3	3	[1, 2, 4, 5, 6]
2	4 → 5 → 6	6	[1, 2, 4, 5]
3	1 → 2 → 4	4	[1, 2, 5]
4	5 → 1 → 2	2	[1, 5]
5	5 → 1 → 5 (döngü)	1	🏆 [5] Kazandı!

Python Kodu

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)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def josephus_circular(players, k):
    if not players: return None
    
    head = Node(players[0])
    current = head
    for player in players[1:]:
        current.next = Node(player)
        current = current.next
    current.next = head
    
    print(f"🎮 Oyun: k={k}, Oyuncular: {players}\n")
    
    prev = current
    current = head
    
    while current.next != current:
        for _ in range(k - 1):
            prev = current
            current = current.next
        print(f"❌ {current.data} elendi!")
        prev.next = current.next
        current = current.next
    
    print(f"\n🏆 KAZANAN: {current.data}")

josephus_circular(["Ali", "Veli", "Ayşe", "Fatma", "Can", "Zeynep"], k=3)

Çıktı bekleniyor...