Çift Yönlü Bağlı Listeler Doubly Linked List

Çift Yönlü Bağlı Liste Nedir?

Çift yönlü bağlı liste (doubly linked list), her düğümün hem bir sonraki hem de bir önceki düğümün adresini tuttuğu bir veri yapısıdır. Tek yönlü bağlı listede sadece ileriye gidebilirken, çift yönlü listede her iki yöne de hareket edebilirsiniz. Bu esneklik, birçok operasyonun karmaşıklığını düşürür ve bazı işlemleri mümkün kılar.

Bunu iki yönlü bir tren vagonu zinciri gibi düşünebilirsiniz: her vagonun önünde ve arkasında bir bağlantı halkası vardır. Herhangi bir vagondayken hem ileriye hem geriye yürüyebilirsiniz. Tek yönlü listede bu mümkün değildi; sadece baş vagonu bilir ve sonuna kadar ileri gidebilirdiniz.

Temel Kavramlar

Düğüm Yapısı: prev + data + next

Tek yönlü listede düğüm sadece data ve next tutarken, çift yönlü listede bir de prev (previous — önceki) pointer'ı eklenir. Bu üç alanlı yapı sayesinde herhangi bir düğümden hem ileri hem geri yönde hareket edebilirsiniz. İlk düğümün prev'i NULL'dur (öncesi yok), son düğümün next'i NULL'dur (sonrası yok).

Tek Yönlü vs Çift Yönlü

Bellek Maliyeti

Çift yönlü listede her düğüm ekstra bir pointer daha taşır. 64-bit sistemde bu, düğüm başına 8 byte daha fazla bellek demektir. Tek bir int saklamak için toplam 24 byte harcanır:

Node Yapısı ve Liste Oluşturma

C dilinde çift yönlü bağlı liste düğümü, tek yönlüye kıyasla bir ek pointer içerir. Struct tanımı ve yeni düğüm oluşturma fonksiyonu şu şekildedir:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* prev;    // önceki düğüm (yeni eklenen alan)
    struct Node* next;    // sonraki düğüm
} Node;

// Yeni düğüm oluşturma
Node* yeniDugum(int deger) {
    Node* dugum = (Node*)malloc(sizeof(Node));
    if (dugum == NULL) {
        printf("Bellek ayrılamadı!\n");
        exit(1);
    }
    dugum->data = deger;
    dugum->prev = NULL;   // başlangıçta bağlantı yok
    dugum->next = NULL;   // başlangıçta bağlantı yok
    return dugum;
}

Şimdi düğümleri birbirine bağlayarak çift yönlü bir liste oluşturalım. Tek yönlüden farklı olarak her bağlantı iki taraflı kurulmalıdır: A'nın next'i B'yi gösterirken, B'nin prev'i de A'yı göstermelidir.

int main() {
    Node* head = yeniDugum(10);
    Node* ikinci = yeniDugum(20);
    Node* ucuncu = yeniDugum(30);

    // İki yönlü bağlantıları kur
    head->next = ikinci;
    ikinci->prev = head;       // ← tek yönlüde bu satır yoktu

    ikinci->next = ucuncu;
    ucuncu->prev = ikinci;     // ← tek yönlüde bu satır yoktu

    // head->prev = NULL (zaten yeniDugum'da atandı)
    // ucuncu->next = NULL (zaten yeniDugum'da atandı)

    // NULL ← 10 ⇄ 20 ⇄ 30 → NULL
    return 0;
}

İleri ve Geri Traverse

Çift yönlü listenin en büyük avantajlarından biri, listeyi her iki yönde de dolaşabilmektir. İleri traverse tek yönlüyle aynıdır: head'den başlayıp next'leri takip edersiniz. Geri traverse ise son düğümden başlayıp prev'leri takip eder.

// İleri traverse: head → NULL
void ileriYazdir(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d ⇄ ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}
// Çıktı: 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ NULL

// Geri traverse: tail → NULL
void geriYazdir(Node* head) {
    if (head == NULL) return;

    // Önce son düğüme git
    Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    // Geriye doğru yürü
    while (temp != NULL) {
        printf("%d ⇄ ", temp->data);
        temp = temp->prev;
    }
    printf("NULL\n");
}
// Çıktı: 40 ⇄ 30 ⇄ 20 ⇄ 10 ⇄ NULL

Başa Eleman Ekleme

Başa ekleme tek yönlüyle benzerdir ama ek olarak eski head'in prev pointer'ını yeni düğüme yönlendirmek gerekir. Toplam 3 pointer işlemi yapılır ve karmaşıklık O(1)'dir.

void basaEkle(Node** head, int deger) {
    Node* yeni = yeniDugum(deger);

    yeni->next = *head;         // yeninin next'i eski head

    if (*head != NULL) {
        (*head)->prev = yeni;   // eski head'in prev'i yeni düğüm ←
    }

    *head = yeni;               // head'i güncelle
    // yeni->prev zaten NULL (yeniDugum'da atandı)
}

Sona Eleman Ekleme

Sona ekleme için son düğüme ulaşmak gerekir. Son düğümün next'i yeni düğüme, yeni düğümün prev'i son düğüme bağlanır. Tail pointer tutuluyorsa bu işlem O(1), tutulmuyorsa O(n)'dir.

void sonaEkle(Node** head, int deger) {
    Node* yeni = yeniDugum(deger);

    if (*head == NULL) {
        *head = yeni;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    temp->next = yeni;    // son düğümün next'i → yeni
    yeni->prev = temp;    // yeninin prev'i ← son düğüm
}

Araya Eleman Ekleme

Belirli bir pozisyona eleman eklemek, tek yönlüye göre biraz daha fazla pointer işlemi gerektirir. Önceki ve sonraki düğümlerin hem next hem prev bağlantıları güncellenmelidir. Toplamda 4 pointer işlemi yapılır.

void pozisyonaEkle(Node** head, int pozisyon, int deger) {
    if (pozisyon == 0) {
        basaEkle(head, deger);
        return;
    }

    Node* yeni = yeniDugum(deger);
    Node* temp = *head;

    // Hedef pozisyonun bir öncesine git
    for (int i = 0; i < pozisyon - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Geçersiz pozisyon!\n");
        free(yeni);
        return;
    }

    // 4 bağlantıyı kur
    yeni->next = temp->next;       // ❶ yeninin next'i → sonraki
    yeni->prev = temp;             // ❷ yeninin prev'i ← önceki

    if (temp->next != NULL) {
        temp->next->prev = yeni;   // ❸ sonrakinin prev'i ← yeni
    }

    temp->next = yeni;             // ❹ öncekinin next'i → yeni
}

Baştan Silme

Baştan silme O(1) karmaşıklığındadır. Head bir sonraki düğüme kaydırılır ve yeni head'in prev'i NULL yapılır. Eski head free() ile serbest bırakılır.

void bastanSil(Node** head) {
    if (*head == NULL) {
        printf("Liste boş!\n");
        return;
    }

    Node* silinecek = *head;
    *head = (*head)->next;      // head'i ilerlet

    if (*head != NULL) {
        (*head)->prev = NULL;   // yeni head'in prev'ini temizle
    }

    free(silinecek);
}

Sondan Silme

İşte çift yönlü listenin tek yönlüye göre en büyük avantajı burada ortaya çıkar. Tek yönlü listede sondan silme O(n) idi çünkü sondan bir önceki düğüme ulaşmak için baştan yürümek gerekiyordu. Çift yönlü listede son düğümün prev pointer'ı zaten bir öncekini gösterir, bu yüzden düğüme doğrudan erişiminiz varsa silme O(1)'dir.

void sondanSil(Node** head) {
    if (*head == NULL) {
        printf("Liste boş!\n");
        return;
    }

    // Tek eleman varsa
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }

    // Son düğüme git
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    temp->prev->next = NULL;  // bir öncekinin next'i = NULL
    free(temp);
}

Belirli Düğümü Silme

Çift yönlü listenin en güçlü özelliği budur: herhangi bir düğümün pointer'ına sahipseniz, o düğümü O(1)'de silebilirsiniz. Tek yönlü listede bir önceki düğümü bulmak için baştan yürümek gerekiyordu, çift yönlüde ise silinecek->prev zaten bir öncekini verir.

void degereSil(Node** head, int deger) {
    if (*head == NULL) return;

    Node* temp = *head;

    // Silinecek düğümü bul
    while (temp != NULL && temp->data != deger) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("%d bulunamadı!\n", deger);
        return;
    }

    // Head siliniyorsa
    if (temp == *head) {
        *head = temp->next;
    }

    // Önceki düğümün next'ini güncelle
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }

    // Sonraki düğümün prev'ini güncelle
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }

    free(temp);
}

// Düğüm pointer'ına doğrudan erişim varsa O(1) silme:
void dugumSil(Node** head, Node* silinecek) {
    if (*head == NULL || silinecek == NULL) return;

    if (silinecek == *head)
        *head = silinecek->next;

    if (silinecek->prev != NULL)
        silinecek->prev->next = silinecek->next;

    if (silinecek->next != NULL)
        silinecek->next->prev = silinecek->prev;

    free(silinecek);
}

Eleman Arama

Eleman arama işlemi tek yönlü listedeki ile aynıdır: head'den başlayıp her düğümün verisini kontrol edersiniz. Çift yönlü olması arama hızını değiştirmez, karmaşıklık yine O(n)'dir. Ancak hem head hem tail pointer'ınız varsa, ilginç bir optimizasyon yapabilirsiniz: iki uçtan aynı anda arama başlatmak.

// Standart arama (tek yönlüyle aynı)
Node* elemanAra(Node* head, int aranan) {
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == aranan)
            return temp;   // düğüm pointer'ını döndür
        temp = temp->next;
    }
    return NULL;  // bulunamadı
}

// İki uçtan arama (head + tail varsa)
Node* ciftYonluAra(Node* head, Node* tail, int aranan) {
    Node* bas = head;
    Node* son = tail;

    while (bas != NULL && son != NULL) {
        if (bas->data == aranan) return bas;
        if (son->data == aranan) return son;

        // İki pointer birbirine ulaştıysa dur
        if (bas->next == son || bas == son) break;

        bas = bas->next;
        son = son->prev;
    }
    return NULL;
}

Çift Yönlü Liste Nerelerde Kullanılır?

Tarayıcı İleri-Geri Navigasyonu

Web tarayıcısında ziyaret ettiğiniz her sayfa çift yönlü bağlı listede bir düğümdür. "Geri" butonu current = current->prev, "İleri" butonu current = current->next işlemine karşılık gelir. Yeni bir sayfaya gitmek mevcut düğümden sonra ekleme yapar ve forward geçmişini temizler.

Undo/Redo Sistemi

Metin editörlerindeki geri alma (undo) ve yeniden yapma (redo) işlemleri çift yönlü liste ile modellenir. Her düğüm bir "durum" veya "aksiyon" temsil eder. Undo geri yürür, redo ileri yürür.

LRU Cache (Least Recently Used)

LRU cache, en az kullanılan veriyi çıkarmak için çift yönlü liste + hash table kombinasyonunu kullanır. Bir elemana erişildiğinde o düğüm O(1)'de listeden çıkarılır ve başa taşınır. Listenin sonundaki eleman en az kullanılandır ve kapasite dolduğunda silinir. Bu yapı işletim sistemlerinden veritabanlarına kadar her yerde kullanılır.

İşletim Sistemi Process Scheduler

Linux çekirdeğinde process listeleri çift yönlü bağlı listeler olarak tutulur. Process eklemek, silmek ve sıralama değiştirmek O(1)'de yapılabilir. Linux'un list_head yapısı çift yönlü dairesel bağlı listedir.

Müzik Çalar / Medya Oynatıcı

"Önceki şarkı" ve "Sonraki şarkı" butonları doğrudan prev ve next pointer'larıyla çalışır. Çalma listesinde şarkı ekleme, silme ve sıra değiştirme O(1) pointer operasyonlarıyla gerçekleşir.

Zaman Karmaşıklığı Karşılaştırma

Sık Yapılan Hatalar

1. Tek Yönlü Bağlantı Kurma

En yaygın hata, A->next = B yazıp B->prev = A yazmayı unutmaktır. İleri traverse düzgün çalışır ama geri traverse yanlış sonuçlar verir. Her bağlantı işleminde kendinize sorun: "İki yönlü bağlantıyı kurduk mu?"

2. NULL Kontrolü Atlama

Head veya tail düğümlerini silerken veya eklerken, komşu düğümün NULL olup olmadığını kontrol etmek zorunludur. Aksi halde NULL pointer üzerinde ->prev veya ->next erişimi programı çökertir.

// ❌ YANLIŞ: NULL kontrolü yok
temp->next->prev = yeni;   // temp->next NULL ise ÇÖKME!

// ✅ DOĞRU: Önce kontrol et
if (temp->next != NULL) {
    temp->next->prev = yeni;
}

3. Silme Sırasında Pointer Sırasını Bozma

Bir düğümü silerken önce komşu bağlantıları güncelleyin, sonra free() çağrın. free() çağrıldıktan sonra o düğümün prev ve next değerlerine erişmek tanımsız davranıştır.

Sonuç

Çift yönlü bağlı liste, tek yönlüye kıyasla ekstra bir pointer maliyeti karşılığında önemli avantajlar sunar. Sondan silme, belirli düğümü doğrudan silme ve geri dolaşma gibi operasyonlar O(1)'e düşer. Bu avantajlar LRU cache, tarayıcı geçmişi ve undo/redo gibi gerçek dünya uygulamalarında çift yönlü listeyi vazgeçilmez kılar.

Çift yönlü listenin en kritik kuralı şudur: her bağlantı çift yönlü olmalıdır. Bu kuralı otomatik bir refleks haline getirmek, birçok hatayı önler. Bir sonraki bölümde dairesel bağlı listeleri (circular linked list) inceleyeceğiz. Dairesel listelerde son düğüm NULL yerine ilk düğüme bağlanır ve bu sayede döngüsel yapılar (round-robin zamanlama, döngüsel çalma listesi) verimli bir şekilde modellenebilir.