4.3: Doubly Linked List (Çift Yönlü Liste)

🤔 Doubly Linked List Nedir?

Her node hem önceki (prev) hem de sonraki (next) node'a işaretçi tutar. Bu sayede listede iki yönlü hareket edebiliriz.

NULL

←

NULL

◀ prev | DATA | next ▶

🎮 İnteraktif Simülasyon

📊 Singly vs Doubly Karşılaştırma

➡️ Singly Linked List

Sadece ileri gidebilir
Daha az hafıza (1 pointer)
Silme için önceki node lazım
Sondan silme O(n)

↔️ Doubly Linked List

İleri ve geri gidebilir
Daha fazla hafıza (2 pointer)
Silme kolaylaşır (prev var)
Sondan silme O(1) (tail ile)

📋 Temel Operasyonlar (Detaylı)

1️⃣ Başa Ekleme (prepend) O(1)

Listeye "X" değerini en başa ekliyoruz.

prepend() Kodu

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def prepend(self, data):
        """Başa ekle - O(1)"""
        new_node = DoublyNode(data)

        if not self.head:  # Liste boşsa
            self.head = self.tail = new_node
        else:
            new_node.next = self.head   # 1. X.next = A
            self.head.prev = new_node   # 2. A.prev = X
            self.head = new_node        # 3. HEAD = X

        print(f"✅ '{data}' başa eklendi")

# Test
dll = DoublyLinkedList()
dll.prepend("B")
dll.prepend("A")
dll.prepend("X")  # X başa eklenir
print(f"HEAD: {dll.head.data}, TAIL: {dll.tail.data}")

2️⃣ Sona Ekleme (append) O(1)

Listeye "X" değerini en sona ekliyoruz. TAIL pointer sayesinde son elemana O(1)'de ulaşıyoruz.

append() Kodu

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        """Sona ekle - O(1)"""
        new_node = DoublyNode(data)

        if not self.tail:  # Liste boşsa
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail   # 1. X.prev = B
            self.tail.next = new_node   # 2. B.next = X
            self.tail = new_node        # 3. TAIL = X

        print(f"✅ '{data}' sona eklendi")

# Test
dll = DoublyLinkedList()
dll.append("A")
dll.append("B")
dll.append("X")  # X sona eklenir
print(f"HEAD: {dll.head.data}, TAIL: {dll.tail.data}")

3️⃣ Sondan Silme (pop_back) O(1)

Listenin son elemanını (C) siliyoruz. Doubly'nin en büyük avantajı: Singly'de O(n), burada O(1)!

pop_back() Kodu

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = DoublyNode(data)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def pop_back(self):
        """Sondan sil - O(1)"""
        if not self.tail:
            return None

        data = self.tail.data

        if self.tail == self.head:  # Tek eleman
            self.head = self.tail = None
        else:
            new_tail = self.tail.prev  # 1. B'yi bul (tail.prev)
            new_tail.next = None       # 2. B.next = None
            self.tail = new_tail       # 3. TAIL = B

        print(f"🗑️ '{data}' silindi")
        return data

# Test
dll = DoublyLinkedList()
dll.append("A")
dll.append("B")
dll.append("C")
print(f"Silmeden önce TAIL: {dll.tail.data}")
dll.pop_back()  # C silinir
print(f"Sildikten sonra TAIL: {dll.tail.data}")

4️⃣ Ortadan Silme (delete_node) O(1)

Elimizde B node'unun referansı var ve onu silmek istiyoruz. prev pointer sayesinde önceki node'a da erişebiliyoruz.

delete_node() Kodu

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = DoublyNode(data)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        return new_node  # Node referansı döndür

    def delete_node(self, node):
        """Verilen node'u sil - O(1)"""
        if not node:
            return

        # 1. Önceki node'un next'ini güncelle
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next  # Silinen HEAD ise

        # 2. Sonraki node'un prev'ini güncelle
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev  # Silinen TAIL ise

        print(f"🗑️ '{node.data}' silindi")

# Test
dll = DoublyLinkedList()
dll.append("A")
node_b = dll.append("B")  # B'nin referansını sakla
dll.append("C")

print("Silmeden önce: A ⟷ B ⟷ C")
dll.delete_node(node_b)  # B'yi sil
print("Sildikten sonra: A ⟷ C")

5️⃣ Arama (search) O(n)

Listede "C" değerini arıyoruz. Arama işlemi hâlâ O(n) - değerin nerede olduğunu bilmiyoruz.

search() Kodu

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = DoublyNode(data)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def search(self, target):
        """Değer ara - O(n)"""
        current = self.head
        index = 0

        while current:
            print(f"  Kontrol: {current.data} == {target}?", end=" ")
            if current.data == target:
                print("✅ BULUNDU!")
                return index
            print("❌")
            current = current.next
            index += 1

        print(f"'{target}' bulunamadı")
        return -1

# Test
dll = DoublyLinkedList()
dll.append("A")
dll.append("B")
dll.append("C")
dll.append("D")

print("'C' aranıyor:")
result = dll.search("C")
print(f"Sonuç: index {result}")

💻 Tam Python Implementasyonu

Python Kodu

class DoublyNode:
    """Çift yönlü bağlı liste düğümü"""
    def __init__(self, data):
        self.data = data
        self.prev = None  # Önceki node
        self.next = None  # Sonraki node

class DoublyLinkedList:
    """Çift Yönlü Bağlı Liste"""
    
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def append(self, data):
        """Sona ekle - O(1)"""
        new_node = DoublyNode(data)
        
        if not self.head:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        
        self.size += 1
        print(f"✅ Sona eklendi: {data}")
    
    def prepend(self, data):
        """Başa ekle - O(1)"""
        new_node = DoublyNode(data)
        
        if not self.head:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        
        self.size += 1
        print(f"✅ Başa eklendi: {data}")
    
    def delete_node(self, node):
        """Belirli node'u sil - O(1)"""
        if not node:
            return
        
        # Önceki node'un next'ini güncelle
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next  # Silinen head ise
        
        # Sonraki node'un prev'ini güncelle
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev  # Silinen tail ise
        
        self.size -= 1
        print(f"🗑️ Silindi: {node.data}")
    
    def pop_back(self):
        """Sondan sil - O(1) 🎉"""
        if not self.tail:
            print("❌ Liste boş!")
            return None
        
        data = self.tail.data
        self.delete_node(self.tail)
        return data
    
    def pop_front(self):
        """Baştan sil - O(1)"""
        if not self.head:
            print("❌ Liste boş!")
            return None
        
        data = self.head.data
        self.delete_node(self.head)
        return data
    
    def display_forward(self):
        """İleri doğru göster"""
        if not self.head:
            print("Liste: [BOŞ]")
            return
        
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        
        print(f"İleri  → : NULL ← {' ⟷ '.join(elements)} → NULL")
    
    def display_backward(self):
        """Geri doğru göster"""
        if not self.tail:
            print("Liste: [BOŞ]")
            return
        
        elements = []
        current = self.tail
        while current:
            elements.append(str(current.data))
            current = current.prev
        
        print(f"Geri  ← : {' ⟷ '.join(elements)}")

# Test
print("↔️ Doubly Linked List Demo\n")
dll = DoublyLinkedList()

dll.append(10)
dll.append(20)
dll.append(30)
dll.display_forward()

print()
dll.prepend(5)
dll.display_forward()
dll.display_backward()

print()
print("🎉 Sondan silme O(1):")
dll.pop_back()
dll.display_forward()

print()
print("🎉 Baştan silme O(1):")
dll.pop_front()
dll.display_forward()

Çıktı bekleniyor...

🎯 Kullanım Alanları

🌐

Tarayıcı Geçmişi

İleri/Geri butonları

🎵

Müzik Çalar

Önceki/Sonraki şarkı

📝

Metin Editörü

Undo/Redo işlemleri

🎮

LRU Cache

En az kullanılan önbellek

📊 Zaman Karmaşıklığı

Operasyon	Singly	Doubly
Başa Ekleme	O(1)	O(1)
Sona Ekleme (tail ile)	O(1)	O(1)
Baştan Silme	O(1)	O(1)
Sondan Silme	O(n) 😢	O(1) 🎉
Verilen Node'u Silme	O(n)	O(1) 🎉
Hafıza (node başına)	data + 1 pointer	data + 2 pointer