Big O Karşılaştırması ve Seçim Kriterleri
| Operasyon | Array | Singly LL | Doubly LL | Python list | deque |
|---|---|---|---|---|---|
| Erişim (index) | O(1) | O(n) | O(n) | O(1) | O(n) |
| Arama (değer) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Başa Ekleme | O(n) | O(1) | O(1) | O(n) | O(1) |
| Sona Ekleme | O(1)* | O(n)/O(1)† | O(1) | O(1)* | O(1) |
| Ortaya Ekleme | O(n) | O(n) | O(n) | O(n) | O(n) |
| Baştan Silme | O(n) | O(1) | O(1) | O(n) | O(1) |
| Sondan Silme | O(1) | O(n) | O(1) | O(1) | O(1) |
| Ortadan Silme | O(n) | O(n) | O(n)‡ | O(n) | O(n) |
* Amortized O(1) - Çoğu durumda O(1), bazen yeniden boyutlandırma gerekir
† Tail pointer varsa O(1)
‡ Node verilmişse O(1), değer ile aranıyorsa O(n)
Toplam: 4 × (size(int) + size(pointer)) = 4 × (4 + 8) = 48 byte (64-bit)
Linked List her eleman için ekstra 8 byte (64-bit sistemde) pointer tutar.
Doubly LL için bu 16 byte olur (prev + next).
Küçük veri tiplerinde (int, char) bu overhead %100-300 ekstra alan demek!
import time
from collections import deque
N = 30000
print(f"🧪 Performans Testi: {N} işlem\n")
print("=" * 55)
# ======= BAŞA EKLEME =======
print("\n📌 BAŞA EKLEME:")
# List
liste = []
start = time.time()
for i in range(N):
liste.insert(0, i)
list_time = time.time() - start
print(f" list.insert(0, x) : {list_time:.4f} sn")
# Deque (LL benzeri)
d = deque()
start = time.time()
for i in range(N):
d.appendleft(i)
deque_time = time.time() - start
print(f" deque.appendleft(x) : {deque_time:.4f} sn")
print(f" 📊 Deque {list_time/deque_time:.0f}x hızlı!")
# ======= BAŞTAN SİLME =======
print("\n📌 BAŞTAN SİLME:")
liste = list(range(N))
start = time.time()
while liste:
liste.pop(0)
list_time = time.time() - start
print(f" list.pop(0) : {list_time:.4f} sn")
d = deque(range(N))
start = time.time()
while d:
d.popleft()
deque_time = time.time() - start
print(f" deque.popleft() : {deque_time:.4f} sn")
print(f" 📊 Deque {list_time/deque_time:.0f}x hızlı!")
# ======= RANDOM ACCESS =======
print("\n📌 RANDOM ACCESS (index erişimi):")
liste = list(range(N))
d = deque(range(N))
# List
start = time.time()
for i in range(N):
_ = liste[i]
list_time = time.time() - start
print(f" list[i] : {list_time:.4f} sn")
# Deque
start = time.time()
for i in range(N):
_ = d[i]
deque_time = time.time() - start
print(f" deque[i] : {deque_time:.4f} sn")
print(f" 📊 List {deque_time/list_time:.1f}x hızlı!")
print("\n" + "=" * 55)
print("\n📋 SONUÇ:")
print(" • Başa ekleme/silme → deque (Linked List)")
print(" • Index erişimi → list (Array)")
print(" • Genel kullanım → list genellikle yeterli")| Özellik | Array | Linked List |
| Hafıza Yerleşimi | Bitişik (contiguous) | Dağınık (scattered) |
| Cache Performansı | ✅ İyi (locality) | ❌ Kötü (random) |
| Boyut Değişikliği | Yeniden tahsis | ✅ Kolay |
| Hafıza Overhead | ✅ Düşük | Pointer başına 8 byte |
| Pratik Kullanım | Python list |
Python deque |