Veri yapıları: yığın, kuyruk, öncelik kuyruğu, bağlı liste, hash, ağaç ve graf

Neden önemli?

Anadolu Market'in çağrı merkezinde arayanlar sıraya girer; ilk arayan ilk konuşur. Şehir hastanesinin acil servisinde ise sıra geliş saatine göre değil, aciliyete göre belirlenir. Kampanya editöründe "geri al" tuşu en son yapılan işlemi geri çevirir. Lojistik ekibi depolar arasındaki yolları bir ağ olarak düşünür. Bu dört iş dört farklı veri yapısı (data structure) ister: kuyruk, öncelik kuyruğu, yığın ve graf.

Yanlış yapı seçmek kodu yanlış yapmaz ama yavaşlatır: 1 milyon elemanlı listede pop(0) her seferinde tüm elemanları kaydırır. Doğru yapı ise aynı işi sabit sürede yapar. Bu derste her yapının ne işe yaradığını, Python'daki hazır karşılığını ve mantığını kavramak için sıfırdan nasıl yazıldığını göreceksin. deque, Counter gibi araçlarla collections ve itertools dersinde, kümelerle Demetler ve kümeler dersinde tanışmıştın; burada onları veri yapısı gözüyle yeniden ele alıyoruz.

Yığın (stack): son giren ilk çıkar

Yığın, üst üste konmuş tabaklar gibidir: en son koyduğunu ilk alırsın (LIFO, last in first out). Python'da sıradan bir list mükemmel bir yığındır: append üste koyar, pop() üstten alır, [-1] üsttekine bakar; üçü de O(1).

def dengeli_mi(ifade):
    eslesme = {")": "(", "]": "[", "}": "{"}
    yigin = []
    for ch in ifade:
        if ch in "([{":
            yigin.append(ch)                       # açılanı üste koy
        elif ch in eslesme:
            if not yigin or yigin.pop() != eslesme[ch]:
                return False                       # kapanış, üstteki açılışla eşleşmeli
    return not yigin                               # açık kalan olmamalı

for f in ["(fiyat * [1 + kdv])", "{indirim: (10]", "((tutar)", ""]:
    print(repr(f), dengeli_mi(f))

Derleyiciler, JSON ayrıştırıcıları ve hesap makineleri iç içe yapıları böyle kontrol eder. Yığının bir başka klasik kullanımı geri al (undo) özelliğidir: her işlem yığına konur, geri al en üsttekini çıkarır. Fonksiyon çağrıları da bir yığında tutulur; özyinelemede gördüğün RecursionError bu çağrı yığınının (call stack) taşmasıdır.

Kuyruk (queue): ilk giren ilk çıkar

Kuyruk, banka gişesindeki sıradır (FIFO, first in first out). Liste ile kuyruk yapmak tuzaktır: liste.pop(0) baştaki elemanı çıkarınca geri kalan tüm elemanları bir sola kaydırır, yani O(n)'dir. collections.deque (double-ended queue, iki uçlu kuyruk) iki uçta da O(1) ekler ve çıkarır.

from collections import deque
cagri = deque()
for musteri in ["Ayşe (sipariş)", "Mehmet (iade)", "Zeynep (kargo)"]:
    cagri.append(musteri)                 # sıranın sonuna
cagri.appendleft("Can (VIP)")             # VIP öne geçer
while cagri:
    print("Görüşülüyor:", cagri.popleft(), "| bekleyen:", len(cagri))

son_islemler = deque(maxlen=3)            # sabit boyutlu pencere
for no in range(101, 106):
    son_islemler.append(no)
print(son_islemler)

maxlen verilen bir deque dolunca yeni eleman eklendikçe öbür uçtaki en eski eleman düşer: "son 100 işlem", "son 5 dakikanın logları" için idealdir. İş parçacıkları (thread) arasında güvenli kuyruk gerekiyorsa queue.Queue kullanılır; onu Eşzamanlılık (concurrency) dersinde göreceksin.

Öncelik kuyruğu: heapq

Acil serviste sıra aciliyete göredir: kırmızı alan hastası, sarı alandakinden önce muayene edilir. Öncelik kuyruğu (priority queue) her zaman en öncelikli elemanı verir. Python'da heapq modülü, sıradan bir listeyi ikili yığın (binary heap) olarak düzenler: en küçük eleman hep h[0]'dadır; ekleme ve çıkarma O(log n)'dir.

import heapq
from itertools import count

sira = count()                       # eşit öncelikte geliş sırası
bekleyenler = []
for ad, oncelik in [("Ali", 3), ("Elif", 1), ("Burak", 2), ("Seda", 1)]:
    heapq.heappush(bekleyenler, (oncelik, next(sira), ad))   # 1 = en acil

while bekleyenler:
    oncelik, _, ad = heapq.heappop(bekleyenler)
    print(f"{ad} (öncelik {oncelik})")

tutarlar = [250, 1999, 75, 4300, 860, 120]
print(heapq.nlargest(3, tutarlar), heapq.nsmallest(2, tutarlar))

Demetler (tuple) sırayla karşılaştırılır: önce öncelik, eşitse ikinci eleman. Araya bir sıra numarası koymak iki işe yarar: eşit öncelikte ilk gelen önce çıkar (kararlılık) ve Python hiçbir zaman üçüncü elemanı (karşılaştırılamayan bir sözlük ya da nesne olabilir) karşılaştırmak zorunda kalmaz. heapq yalnızca en küçüğü verir; en büyüğü istiyorsan önceliği eksiyle sakla: (-tutar, ...).

Bağlı liste: düğümler zinciri

Bağlı liste (linked list), her biri bir değer ve bir sonraki düğüme bağlantı taşıyan düğümlerden (node) oluşur. Başa ekleme O(1)'dir ve hiçbir eleman kaydırılmaz; buna karşılık i'inci elemana erişmek için baştan yürümek gerekir, O(n). Python'da günlük işte bağlı liste yazmazsın (deque zaten içeride bağlı bloklar kullanır), ama mülakatlarda ve "referans" kavramını oturtmakta çok değerlidir.

class Dugum:
    def __init__(self, deger, sonraki=None):
        self.deger = deger
        self.sonraki = sonraki

class BagliListe:
    def __init__(self):
        self.bas = None
        self.uzunluk = 0
    def basa_ekle(self, deger):
        self.bas = Dugum(deger, self.bas)   # yeni düğüm eski başı gösterir
        self.uzunluk += 1
    def __iter__(self):
        dugum = self.bas
        while dugum:
            yield dugum.deger
            dugum = dugum.sonraki
    def ters_cevir(self):
        onceki, dugum = None, self.bas
        while dugum:
            dugum.sonraki, onceki, dugum = onceki, dugum, dugum.sonraki
        self.bas = onceki

rota = BagliListe()
for durak in ["Bursa", "Ankara", "İstanbul"]:
    rota.basa_ekle(durak)
print(list(rota), rota.uzunluk)
rota.ters_cevir()
print(" -> ".join(rota))

__iter__'ı üreteçle (generator) yazınca sınıf list(), for ve join ile doğal çalışır. Ters çevirme, üç işaretçiyle (önceki, şimdiki, sonraki) yerinde yapılır; klasik bir mülakat sorusudur.

Hash tablosu: dict ve set nasıl bu kadar hızlı?

Sözlükte d["AM-1042"] araması, sözlükte 10 ya da 10 milyon eleman olsa da ortalama aynı sürede biter. Sırrı hash tablosudur: anahtar hash() fonksiyonuyla bir tam sayıya çevrilir, bu sayıdan bir kova (bucket) indeksi hesaplanır (hash(anahtar) % kova_sayisi) ve değer doğrudan o kovaya gider. Aramada aynı hesap tekrar yapılır; tarama yoktur.

İki farklı anahtar aynı kovaya düşebilir: buna çakışma (collision) denir. Çözümlerden biri her kovada küçük bir liste tutmaktır (zincirleme, chaining); CPython ise boş kova arayarak ilerleyen açık adresleme (open addressing) kullanır. Tablo dolmaya başlayınca (doluluk oranı, load factor) kova sayısı büyütülür ve her şey yeniden yerleştirilir; bu yüzden ekleme "amortize" O(1)'dir.

class MiniSozluk:
    def __init__(self, kova_sayisi=4):
        self.kovalar = [[] for _ in range(kova_sayisi)]
    def _kova(self, anahtar):
        return self.kovalar[hash(anahtar) % len(self.kovalar)]
    def koy(self, anahtar, deger):
        kova = self._kova(anahtar)
        for i, (a, _) in enumerate(kova):
            if a == anahtar:                 # aynı anahtar: güncelle
                kova[i] = (anahtar, deger)
                return
        kova.append((anahtar, deger))        # çakışma olsa da aynı kovaya eklenir
    def al(self, anahtar):
        for a, d in self._kova(anahtar):
            if a == anahtar:
                return d
        raise KeyError(anahtar)

s = MiniSozluk()
for kod, stok in [("SUT", 40), ("EKMEK", 120), ("PEYNIR", 15), ("YAG", 8), ("CAY", 60)]:
    s.koy(kod, stok)
s.koy("SUT", 35)
print(s.al("SUT"), s.al("CAY"))
print([len(k) for k in s.kovalar], "eleman/kova")
print(hash(1) == hash(1.0), {1: "a", 1.0: "b"})

Son satır önemli bir kuralı gösterir: eşit olan nesnelerin hash'i de eşit olmalıdır. 1 == 1.0 olduğu için sözlük onları aynı anahtar sayar. Bu kuralın sonucu: değişebilir nesneler (list, dict, set) anahtar olamaz, çünkü içerikleri değişince hash'leri de değişir ve kayıt yanlış kovada kalır. Anahtar olabilen nesnelere hashable denir: int, str, tuple (içi de hashable ise), frozenset. Kendi sınıfında __eq__ yazarsan __hash__'i de tutarlı yazmalısın; @dataclass(frozen=True) bunu senin için yapar.

Küme işlemleri

set değeri olmayan bir hash tablosudur: üyelik testi O(1), tekrarları otomatik atar. Kampanya hedeflemede kümeler doğal dildir:

sut_alan = {"m1", "m2", "m3", "m5"}
kahve_alan = {"m2", "m3", "m4"}
sadik = {"m3", "m5", "m9"}
print(sorted(sut_alan & kahve_alan))          # kesişim: ikisini de alan
print(sorted(sut_alan | kahve_alan))          # birleşim
print(sorted(sut_alan - kahve_alan))          # fark: süt alıp kahve almayan
print(sorted(sut_alan ^ kahve_alan))          # yalnız birini alan
print((sut_alan & kahve_alan) <= (sut_alan | sadik))   # alt küme mi?
segmentler = {frozenset({"süt", "kahve"}): 2}  # frozenset sözlük anahtarı olabilir
print(segmentler[frozenset({"kahve", "süt"})])

İkili arama ağacı (BST)

Ağaç (tree), kökten dallanan düğümlerden oluşur. İkili arama ağacında (binary search tree) her düğümün solundaki tüm değerler ondan küçük, sağındakiler büyüktür. Bu kural sayesinde arama her adımda yarı yarıya daralır; ağaç dengeliyse ekleme ve arama O(log n)'dir. Ağacı sıralı gezmek (in-order: sol, kök, sağ) değerleri küçükten büyüğe verir.

class Dugum:
    def __init__(self, deger):
        self.deger, self.sol, self.sag = deger, None, None

def ekle(kok, deger):
    if kok is None:
        return Dugum(deger)
    if deger < kok.deger:
        kok.sol = ekle(kok.sol, deger)
    elif deger > kok.deger:
        kok.sag = ekle(kok.sag, deger)
    return kok                                  # eşitse eklenmez

def ara(kok, deger):
    while kok and kok.deger != deger:
        kok = kok.sol if deger < kok.deger else kok.sag
    return kok is not None

def sirali(kok):
    return sirali(kok.sol) + [kok.deger] + sirali(kok.sag) if kok else []

def yukseklik(kok):
    return 1 + max(yukseklik(kok.sol), yukseklik(kok.sag)) if kok else 0

kok = None
for fiyat in [50, 30, 70, 20, 40, 60, 80]:
    kok = ekle(kok, fiyat)
print(sirali(kok), ara(kok, 60), ara(kok, 65), yukseklik(kok))
sirali_giris = None
for fiyat in range(1, 8):
    sirali_giris = ekle(sirali_giris, fiyat)
print("sıralı eklenince yükseklik:", yukseklik(sirali_giris))

Son satır BST'nin zayıf noktasıdır: veriyi sıralı eklersen ağaç bir zincire (bağlı listeye) dönüşür ve işlemler O(n) olur. Gerçek sistemler bunu önlemek için kendini dengeleyen ağaçlar (AVL, kırmızı-siyah) ya da veritabanlarında B-ağaçları kullanır. Veritabanı indeksleri (index) tam olarak budur.

Graf: komşuluk listesi

Graf (graph), düğümler (vertex) ve onları bağlayan kenarlardan (edge) oluşur: depolar ve yollar, kullanıcılar ve takip ilişkileri, banka hesapları ve para transferleri. Python'da en pratik temsil komşuluk listesidir (adjacency list): her düğüm için komşularının listesi ya da kümesi.

from collections import defaultdict
yollar = [("Gebze", "İstanbul"), ("Gebze", "Bursa"), ("Bursa", "İzmir"), ("Ankara", "Bursa")]
graf = defaultdict(set)
for a, b in yollar:            # yönsüz: iki yöne de ekle
    graf[a].add(b)
    graf[b].add(a)
for depo in sorted(graf):
    print(depo, "->", sorted(graf[depo]))
en_bagli = max(sorted(graf), key=lambda d: len(graf[d]))
print("En çok bağlantı:", en_bagli, len(graf[en_bagli]))
print("Bursa-İzmir yolu var mı?", "İzmir" in graf["Bursa"])

Kenar sayısı az olan (seyrek) graflarda komşuluk listesi bellek dostudur. Alternatif olan komşuluk matrisi (n×n tablo) "iki düğüm bağlı mı" sorusunu O(1) yanıtlar ama n² bellek ister. Graf üzerinde gezinme (BFS, DFS) ve en kısa yol Algoritmalar dersinin konusu.

Karmaşıklık tablosu