Bağlı Listeler

Dizinin ekleme ve silme maliyeti, tek bir gereklilikten doğuyordu: elemanların bitişik durması. Bitişiklik terk edilirse kaydırma da ortadan kalkar.

Bağlı liste (linked list) bu değiş tokuşu yapar. Elemanlar bellekte istedikleri yerde durur; sıra, her elemanın bir sonrakinin adresini taşımasıyla kurulur.

Düğüm ve Bağ

Yapının birimi düğümdür (node): bir değer ve bir sonraki düğümün adresi.

baş → [12 | •] → [18 | •] → [7 | •] → [25 | ⏚]

Son düğümün bağı boştur; listenin sonunu bu boşluk belirtir. Listenin kendisi tek bir şeyle temsil edilir: ilk düğümün adresi, yani baş.

Adres aritmetiği burada geçersizdir. Üçüncü elemanın nerede olduğu hesaplanamaz; baştan başlanıp iki bağ izlenmelidir. Bu, dizinin sabit zamanlı erişimini kaybetmek demektir: bağlı listede $i$’nci elemana erişim $O(n)$’dir.

class Dugum:
    """Bir değer ve bir sonraki düğümün bağı."""

    def __init__(self, deger: int) -> None:
        self.deger = deger
        self.sonraki: "Dugum | None" = None


class BagliListe:
    def __init__(self) -> None:
        self.bas: Dugum | None = None
        self.uzunluk = 0

    def basa_ekle(self, deger: int) -> None:
        """Yeni düğümü başa bağlar: sabit zamanlı."""
        yeni = Dugum(deger)
        yeni.sonraki = self.bas
        self.bas = yeni
        self.uzunluk += 1

    def bul(self, deger: int) -> int:
        """Değerin sırasını döndürür; yoksa -1. İzlenen bağ sayısı kadar adım atar."""
        sira = 0
        dugum = self.bas
        while dugum is not None:
            if dugum.deger == deger:
                return sira
            dugum = dugum.sonraki
            sira += 1
        return -1

    def degerler(self) -> list[int]:
        sonuc = []
        dugum = self.bas
        while dugum is not None:
            sonuc.append(dugum.deger)
            dugum = dugum.sonraki
        return sonuc


liste = BagliListe()
for olcum in (25, 7, 18, 12):        # ters sırada eklenir
    liste.basa_ekle(olcum)

print(liste.degerler())              # [12, 18, 7, 25]
print(liste.bul(7), liste.bul(99))   # 2 -1
print(liste.uzunluk)                 # 4

Başa ekleme sabit zamanlıdır: iki bağ yazılır, hiçbir eleman taşınmaz. Dizide aynı işlem tüm elemanları kaydırıyordu.

Konum Bulmak ile Bağlamak

Bağlı listenin en sık yanlış anlaşılan yanı şudur: ekleme ve silme ucuzdur, ancak yerini bulmak pahalıdır.

Elde bir düğüm referansı varsa, ondan sonrasına eklemek birkaç işaretçi yazımıdır — $O(1)$. Ancak “onuncu elemandan sonraya ekle” denirse, önce dokuz bağ izlenir; toplam maliyet yine $O(n)$ olur.

Bu ayrım, bağlı listenin doğru kullanım alanını belirler: ilgili düğümün referansı zaten elde tutuluyorsa yapı kazanç sağlar; her işlemde baştan aranıyorsa sağlamaz.

Çift Yönlü Liste

Tek yönlü listede bir düğümü silmek, önceki düğümün bağını değiştirmeyi gerektirir; oysa düğümden geriye gidilemez. Çözüm, her düğüme bir de geri bağ eklemektir.

Çift yönlü listede her düğüm hem sonrakini hem öncekini bilir. Sonuçları:

• Elde bir düğüm referansı varken silme $O(1)$ olur.
• Liste iki yönde gezilebilir.
• Her düğüm bir işaretçi daha taşır; bellek ek yükü artar.
• Her ekleme ve silmede iki yerine dört bağ güncellenir; kod daha hatalıdır.

Baş ve son işaretçilerinin ikisi birden tutulursa, listenin her iki ucuna ekleme sabit zamanlı olur. Bu, sonraki iki dersteki yığıt ve kuyruk yapılarının doğal temelidir.

Üçüncü bir varyant, son düğümün başa bağlandığı dairesel listedir; sıradaki öğeye sürekli dönen zamanlama ve tampon uygulamalarında kullanılır.

Sınır Düğümü

Bağlı liste kodunun hata kaynağı, uç durumlardır: boş listeye ekleme, ilk düğümü silme, son düğümden sonrasına ekleme. Her biri ayrı bir if bloğu gerektirir ve bu bloklardan biri unutulduğunda hata, yalnızca o durumda ortaya çıkar.

Sınır düğümü (sentinel), değer taşımayan sahte bir düğümdür ve listenin başına kalıcı olarak yerleştirilir. Baş her zaman var olduğundan, “ilk düğümü silmek” ayrı bir durum olmaktan çıkar — her düğümün bir öncesi vardır.

class SinirliListe:
    """Baştaki sınır düğümü sayesinde silme tek bir kodla yürür."""

    def __init__(self) -> None:
        self.sinir = Dugum(0)          # değeri kullanılmaz

    def ekle(self, deger: int) -> None:
        yeni = Dugum(deger)
        yeni.sonraki = self.sinir.sonraki
        self.sinir.sonraki = yeni

    def sil(self, deger: int) -> bool:
        onceki = self.sinir            # her zaman geçerli bir "önceki" var
        while onceki.sonraki is not None:
            if onceki.sonraki.deger == deger:
                onceki.sonraki = onceki.sonraki.sonraki
                return True
            onceki = onceki.sonraki
        return False


liste = SinirliListe()
for o in (7, 18, 12):
    liste.ekle(o)
print(liste.sil(12), liste.sil(99))    # True False

Aynı teknik, dairesel çift yönlü listelerde de kullanılır ve kodun uç durum sayısını belirgin biçimde azaltır.

Bellek Ek Yükü ve Önbellek

Bağlı listenin ilan edilen üstünlükleri, pratikte iki maliyetle sınırlanır.

Ek yer. Her düğüm, değerin yanında bir veya iki işaretçi taşır. Sekiz baytlık işaretçilerle, dört baytlık tam sayılardan oluşan tek yönlü bir listede yapı verisi, gerçek veriden fazladır. Diziyle karşılaştırıldığında bellek kullanımı kat düzeyinde artabilir.

Yerellik. Düğümler öbekte dağınık durur. Bir düğümden diğerine geçmek, bellekte öngörülemeyen bir adrese atlamaktır; önbellek satırı getirmenin kazancı yoktur ve önden getirme çalışmaz. Bilgisayarlar Nasıl Çalışır kursunun önbellek dersinde hesaplanan fark burada tersine işler: dizi taraması satır başına birçok eleman kullanırken, liste taraması her düğüm için ayrı bir ıska riski taşır.

Sonuç şudur: kâğıt üzerinde $O(1)$ olan bağlı liste eklemesi, gerçek ölçümlerde $O(n)$ olan dizi eklemesinden yavaş kalabilir — özellikle eleman sayısı küçük veya orta ölçekteyken. Karmaşıklık sınıfı, sabit çarpanları görmezden gelir; donanım görmezden gelmez.

Ne Zaman Bağlı Liste

Yapının meşru kullanım alanları dardır ama gerçektir:

• Düğüm referansı elde tutuluyorsa. En bilinen örnek, bir karma tablosuyla birlikte kullanılan çift yönlü listedir: tablo düğümü doğrudan verir, liste sıralamayı sabit zamanda günceller. En az kullanılanı çıkaran önbellek tasarımı bu ikilinin üzerine kurulur.
• Yeniden ayırma kabul edilemezse. Dinamik dizinin büyümesi, tek bir işlemi uzun sürdürür; gecikme sınırı olan sistemlerde bu kabul edilmeyebilir.
• Referans kararlılığı gerekiyorsa. Bağlı listede bir düğümün adresi, listeye yeni elemanlar eklendiğinde değişmez; dinamik dizide yeniden ayırma tüm adresleri geçersizleştirir.
• Listelerin birleştirilmesi sıksa. İki listeyi uç uca eklemek, bağ yazmaktan ibarettir.

Bunların dışında, varsayılan seçim dizidir.

Maliyet Tablosu

Yapı	Erişim	Arama	Başa ekleme	Sona ekleme	Silme (düğüm elde)
Dizi (sabit boyut)	$O(1)$	$O(n)$	$O(n)$	$O(1)$*	$O(n)$
Dinamik dizi	$O(1)$	$O(n)$	$O(n)$	$O(1)$ amortize	$O(n)$
Tek yönlü bağlı liste	$O(n)$	$O(n)$	$O(1)$	$O(n)$**	$O(n)$
Çift yönlü bağlı liste	$O(n)$	$O(n)$	$O(1)$	$O(1)$**	$O(1)$

* Yer kaldığı sürece. ** Son işaretçisi tutuluyorsa $O(1)$.

Özet

• Bağlı listede elemanlar bitişik durmaz; sıra, her düğümün bir sonrakinin adresini taşımasıyla kurulur.
• Adres aritmetiği geçersizdir; $i$’nci elemana erişim doğrusal zamanlıdır.
• Ekleme ve silme, işaretçi yazmaktan ibaret olduğu için ucuzdur; pahalı olan, konumu bulmaktır.
• Çift yönlü listede geri bağ, elde düğüm varken silmeyi sabit zamanlı yapar; karşılığı ek bellek ve daha karmaşık güncellemedir.
• İşaretçi ek yükü ve dağınık yerleşim, listenin pratik başarımını kuramsal maliyetinin altına çekebilir.
• Yapı, düğüm referansının elde tutulduğu, yeniden ayırmanın kabul edilmediği veya referans kararlılığının gerektiği durumlarda seçilir.

Sonraki Adım

Sonraki iki ders, buraya kadar tanımlanan yapıların üzerine kurulan iki soyut veri tipini ele alacak. İlki, yalnızca son eklenen elemana erişime izin veren yığıttır; fonksiyon çağrılarının nasıl yönetildiğini önceki kurstan hatırlayacaksınız.