Tek Yönlü Bağlı Liste Implementasyonu
Listeye yeni bir eleman eklemek istiyoruz ve bu elemanı listenin en başına koymak istiyoruz. Aşağıdaki örnekte "X" değerini içeren yeni bir node oluşturup başa ekliyoruz.
Başlangıç durumu: A → B → NULL şeklinde 2 elemanlı bir listemiz var.
Sonuç: X artık listenin ilk elemanı, HEAD X'i gösteriyor.
new_node.next = head → Yeni node'un next pointer'ını mevcut head'e (A'ya) bağlahead = new_node → HEAD pointer'ını yeni node'a (X'e) güncelle📌 Önemli: Sıralama kritik! Önce yeni node'u bağlamalı, sonra HEAD'i güncellemeliyiz. Aksi halde eski listenin referansını kaybederiz.
Listeye yeni bir eleman eklemek istiyoruz ve bu elemanı listenin en sonuna koymak istiyoruz. Aşağıdaki örnekte "X" değerini içeren yeni bir node oluşturup sona ekliyoruz.
Başlangıç durumu: A → B → C → NULL şeklinde 3 elemanlı bir listemiz var. Önce son node'u (C) bulmalıyız.
Sonuç: X artık listenin son elemanı, C'nin next pointer'ı X'i gösteriyor.
current = head → Baştan başla (A)while current.next != null → next'i null olmayanları gez (A→B→C)current.next = new_node → Son node'un (C) next'ini yeni node'a (X) bağla📌 İpucu: Tail pointer tutarak bu işlemi O(1) yapabilirsiniz! (Aşağıda optimizasyon bölümüne bakın)
Listeden bir eleman silmek istiyoruz. Aşağıdaki örnekte "B" değerini içeren node'u siliyoruz. Silme işleminin zorluğu: silinecek node'un öncesindeki node'u bulmamız gerekiyor.
Başlangıç durumu: A → B → C → NULL şeklinde 3 elemanlı listemiz var. "B" node'unu silmek istiyoruz.
Sonuç: B listeden çıkarıldı, A artık doğrudan C'ye bağlı.
current = head → Baştan başla (A)while current.next.data != "B" → B'nin öncesini aracurrent.next = current.next.next → A'nın next'ini B'nin next'ine (C'ye) bağla📌 Kritik nokta: Tek yönlü listede geri gidemeyiz! Bu yüzden silinecek node'u değil, onun öncesindeki node'u bulmalıyız. B'yi bulsak bile A'ya ulaşamayız.
⚠️ Özel durum: Eğer silinecek node HEAD ise (ilk eleman), sadece head = head.next yapmak yeterli — bu O(1)!
Listede belirli bir değeri aramak istiyoruz. Aşağıdaki örnekte "C" değerini arıyoruz. Linked list'te rastgele erişim (random access) yoktur, bu yüzden baştan başlayıp sırayla kontrol etmeliyiz.
Arama süreci: A → B → C → D → NULL listesinde "C" değerini arıyoruz.
current = head, index = 0 → Baştan başlawhile current != null → Liste bitene kadar devam etif current.data == aranan → Eşleşme varsa index döndürcurrent = current.next, index++ → Sonraki node'a geç📌 En kötü durum: Aranan değer listenin sonundaysa veya listede yoksa, tüm n elemanı gezmemiz gerekir.
📌 Array ile karşılaştırma: Array'de index ile erişim O(1)'dir (arr[2]), ama linked list'te 2. elemana ulaşmak için baştan 2 adım atmamız gerekir!
class Node:
"""Tek yönlü bağlı liste düğümü"""
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
"""Tek Yönlü Bağlı Liste"""
def __init__(self):
self.head = None
self.size = 0
def prepend(self, data):
"""Başa ekle - O(1)"""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
self.size += 1
print(f"✅ Başa eklendi: {data}")
def append(self, data):
"""Sona ekle - O(n)"""
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next: # Son node'u bul
current = current.next
current.next = new_node
self.size += 1
print(f"✅ Sona eklendi: {data}")
def delete(self, data):
"""Belirli değeri sil - O(n)"""
if not self.head:
print("❌ Liste boş!")
return
# Silinecek head ise
if self.head.data == data:
self.head = self.head.next
self.size -= 1
print(f"🗑️ Silindi: {data}")
return
# Ara ve sil
current = self.head
while current.next:
if current.next.data == data:
current.next = current.next.next
self.size -= 1
print(f"🗑️ Silindi: {data}")
return
current = current.next
print(f"❌ Bulunamadı: {data}")
def search(self, data):
"""Değeri ara - O(n)"""
current = self.head
index = 0
while current:
if current.data == data:
print(f"🔍 Bulundu: {data} (index: {index})")
return index
current = current.next
index += 1
print(f"🔍 Bulunamadı: {data}")
return -1
def display(self):
"""Listeyi 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"Liste: HEAD → {' → '.join(elements)} → NULL")
print(f"Boyut: {self.size}")
# Test
print("🔗 Singly Linked List Demo\n")
liste = SinglyLinkedList()
liste.append(10)
liste.append(20)
liste.append(30)
liste.display()
print()
liste.prepend(5)
liste.display()
print()
liste.delete(20)
liste.display()
print()
liste.search(30)
liste.search(100)Sona ekleme işlemini O(1) yapmak için tail pointer kullanabiliriz:
class Node:
"""Tek yönlü bağlı liste düğümü"""
def __init__(self, data):
self.data = data
self.next = None
class OptimizedLinkedList:
"""Tail pointer ile optimize edilmiş liste"""
def __init__(self):
self.head = None
self.tail = None # Son node'u takip et!
self.size = 0
def append(self, data):
"""Sona ekle - Artık O(1)!"""
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node # Direkt tail'e bağla
self.tail = new_node # Tail'i güncelle
self.size += 1
def prepend(self, data):
"""Başa ekle - O(1)"""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
if not self.tail: # İlk elemansa tail'i de ayarla
self.tail = new_node
self.size += 1
def display(self):
elements = []
current = self.head
while current:
elements.append(str(current.data))
current = current.next
print(f"HEAD → {' → '.join(elements)} → NULL")
print(f"(head={self.head.data if self.head else 'None'}, tail={self.tail.data if self.tail else 'None'})")
# Test
print("⚡ Optimized Linked List (Tail Pointer)\n")
opt_list = OptimizedLinkedList()
import time
N = 10000
# Normal append (simüle)
start = time.time()
for i in range(N):
opt_list.append(i)
print(f"✅ {N} eleman O(1) append: {time.time()-start:.4f} sn")
print(f"Son eleman: {opt_list.tail.data}")⚠️ Sondan silme her zaman O(n) çünkü önceki node'u bulmak gerekir (tek yönlü!)