---
title: 'Bağlı Listeler'
source: 'https://academia.sh/tr/kurslar/veri-yapilari/bagli-listeler'
course: 'Veri Yapıları'
language: tr
updated: '2026-08-17T18:07:56+00:00'
license: 'CC BY-SA 4.0'
---

# Bağlı Listeler

Düğüm ve bağ yapısı, tek ve çift yönlü listeler, işaretçi yeniden bağlamanın maliyeti ve pratikteki sınırları.

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.

```python
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.

```python
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.