📊 4.7: Linked List Analizi

🤔 Bu Sayfa Neden Önemli?

Şimdiye kadar Array ve Linked List yapılarını öğrendik. Peki hangisini ne zaman kullanmalıyız? Bu sorunun cevabı, her iki yapının performans özelliklerini anlamaktan geçiyor.

Programlamada "performans" derken genellikle iki şeyi kastediyoruz: işlemlerin ne kadar zaman aldığı ve ne kadar hafıza kullandığı. Big O notasyonu, bu özellikleri veri boyutu büyüdükçe nasıl değiştiğini anlamamıza yardımcı olur.

Aşağıdaki tabloda O(1) "sabit süre" demek - veri ne kadar büyürse büyüsün işlem aynı sürede biter. O(n) ise "lineer süre" demek - veri 10 kat büyürse işlem de kabaca 10 kat uzun sürer. Tabii ki O(1) daha iyidir!

⏱️ Zaman Karmaşıklığı Karşılaştırması

Aşağıdaki tablo, farklı veri yapılarında temel işlemlerin ne kadar sürdüğünü gösteriyor. Yeşil renkteki O(1) değerleri hızlı işlemleri, kırmızı renkteki O(n) değerleri ise yavaş işlemleri temsil ediyor.

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

💾 Alan Karmaşıklığı (Hafıza Kullanımı)

Bir veri yapısının ne kadar hafıza kullandığı, özellikle büyük veri setleriyle çalışırken çok önemlidir. Array ve Linked List bu konuda çok farklı davranır.

Array elemanlarını hafızada yan yana (bitişik) saklar. Bu sayede ekstra alan kullanmaz - sadece verinin kendisi için yer ayrılır. Ancak bir dezavantajı var: Array'i büyütmek istediğimizde, yeterli büyüklükte yeni bir bitişik alan bulup tüm veriyi oraya taşımamız gerekebilir.

Linked List ise her eleman için veri + pointer (işaretçi) saklar. Bu pointer, sonraki (veya önceki) elemanın hafızadaki adresini tutar. 64-bit bir sistemde her pointer 8 byte yer kaplar. Yani bir integer (4 byte) saklarken aslında 4 + 8 = 12 byte kullanmış oluruz. Bu %200 overhead demek!

🎯 Ne Zaman Hangisini Kullanmalı?

Teorik Big O değerleri önemli, ama gerçek hayatta seçim yaparken duruma göre düşünmek gerekir. Aşağıda her iki yapının güçlü olduğu senaryoları açıklıyoruz.

🧪 Pratik Performans Testi

Teorik Big O değerleri güzel, ama gerçekte ne kadar fark yaratıyor? Aşağıdaki kod, Python'da list (array tabanlı) ve deque (linked list tabanlı) arasındaki performans farkını ölçüyor. Kodu çalıştırarak sonuçları kendiniz görün!

Özellikle "başa ekleme" ve "baştan silme" işlemlerinde deque'in ne kadar hızlı olduğuna, ama "index erişimi"nde list'in nasıl ezdiğine dikkat edin.

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

📚 Özet ve Son Sözler

Bu sayfada Array ve Linked List veri yapılarının performans özelliklerini karşılaştırdık. Aşağıdaki tablo, öğrendiklerimizi özetliyor.