T: tema · Z: kodu büyüt · S: konuşmacı notları · F: tam ekran · Esc: genel bakış · ⌂ ders haritası
OYUNLARDA YAPAY ZEKÂ · VERİ YAPILARI
Bağlı Listeler
Linked lists — dizi mi, bağlı liste mi? Bellekte gerçekte neler oluyor?
PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

  1. Dizi: bellekte tek parça — güçlü ve zayıf yanları array
  2. Bağlı liste: düğümler ve oklar linked list
  3. İşlemler: başa/sona ekleme, silme, arama, tersine çevirme
  4. Dinamik dizi: Python list, C# List<T> aslında ne? resizing array
  5. Büyük karşılaştırma: işlemler, bellek, önbellek, canlı ölçüm
  6. Oyunlarda: yılan oyunu, Uno sırası, mermi havuzu, düşman listesi
  7. ⚙️ Perde arkası: C’de işaretçiler, bellek sızıntısı, çöp toplayıcı
🎮 Bu dersin sonunda…

…“bu oyunda düşmanları hangi yapıda tutmalıyım?” sorusuna gerekçeli bir cevap verebileceksiniz — ve cevabın çoğu zaman sandığınız gibi olmadığını göreceksiniz. 😉

🤔 ISINMA: DOLAPLAR ve HAZİNE AVI

🗄️ Spor salonu dolapları

Yan yana numaralı 100 dolap. 37 numaralı dolaba nasıl gidersiniz?

🗺️ Hazine avı

Her ipucu kâğıdı bir sonrakinin yerini söylüyor. 37. ipucuna nasıl ulaşırsınız?

Dolap: doğrudan gidersiniz (numarası belli) → dizi. Hazine avı: 1’den başlayıp 36 ipucunu takip edersiniz → bağlı liste.

Ama araya yeni bir ipucu eklemek için hazine avında sadece bir kâğıdı değiştirmek yeter; dolaplarda herkesi bir dolap kaydırmanız gerekir! 🤔

Oyun programcısı neden umursamalı?

🐍
Yılan oyunuHer adımda başa ekle, sondan sil
🃏
Tur sırasıUno: “yön değiştir”, “atla”, oyuncu elendi
🔫
Mermi havuzuSaniyede yüzlerce mermi — new olmadan!
👾
Düşman listesiÖlen düşmanı listeden en hızlı nasıl çıkarırım?
⚡
PerformansAynı algoritma, farklı veri yapısı: 10 kat hız farkı
🧱
Temel taşYığın, kuyruk, ağaç, graf… hepsi bu iki fikirden doğar

Mini sözlük (1/2)

arraydiziBellekte yan yana duran, indeksle erişilen elemanlar
contiguousbitişikBellekte boşluksuz, ardışık
random accessrastgele (doğrudan) erişima[i]’ye tek adımda ulaşmak
nodedüğümBağlı listenin bir halkası: değer + bağlantı
link / nextbağlantı / sonrakiBir sonraki düğümün referansı (adresi)
head / tailbaş / sonListenin ilk / son düğümünü gösteren değişken
nullboş referans“Hiçbir düğümü göstermiyor” — listenin sonu

Mini sözlük (2/2)

doubly linked listçift yönlü bağlı listeHer düğümde hem next hem prev var
circular listdairesel listeSonun next’i başa döner
dynamic (resizing) arraydinamik diziDolunca kendini büyüten dizi (list, List<T>)
capacitykapasiteAyrılmış yer sayısı (kullanılan eleman sayısından büyük olabilir)
amortizedamortize (uzun vadeli ortalama)Ara sıra pahalı, ortalamada ucuz işlem
cache localityönbellek yerelliğiBirlikte kullanılan verinin bellekte yakın durması
object pool / free listnesne havuzu / boş listeNesneleri silmek yerine geri dönüştürmek
LEVEL 0
Dizi
array — bellekte tek parça, numaralı dolaplar gibi
  • dizi: bellekte tek parça
  • bağlı liste: düğümler ve oklar
  • işlemler
  • dinamik dizi
  • büyük karşılaştırma
  • varyasyonlar ve oyunlar
  • perde arkası

Dizi bellekte nasıl durur?

Dizi = bellekte yan yana duran, aynı boyutta kutular. a[i]’nin adresi tek bir hesapla bulunur:

💪 Süper gücü: rastgele erişim random accessa[0] ile a[999999]’a ulaşmak aynı sürer: bir çarpma + bir toplama. → İkili arama bu yüzden dizide çalışır!
⚙️ Bonus: önbellek dostuİşlemci bellekten 64 baytlık parçalar getirir. a[i]’yi okuyunca komşuları da “bedavaya” gelir.

Dizinin bedeli: araya ekleme ve silme

😓 Zayıf yan 1: kaydırmaAraya ekleme/silme, sağdaki her elemanı bir kaydırır. Başa eklemek = N taşıma.
😓 Zayıf yan 2: sabit boyutnew int[12] diye ayrılan dizi büyüyemez. 13. eleman için yeni, daha büyük bir dizi ayırıp hepsini kopyalamak gerekir.

🔗 Başka gözle: etkileşimli anlatımlar ve yazılar

Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.

Quiz 1 · dizi
1000 elemanlı bir dizinin (yeterli kapasitesi var) en başına yeni bir eleman eklemek kaç taşıma gerektirir?
Yeni elemana yer açmak için mevcut 1000 elemanın hepsi bir sağa kaymalı. Sona eklemek ise 0 taşıma. Dizide “nereye” eklediğiniz çok önemli.
LEVEL 1
Bağlı Liste
linked list — her düğüm bir sonrakinin yerini bilir (hazine avı)
  • dizi: bellekte tek parça
  • bağlı liste: düğümler ve oklar
  • işlemler
  • dinamik dizi
  • büyük karşılaştırma
  • varyasyonlar ve oyunlar
  • perde arkası

🎒 Ön bilgi: sınıf ve nesne class & object

  • Sınıf class = kalıp: “Her düğümün bir değeri ve bir sonraki bağlantısı olur.”
  • Nesne object = kalıptan üretilmiş somut düğüm
  • Alan field = nesnenin bilgisi: key, next
  • Yapıcı constructor = nesne üretilirken çalışan fonksiyon (__init__ / constructor)
  • self / this = “bu nesnenin”
  • Nokta = “-nin”: n.key → “n’nin değeri”

🎒 Ön bilgi: referans ve null reference · null

Bir değişken nesnenin kendisini değil, nerede durduğunu (adresini) tutar: bir ok gibi düşünün.

  • b = a yeni düğüm üretmez: iki ok aynı düğümü gösterir.
  • a.next = b → a’nın içine b’nin adresi yazıldı: işte “bağlantı”!
  • None / null = ok hiçbir şeyi göstermiyor → listenin sonu.
  • null.key okumaya çalışmak → hata (NullReferenceException — Unity’nin en meşhur hatası 😅)

Bağlı liste: tanım

  • Her düğüm: bir değer + bir sonraki düğümün referansı (next)
  • head değişkeni ilk düğümü gösterir
  • Son düğümün next’i null
  • Boş liste: head = null

Düğümler bellekte herhangi bir yerde olabilir; sırayı adresler değil oklar belirler.

📜 1955–56Bağlı listeler, ilk yapay zekâ programlarından biri olan Logic Theorist için (Newell, Shaw, Simon) icat edildi. Yani bağlı liste ve yapay zekâ en başından beri kardeş! 🤖
head to be or null key │ next

Elle bir liste kuralım: “kılıç → kalkan → iksir”

Örnek: bir envanterde art arda duran üç eşya.

Listeyi gezmek traversal: “oku takip et”

Dizideki for (i = 0; i < N; i++) döngüsünün bağlı liste hali:

  1. x = head — baştan başla
  2. x null değilken: düğümü kullan
  3. x = x.next — bir sonrakine geç
🎒 x = x.next ne demek?“x şu an bir düğümü gösteriyor. O düğümün sonraki okunun gösterdiği yeri, x’in yeni değeri yap.” x bir “parmak” gibi listede ilerler; düğümlerin kendisi yerinden kıpırdamaz.

Arama animasyonu

Dizide ikili arama yapabiliyorduk; bağlı listede yapamayız: ortadaki düğüme ulaşmak için zaten yarısını yürümek gerekir. Arama hep O(N).

LEVEL 2
İşlemler
başa ekle · baştan sil · sona ekle · sil · tersine çevir
  • dizi: bellekte tek parça
  • bağlı liste: düğümler ve oklar
  • işlemler
  • dinamik dizi
  • büyük karşılaştırma
  • varyasyonlar ve oyunlar
  • perde arkası

Başa ekleme: 3 adım, liste ne kadar uzun olursa olsun

Başa ekle / baştan sil — kod

🎒 Fonksiyon head’i değiştirdiği için yeni başı döndürüyoruz ve çağıran head = push_front(head, …) diye kaydediyor. (Gerçek kodda bunu bir LinkedList sınıfının içine saklarız; yığınlar dersinde göreceğiz.) C#’taki ref: “değişkenin kopyasını değil, kendisini ver.”

Sona ekleme — tail olmadan: yürümek zorundayız

Sona ekleme — tail ile: O(1)

Sona ekle (tail ile) — kod

🎒 Burada düğümleri ve head/tail’i bir sınıfın içine sakladık: kullanan kişi okları hiç görmez, sadece push_back("x") der. Buna kapsülleme encapsulation denir.

Ortadan silme: “üzerinden atla”

👍 Kaydırma yokSadece prev.next = x.next: tek bir bağlantı değişir.
👎 Ama önce bulmak lazımSilinecek düğümü ve bir öncekini bulmak için baştan yürümek gerekir: O(N). Elimizde düğümün kendisi varsa (ve çift yönlü listeyse) O(1).

Tersine çevirme: klasik bir bulmaca 🔄

Tersine çevirme — kod

🎬 Ara: bağlı liste, tahtada

Linked Lists
Computerphile · 10 dk 11 sn · YouTube’da aç

Düğüm, işaretçi ve “bir sonraki”nin bellekte gerçekten nasıl durduğu; dizi ile bağlı listenin farkı kalemle çizilerek anlatılıyor.

🤔 İzlerkenVideoda listenin ortasına ekleme kaç işaretçi değişikliği gerektiriyor? Dizide aynı iş için kaç eleman kaydırılır? Önbellek açısından hangisi neden daha yavaş?
Quiz 2 · işlemler
Tersine çevirme kodunda nxt = cur.next satırını unutup doğrudan cur.next = prev yazarsak ne olur?
cur.next, listenin geri kalanına giden tek yol. Önce onu bir değişkende saklamazsak üzerine prev yazdığımız an devamı kaybolur (ve çöp toplayıcı onları siler). Bağlı listelerde altın kural: bir oku değiştirmeden önce, gösterdiği yeri kaydet.

🧪 Kod laboratuvarı: uzunluk (ısınma)

Dene:
  1. Çalıştır: tüm testler geçiyor mu?
  2. 8. satırı (x = x.next) sil. Ne oldu, neden?
  3. Fonksiyonu özyinelemeli yaz: boş listenin uzunluğu 0; değilse 1 + kalanın uzunluğu.

🧪 Kod laboratuvarı: tersine çevir

Önce animasyonu tekrar izle, sonra kendin yaz. Takılırsan önceki slayttaki kodu ezberden değil, adımları düşünerek yazmayı dene. Bonus: özyinelemeli sürüm.

🐍 Kod laboratuvarı — Python: sona ekle

Bu kodda bir hata var: çalıştır, hangi testte patlıyor? Düzelt. (İpucu: boş liste.)
LEVEL 3
Dinamik Dizi
resizing array — Python list, C# List<T>, JS Array aslında ne?
  • dizi: bellekte tek parça
  • bağlı liste: düğümler ve oklar
  • işlemler
  • dinamik dizi
  • büyük karşılaştırma
  • varyasyonlar ve oyunlar
  • perde arkası

Sürpriz: Python’un list’i bağlı liste DEĞİL! 😮

Python list, C# List<T>, JavaScript Array ve C++ vector: hepsi içeride bir dizi kullanır.

  • Eleman sayısı count: kullandığınız kutu sayısı
  • Kapasite capacity: ayrılmış kutu sayısı (genelde daha fazla)
  • Dolunca: daha büyük yeni bir dizi ayır, eskileri kopyala, eskiyi bırak

Bu yüzden a[i] hızlı (dizi!), sona ekleme genelde hızlı, başa ekleme (insert(0, x), unshift) yavaş.

⚠️ İsim tuzağıC#’ta List<T> = dinamik dizi. Gerçek bağlı liste ise LinkedList<T>. Java’da da ArrayList ve LinkedList ayrı. Python’da yerleşik bağlı liste yok (collections.deque bloklardan oluşan bir liste).

Dolunca ne kadar büyütmeli? 📐

Neden “iki katı”? Amortize maliyet amortized cost

Kapasite 1, 2, 4, 8, …, N olurken yapılan toplam kopya:

\( 1 + 2 + 4 + \dots + \frac{N}{2} = N - 1 \; < \; N \)

N ekleme için: N yazma + < N kopya → toplam < 2N → eleman başına < 2 iş (kitapta ~3 dizi erişimi olarak sayılır).

Bazı eklemeler pahalı (kopyalama anı), ama uzun vadede ortalama sabit: buna amortize O(1) denir.

ÖnermeKapasiteyi her dolduğunda iki katına çıkaran dinamik dizide, boş diziden başlayan N push işlemi toplam ~N’e orantılı zaman alır.

🧠 Benzetme: kira öder gibi değil, ev alır gibi. Arada bir büyük ödeme (taşınma), ama yıllara bölünce aylık maliyet düşük.

Quiz 3 · dinamik dizi
Dinamik dizi, eleman sayısı kapasitenin yarısına düşünce kapasiteyi yarıya indirirse ne olabilir?
Kapasite 8, eleman 8 → push: 16’ya büyü (kopya). Pop: eleman 8 = 16’nın yarısı → 8’e küçül (kopya). Push → büyü… Her işlem N kopya! Buna “çırpınma” thrashing denir. Çözüm: kapasitenin dörtte birine düşünce yarıya indir.

Kendi dinamik dizimiz

🎒 C#’taki a[n++] = x: önce a[n] = x, sonra n bir artar (modern kısa yazım). --n: önce azalt, sonra kullan. Python’da “referansı bırak” satırı önemli: yoksa silinmiş eleman bellekte kalır (bekleyen referans loitering).

🎮 Unity ipuçları: List<T> ile çöpsüz çalışmak

🎒 new List<Enemy>(256): “baştan 256 kişilik yer ayır” → ilk 256 eklemede hiç büyütme/kopya olmaz. readonly: değişken bir kez atanır (liste aynı kalır, içeriği değişebilir).

LEVEL 4
Büyük Karşılaştırma
işlemler · bellek · önbellek · canlı ölçüm
  • dizi: bellekte tek parça
  • bağlı liste: düğümler ve oklar
  • işlemler
  • dinamik dizi
  • büyük karşılaştırma
  • varyasyonlar ve oyunlar
  • perde arkası

İşlem işlem karşılaştırma 📋

işlemsabit dizidinamik dizitek yönlü liste
(head + tail)
çift yönlü liste
a[i]’ye eriş11ii
arama (sırasız)NNNN
arama (sıralı)lg Nlg NNN
başa ekle / baştan silNN11
sona ekle— (dolu)1*11
sondan sil11*N1
düğümü elindeyken araya ekle/silNN1 (sonrasına)1
eleman başına belleken azaz (+ boş kapasite)çok (+1 ref)daha çok (+2 ref)

* amortize (ortalama). Büyük-O tablosu hikâyenin sadece yarısı → sonraki slaytlar: bellek ve önbellek.

⚙️ 1 milyon tamsayı ne kadar yer kaplar?

yapı (C#, 64-bit)eleman başına1 milyon eleman
int[]4 bayt~4 MB
List<int>4–8 bayt~4–8 MB
LinkedList<int>~48 bayt~48 MB

Yaklaşık değerler. Her düğüm ayrı bir nesne: nesne başlığı (~16 bayt) + değer + next/prev referansları (8’er bayt) + listenin kendisine referans + hizalama boşlukları.

⚙️ Neden önemli?
  • Daha çok bellek = önbelleğe daha az eleman sığar
  • 1 milyon ayrı nesne = çöp toplayıcı için 1 milyon ayrı iş
  • Mobil oyunlarda bellek sınırı gerçek bir sorun

⚙️ Önbellek simülasyonu: diziyi ve listeyi gezmek

Her hücre bir bellek adresi; her satır (8 hücre) bir önbellek satırı. Önbellek sadece 3 satır tutabiliyor. Dizide elemanlar yan yana; listede her düğüm (değer + sonraki adres) belleğe dağılmış.

🧪 Canlı ölçüm: bu bilgisayarda kim kazanır?

Tahmin edin, sonra ölçünBaşa ekleme: liste kazanmalı (dizi her seferinde kaydırıyor). Sona ekleme ve gezme: dizi kazanmalı (önbellek!). Sonuçlar tahminle uyuşuyor mu?
🔬 Bilimsel yöntemAlgoritma analizi dersindeki gibi: hipotez → deney → sonuç. N’i iki katına çıkarınca süreler nasıl değişiyor?

📜 C++’ın yaratıcısı: “Bağlı listelerden kaçının”

2012’de Bjarne Stroustrup bir konferansta şu deneyi gösterdi: Sıralı bir diziye rastgele sayılar ekle (doğru yere), sonra rastgele konumlardan sil.

Teoride bağlı liste kazanmalı: ekleme/silme O(1)! Ama… doğru yeri bulmak zaten sıralı arama gerektiriyor (O(N)), ve listede bu arama önbellek ıskalarıyla dolu.

Sonuç: dizi (vector) her boyutta kat kat hızlı çıktı.

💡 Stroustrup’un dersi
  • Gereksiz veri saklama
  • Veriyi sıkı tut
  • Belleğe tahmin edilebilir şekilde eriş

Kendisi de “bu bağlı listeler kötü demek değil, ölçmeden karar vermeyin demek” diye ekliyor.

Peki ne zaman hangisi? 🧭

✅ Varsayılan: dinamik dizi
  • Çoğunlukla gezip okuyorsanız
  • a[i] ile erişiyorsanız, sıralayıp ikili arama yapıyorsanız
  • Ekleme/silme çoğunlukla sonda ise
  • Sıra önemli değilse silme için “swap & pop” (Level 5)
✅ Bağlı liste mantıklı olduğunda
  • Düğümün kendisi elinizdeyken sık sık araya ekleme/silme (ör. LRU önbelleği)
  • Elemanların bellekte yer değiştirmemesi gerekiyorsa (adresleri sabit kalmalı)
  • Başa ekleme/baştan silme ağırlıklı (yığın, kuyruk — sonraki ders)
  • Çok büyük nesneleri kopyalamadan taşımak

Altın kural: Önce basit olanı (dinamik dizi) kullan. Yavaşsa, ölç. Sonra değiştir.

Quiz 4 · karşılaştırma
Bir 2D nişancı oyununda ekranda ~500 düşman var. Her karede hepsi güncelleniyor (gezme), ara sıra biri ölüyor (sıra önemsiz), ara sıra yenisi ekleniyor. Hangi yapı?
İşin çoğu her karede gezmek → dizi önbellek sayesinde kazanır. Silme: sıra önemli değilse ölen düşmanın yerine sondakini koyup diziyi bir kısaltmak (swap & pop) O(1). Bağlı listenin silme avantajı burada gerekmiyor ama gezme bedelini her karede ödersiniz.
LEVEL 5
Varyasyonlar ve Oyunlar
çift yönlü · dairesel · yılan · Uno · mermi havuzu
  • dizi: bellekte tek parça
  • bağlı liste: düğümler ve oklar
  • işlemler
  • dinamik dizi
  • büyük karşılaştırma
  • varyasyonlar ve oyunlar
  • perde arkası

Çift yönlü ve dairesel listeler doubly linked · circular

  • Çift yönlü: her düğümde prev de var → geriye gidebilir, elindeki düğümü O(1)’de silebilirsin. Bedeli: düğüm başına bir referans daha.
  • Dairesel: son düğümün next’i başa döner → “sonra kim?” sorusu hiç bitmez. Tur sırası, döngüsel animasyonlar, müzik çalma listesi (“tekrarla”).

C#’taki LinkedList<T> çift yönlü ve içeride dairesel bir listedir.

🃏 Uno masası: dairesel çift yönlü liste

🐍 Yılan oyunu: gövde = liste

Her adımda: yeni baş düğüm başa eklenir, kuyruk sondan silinir (yemek yediyse silinmez). Uzunluk 1000 olsa bile her adım sabit iş. Yılanı yöneten minik “YZ”: yemeğe en çok yaklaştıran güvenli yönü seçiyor (açgözlü / greedy — yol bulma derslerine selam!).

👾 Ölen düşmanı listeden çıkarmak: swap & pop

🔫 Mermi havuzu: nesne havuzu + boş liste object pool · free list

Saniyede yüzlerce mermi için new/Destroy = sürekli çöp + GC takılmaları. Havuz: mermileri baştan bir kez oluştur; boş olanları indekslerle bağlı bir liste (boş liste) halinde tut. Ateş: listenin başını al. Yok olma: başa geri koy. İkisi de O(1), çöp sıfır!

Mermi havuzu — kod

🎒 koşul ? a : b = “koşul doğruysa a, değilse b” · Array.from({ length: n }, (_, i) => …) = “n elemanlı dizi, i. eleman = …” · Unity’nin kendi hazır havuzu da var: UnityEngine.Pool.ObjectPool<T>.

Hash + çift yönlü liste = LRU önbelleği

Oyununuz bellek sınırlı bir cihazda: en fazla 50 doku texture bellekte durabiliyor. Yenisi gerekince hangisini atmalı?

En uzun süredir kullanılmayanı (Least Recently Used, LRU):

  • Dokuları çift yönlü listede tut: kullanılan doku listenin başına taşınır (O(1))
  • Yer lazım olunca listenin sonundakini at (O(1))
  • “Bu doku listede nerede?” sorusu için bir hash tablosu (Dictionary) düğümü doğrudan gösterir (ileriki ders)
🌍 Her yerdeİşlemci önbellekleri, web tarayıcıları, veritabanları, işletim sistemlerinin sayfa yönetimi… Bağlı listenin “elindeki düğümü O(1) taşı/sil” süper gücünün en ünlü kullanımı.
LEVEL 6
Perde Arkası
C’de işaretçiler · bellek sızıntısı · çöp toplayıcı
  • dizi: bellekte tek parça
  • bağlı liste: düğümler ve oklar
  • işlemler
  • dinamik dizi
  • büyük karşılaştırma
  • varyasyonlar ve oyunlar
  • perde arkası

⚙️ Bağlı liste C dilinde: gerçek işaretçiler pointer

  • Node* = “bir Node’un adresi” (işaretçi). C#/Python/JS’deki referansın çıplak hali.
  • malloc: bellekten yer iste · free: geri ver — elle!
  • Bellek sızıntısı memory leak: free’yi unutmak → bellek hep dolu kalır. Saatlerce açık kalan oyunlar yavaş yavaş belleği yer.
  • Sarkan işaretçi dangling pointer: free’den sonra hâlâ kullanmak → rastgele çökme, güvenlik açığı.
  • C#, Python, JS’de bunları çöp toplayıcı sizin yerinize yapar: ulaşılamayan düğümler otomatik silinir.

Derin hikâye: Linux’un “müdahaleci” listeleri (list_head)

  • Klasik bağlı listede düğüm, veriyi tutar: Node { data; next; }. Linux çekirdeği tersini yapar: veri, düğümü içinde taşır. Her yapının içine küçük bir struct list_head { next, prev } gömülür.
  • Listede dolaşırken eldeki list_head işaretçisinden, onu içeren asıl yapıya container_of makrosuyla (alanın yapı içindeki konumunu çıkararak) geri dönülür.
  • Kazançlar: düğüm için ayrı bellek ayırma yok; bir nesne aynı anda birden çok listede olabilir (ör. bir süreç hem “çalışanlar” hem “bekleyenler” listesinde ayrı list_head’lerle); nesneyi bildiğinizde listeden O(1) çıkarabilirsiniz.
DersBağlı listenin güçlü olduğu yer, elinizde düğüm varken O(1) ekleme/çıkarmadır; zayıf olduğu yer, rastgele erişim ve önbellek (Stroustrup’un uyarısı). Oyun motorlarında da aynı kalıp görülür: varlıkların içine gömülü listeler, nesne havuzlarının “serbest listeleri”, LRU önbellekleri.

Kaynak: Linux: include/linux/list.h · Stroustrup: Are lists evil?

🧰 Kütüphaneler ve araçlar

adplatformne yapar / sınırlarınasıl eklenir
LinkedList<T>C# / UnityÇift yönlü; LinkedListNode ile O(1) ekleme/çıkarma. Her düğüm bir nesne: Unity’de sık ekleme çöp üretir.yerleşik
collections.deque · OrderedDictPythondeque blok bağlantılı; OrderedDict.move_to_end ile LRU.standart kütüphane
functools.lru_cachePythonHazır LRU önbellek dekoratörü (içeride hash + çift bağlı liste).standart kütüphane
std::list · std::forward_listC++Çift ve tek bağlı listeler; splice ile O(1) liste birleştirme.#include <list>
(JS’te yok)JavaScriptYerleşik bağlı liste yok; çoğu durumda dizi daha hızlı. LRU için Map’in ekleme sırası kullanılabilir.—

🧩 Oyunlarda bağlı liste fikri

  • Nesne havuzu + serbest liste: bir dizinin içinde, boş yuvaların “sonraki boş” indekslerini tutarak O(1) al/bırak; çöp yok. Mermiler, parçacıklar, düşmanlar.
  • LRU önbellek: hash + çift bağlı liste; en son kullanılanı başa taşı, dolunca sondakini at (doku/ses önbellekleri, yol önbelleği).
  • Müdahaleci listeler: varlık kendi next/prev’ini taşır; aynı varlık “görünenler” ve “aktifler” listelerinde.
  • Rastgele erişim ya da sık dolaşma varsa: dizi (List<T>), çoğu zaman daha hızlı.
Sık hatalar
  • Rastgele erişim için bağlı liste (O(n)).
  • Her düğüm için new: Unity’de çöp baskısı.
  • Silmede prev/next’ten birini güncellemeyi unutmak.
  • Dolaşırken listeden silip iteratörü bozmak.

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin
  • Rastgele erişim için bağlı liste
  • Her düğüm için new
  • prev/next güncellemesini unutmak
  • Dolaşırken silme
İyi bir istek (prompt) örneği

“Unity 6, C#. Bir mermi havuzu yaz: sabit kapasiteli Bullet[] dizisi + int nextFree[] ile indeks tabanlı serbest liste; Spawn() O(1) ve çöp üretmeden bir yuva verir, Despawn(index) O(1) geri koyar; aktif mermileri dolaşmak için ayrıca sıkı (dense) bir aktif indeks dizisi tut (swap-remove). Profilleyicide GC Alloc = 0 olduğunu gösteren bir PlayMode testi ve List + Instantiate/Destroy ile karşılaştırma ölçümü ekle.”

  • Dizi içinde indeks tabanlı serbest liste isteyin
  • Çöp üretmeyen tasarımı açıkça isteyin
  • Silme sırasında bağlantı güncellemesini test ettirin
  • Önce List ile karşılaştırma ölçümü isteyin

🚀 Proje ve araştırma önerileri

  1. [kolay] Nesne havuzu — Serbest listeli mermi havuzu; Instantiate/Destroy ile ölçün.
  2. [orta] LRU önbellek — Hash + çift bağlı liste ile LRU; isabet oranını farklı kapasitelerde ölçün.
  3. [orta] Müdahaleci liste — Varlıkların içine gömülü next/prev ile “görünen düşmanlar” listesi.
  4. [araştırma] Stroustrup deneyi — Sıralı diziye rastgele ekleme/silme: dizi ve bağlı liste sürelerini N büyüdükçe karşılaştırın; önbellek etkisini açıklayın.

📄 Akademik okumalar ve kaynaklar

Newell & Shaw 1957 · Programming the Logic Theory Machine (Western Joint Computer Conference)
Liste işleme dilinin (IPL) ve bağlı listenin doğuşu.
Knuth 1997 · The Art of Computer Programming, Vol. 1, §2.2 Linear Lists (Addison-Wesley)
Bağlı bellek ayırma.
Stroustrup 2014 · Are lists evil? (isocpp.org)
Dizi mi liste mi: önbellek gerçeği.

Neler öğrendik? 🎒

  • Dizi: bitişik bellek, a[i] O(1), araya ekleme O(N), sabit boyut.
  • Bağlı liste: düğümler + oklar; başa ekleme O(1), a[i] O(N).
  • Ok kuralı: değiştirmeden önce gösterdiği yeri kaydet.
  • Dinamik dizi: iki katına büyüt, dörtte birde yarıya küçült → amortize O(1).
  • Bellek ve önbellek: Büyük-O her şey değil; dizi çoğu zaman kazanır.
  • Çift yönlü / dairesel: Uno sırası, LRU önbelleği.
  • Oyun desenleri: yılan, swap & pop, nesne havuzu + boş liste.
  • ⚙️ İşaretçi, sızıntı, sarkan işaretçi, çöp toplayıcı.

Alıştırmalar 🏋️

  1. Kâğıt-kalem: 1 → 2 → 3 → 4 listesini tersine çevirirken her adımda prev, cur, nxt’nin neyi gösterdiğini çizin.
  2. Laboratuvarda removeFirst(head, key) yazın: değeri key olan ilk düğümü silip başı döndürsün. (Silinecek ilk düğümse?)
  3. Bir listenin ortadaki düğümünü tek geçişte bulun. (İpucu: biri birer, biri ikişer adım atan iki işaretçi.)
  4. p5.js’te yılan oyununu yazın; gövdeyi bir dizi ile unshift/pop kullanarak tutun. Yılan çok uzayınca ne olur? (İpucu: unshift O(N)!)
  5. Unity’de mermiler için Instantiate/Destroy ile havuzu karşılaştırın: Profiler’da GC Alloc sütununa bakın.
  6. 🤖 Bir YZ asistanından C#’ta çift yönlü liste isteyin. Boş liste, tek elemanlı liste ve baştaki/sondaki düğümü silme durumlarını test edin — kodda hata buldunuz mu?

Kaynaklar: videolar 🎬

Kaynaklar: okuma ve görselleştirme 📚

NEXT LEVEL ▶
Yığınlar ve Kuyruklar
Başa ekle + baştan çıkar = yığın. Sona ekle + baştan çıkar = kuyruk. İkisini de az önce yaptık! 😉
SONRAKİ SUNUM ▶