Pratik Kullanım ve Performans Karşılaştırması
Python'da yerleşik bir LinkedList sınıfı yok. Bu durum yeni başlayanları şaşırtabilir çünkü linked list veri yapıları derslerinde en çok öğretilen konulardan biridir. Peki Python neden dahili bir LinkedList sağlamıyor?
Bunun birkaç önemli sebebi var:
list çok yetenekli: Python'un dahili list tipi aslında bir dinamik dizi (dynamic array) yapısıdır. Dinamik diziler bellekte ardışık (contiguous) şekilde tutulur ve sondan ekleme/çıkarma işlemleri için O(1) performans sağlar. Çoğu günlük programlama ihtiyacını karşılar.collections.deque zaten var: Python standart kütüphanesi deque (double-ended queue - çift uçlu kuyruk) sağlar. deque aslında içeride doubly linked list mantığıyla çalışır ve hem baştan hem sondan O(1) ekleme/çıkarma yapabilir.list ve deque kombinasyonu linked list'in yapabileceği hemen her şeyi yapabilir. Bu yüzden ayrı bir LinkedList sınıfına gerek duyulmamış.💡 Önemli Not: Linked list'i öğrenmek algoritma ve veri yapıları bilgisi için çok önemlidir. Ancak Python'da "üretim" (production) kodu yazarken genellikle list veya deque kullanmak daha mantıklıdır.
deque ("deck" olarak okunur, double-ended queue'nin kısaltması), Python'un collections modülünde bulunan güçlü bir veri yapısıdır. İsminden de anlaşılacağı gibi "çift uçlu kuyruk" demektir - yani hem başından hem sonundan eleman ekleyip çıkarabilirsiniz.
Neden bu kadar önemli? Normal Python list'inde başa eleman eklemek (insert(0, x)) veya baştan eleman silmek (pop(0)) O(n) zaman alır. Çünkü tüm elemanları bir sağa kaydırmak gerekir. Ancak deque içeride doubly linked list benzeri bir yapı kullandığı için bu işlemler O(1) - yani sabit zamanda gerçekleşir!
Bu özellik deque'i kuyruk (queue) ve yığın (stack) implementasyonları için ideal kılar. Ayrıca maxlen parametresiyle sabit boyutlu dairesel tampon (circular buffer) olarak da kullanılabilir.
from collections import deque
print("🔄 collections.deque Kullanımı\n")
# Oluşturma
d = deque(['A', 'B', 'C'])
print(f"Başlangıç: {list(d)}")
# Başa ve sona ekleme - O(1)
d.appendleft('X') # Başa
d.append('Y') # Sona
print(f"X başa, Y sona: {list(d)}")
# Baştan ve sondan silme - O(1)
d.popleft() # Baştan
d.pop() # Sondan
print(f"Baş ve son silindi: {list(d)}")
# Rotate - Circular gibi döndürme!
d = deque([1, 2, 3, 4, 5])
print(f"\nRotate öncesi: {list(d)}")
d.rotate(2) # Sağa 2 döndür
print(f"rotate(2): {list(d)}")
d.rotate(-3) # Sola 3 döndür
print(f"rotate(-3): {list(d)}")
# Maxlen - Sabit boyutlu (LRU Cache gibi!)
print(f"\n📦 Sabit boyutlu deque (maxlen=3):")
limited = deque(maxlen=3)
for i in range(5):
limited.append(i)
print(f" append({i}): {list(limited)}")Şimdi list ve deque arasındaki performans farkını somut olarak görelim. Aşağıdaki kod, her iki veri yapısında da baştan ekleme ve baştan silme işlemlerini karşılaştırır.
Neden baştan işlemler önemli?
list'inde başa ekleme: list.insert(0, x) kullandığınızda, mevcut tüm elemanlar bir sağa kaydırılmalıdır. 50.000 elemanlı bir listede her ekleme 50.000 eleman kaydırma demek! Bu yüzden O(n) karmaşıklığa sahip.deque'de başa ekleme: deque.appendleft(x) sadece yeni bir düğüm oluşturup başa bağlar. Kaydırma yok! Bu yüzden O(1) - sabit zaman.Aşağıdaki benchmark kodu bu farkı ölçer. Sonuç genellikle 100x-500x hız farkı gösterir! Bu fark eleman sayısı arttıkça daha da büyür.
import time
from collections import deque
N = 50000
print(f"🧪 Performans Testi: {N} işlem\n")
print("=" * 50)
# 1. LIST - Başa ekleme
liste = []
start = time.time()
for i in range(N):
liste.insert(0, i) # O(n) - her seferinde kaydırma!
list_insert_time = time.time() - start
print(f"📋 list.insert(0, x) : {list_insert_time:.4f} sn")
# 2. DEQUE - Başa ekleme
kuyruk = deque()
start = time.time()
for i in range(N):
kuyruk.appendleft(i) # O(1) - sabit zaman!
deque_append_time = time.time() - start
print(f"🔄 deque.appendleft() : {deque_append_time:.4f} sn")
print(f"\n💡 Deque {list_insert_time/deque_append_time:.0f}x daha hızlı!")
print("\n" + "=" * 50)
# 3. LIST - Baştan silme
liste = list(range(N))
start = time.time()
while liste:
liste.pop(0) # O(n)
list_pop_time = time.time() - start
print(f"📋 list.pop(0) : {list_pop_time:.4f} sn")
# 4. DEQUE - Baştan silme
kuyruk = deque(range(N))
start = time.time()
while kuyruk:
kuyruk.popleft() # O(1)
deque_pop_time = time.time() - start
print(f"🔄 deque.popleft() : {deque_pop_time:.4f} sn")
print(f"\n💡 Deque {list_pop_time/deque_pop_time:.0f}x daha hızlı!")
print("\n" + "=" * 50)
print("\n📊 SONUÇ:")
print(" - Başa ekleme/silme → deque kullan!")
print(" - Random access (index) → list kullan!")
print(" - Sona ekleme/silme → ikisi de O(1)")Deque'i sarmalayarak LinkedList benzeri API oluşturalım:
from collections import deque
class LinkedList:
"""deque tabanlı LinkedList wrapper"""
def __init__(self, iterable=None):
self._data = deque(iterable) if iterable else deque()
def prepend(self, value):
"""Başa ekle - O(1)"""
self._data.appendleft(value)
def append(self, value):
"""Sona ekle - O(1)"""
self._data.append(value)
def pop_first(self):
"""Baştan sil - O(1)"""
if not self._data:
raise IndexError("Liste boş!")
return self._data.popleft()
def pop_last(self):
"""Sondan sil - O(1)"""
if not self._data:
raise IndexError("Liste boş!")
return self._data.pop()
@property
def head(self):
"""İlk eleman"""
return self._data[0] if self._data else None
@property
def tail(self):
"""Son eleman"""
return self._data[-1] if self._data else None
def __len__(self):
return len(self._data)
def __iter__(self):
return iter(self._data)
def __repr__(self):
return f"LinkedList({list(self._data)})"
# Test
print("🔗 LinkedList Wrapper Demo\n")
ll = LinkedList([1, 2, 3])
print(f"Başlangıç: {ll}")
ll.prepend(0)
ll.append(4)
print(f"0 başa, 4 sona: {ll}")
print(f"Head: {ll.head}, Tail: {ll.tail}")
print(f"pop_first(): {ll.pop_first()}")
print(f"pop_last(): {ll.pop_last()}")
print(f"Sonuç: {ll}")
print(f"\nİterasyon:")
for item in ll:
print(f" → {item}")