Veri Yapıları ve Programlama

6 - Bağlı Liste İşlemleri

Emre Can Yılmaz

emrecan@omu.edu.tr

Ondokuz Mayıs Üniversitesi

2026

Bağlı Liste İşlemleri - Giriş

Geçen hafta bağlı listenin ne olduğunu, neden diziye alternatif olduğunu ve düğümlerin işaretçilerle bağlandığını gördük. Bu hafta odağımız şudur:

• var olan bir liste üzerinde güvenli işlem yapmak,
• bağlantıları bozmadan düğüm eklemek ve silmek,
• her işlemde hangi kenar durumlarının kontrol edilmesi gerektiğini anlamak.

Bu işlemleri tek yönlü bağlı liste üzerinde göstereceğiz. Öğrendiğiniz mantık, çift yönlü ve dairesel listelere de temel oluşturur.

Bu Derste Ne Öğreneceğiz?

Bu dersin sonunda şunları yapabiliyor olmanız beklenir:

• bağlı listede gezme, ekleme, silme ve arama işlemlerini açıklamak,
• bir işlem sırasında head’in değişip değişmeyeceğini yorumlamak,
• hangi fonksiyonlarda işaretçinin işaretçisinin gerekli olduğunu ayırt etmek,
• boş liste, tek elemanlı liste ve son düğüm gibi kenar durumlarını fark etmek,
• temel işlemlerin neden çoğunlukla \(O(n)\) veya \(O(1)\) olduğunu yorumlamak.

Geçen Haftalardan Bu Haftaya Köprü

Bu haftayı anlamak için iki önceki dersin fikrini birleştiriyoruz:

• 4. hafta: malloc ile heap’te bellek ayırıyor, işimiz bitince free ile geri veriyoruz.
• 5. hafta: bağlı listede veriye indeksle değil, next bağlantılarını takip ederek ulaşıyoruz.

Bu yüzden bu haftanın ana sorusu şudur:

Bir düğümün bağlantısını kaybetmeden listeyi nasıl değiştiririz?

Hatırlanması Gereken Temel Yapı

• head, bağlı listenin ilk düğümünü gösterir.
• Son düğümün next alanı NULL olur.
• head == NULL ise liste boştur.

Not

Bu dersteki kod parçaları kavramı göstermek için sadeleştirilmiştir. Kodları doğrudan derlemek istediğinizde uygun yerlerde stdio.h, stdlib.h ve main fonksiyonu eklemeyi unutmayın.

struct node {
    int data;
    struct node *next;
};

Bu derste örnek başlangıç durumunu çoğu zaman şöyle düşüneceğiz:

head -> 1 -> 2 -> 3 -> NULL

İşleme Başlamadan Önce Sorulacak 3 Soru

Bir bağlı liste işlemini ezberlemek yerine önce şu üç soruyu sorun:

1. Liste boş olabilir mi?
2. Bu işlem head değerini değiştirebilir mi?
3. Bağlantıyı değiştirmeden önce gerekli düğümü gerçekten buldum mu?

Bu üç soru, haftanın neredeyse tüm kodlarını anlamanızı sağlar.

Bağlı Listeyi Gezme (Traversal)

• Amaç: listedeki tüm düğümleri sırayla ziyaret etmek.
• Başlangıç noktası her zaman head’dir.
• Durma koşulu NULL’a ulaşmaktır.

Traversal, sonraki haftalarda göreceğiniz birçok işlem için temel kalıptır; çünkü arama, sona ekleme ve sondan silme gibi işlemler çoğu zaman önce dolaşmayı gerektirir.

Gerçekleme

void printList(struct node *head) {
    struct node *current = head;

    printf("Liste: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

Gezme İşleminin Mantığı

Basit gezme işleminde liste yapısını değiştirmeyiz; bu yüzden doğrudan head üzerinde ilerlemek yerine genellikle geçici bir işaretçi kullanırız.

Neden temp veya current kullanıyoruz?

head ilk düğümü göstermeye devam etmelidir. Eğer doğrudan head = head->next yaparsanız, listenin başlangıcını kaybedersiniz.

Tam dolaşım yapıldığında bütün düğümler tek tek ziyaret edildiği için maliyet genellikle \(O(n)\) olur.

Eleman Ekleme İçin Genel Mantık

Ekleme işlemlerinde temel düşünce aynıdır:

1. Yeni düğüm için bellek ayır.
2. Veriyi yerleştir.
3. Yeni düğümün bağlantısını doğru yere kur.
4. Gerekirse eski düğümün veya head’in bağlantısını güncelle.

Burada en kritik nokta şudur:

Bağlantıyı yanlış sırada değiştirirseniz listenin bir kısmını kaybedebilirsiniz.

1. Başa Ekleme

Başa ekleme, bağlı listede en sezgisel ve en verimli işlemlerden biridir.

1. Yeni düğüm oluşturulur.
2. newNode->next, eski head’i gösterecek şekilde ayarlanır.
3. head, yeni düğümü gösterecek şekilde güncellenir.

Bu işlemde listenin geri kalanını aramamız gerekmez.

Gerçekleme

void insertAtBeginning(struct node **headRef, int newData) {
    struct node *newNode = malloc(sizeof *newNode);

    if (newNode == NULL) {
        printf("Bellek ayirma basarisiz.\n");
        return;
    }

    newNode->data = newData;
    newNode->next = *headRef;
    *headRef = newNode;
}

Neden struct node **headRef Kullanıyoruz?

Başa ekleme ve baştan silme gibi işlemler, head değişkeninin kendisini değiştirebilir. Bu nedenle fonksiyona yalnızca head’in değeri değil, head’in adresi gönderilir.

• headRef: head değişkeninin adresi
• *headRef: gerçek head değeri

Fonksiyon içinde *headRef = newNode; dediğimizde, çağıran koddaki gerçek head güncellenmiş olur.

Karşılaştırma

Sadece mevcut bir düğümün sonrasını değiştiriyorsak çoğu zaman struct node ** gerekmez. Ama head değişebiliyorsa genellikle gerekir.

2. Sona Ekleme

Yeni düğümü listenin en sonuna eklemek için önce son düğümü bulmamız gerekir.

1. Yeni düğüm oluşturulur.
2. next alanı NULL yapılır.
3. Liste boşsa, yeni düğüm doğrudan head olur.
4. Liste boş değilse, son düğüme kadar ilerlenir.
5. Son düğümün next alanı yeni düğümü gösterecek şekilde ayarlanır.

Gerçekleme

void insertAtEnd(struct node **headRef, int newData) {
    struct node *newNode = malloc(sizeof *newNode);

    if (newNode == NULL) {
        printf("Bellek ayirma basarisiz.\n");
        return;
    }

    newNode->data = newData;
    newNode->next = NULL;

    if (*headRef == NULL) {
        *headRef = newNode;
        return;
    }

    struct node *last = *headRef;
    while (last->next != NULL) {
        last = last->next;
    }

    last->next = newNode;
}

Başa Ekleme ile Sona Ekleme Arasındaki Fark

• Başa ekleme için arama gerekmez, genellikle \(O(1)\)’dir.
• Sona ekleme, tail tutulmuyorsa son düğümü aramayı gerektirir; bu yüzden çoğu zaman \(O(n)\)’dir.

Bu karşılaştırma, geçen haftaki “neden bazen tail tutulur?” sorusunu da açıklar.

3. Araya Ekleme (Verilen Düğümden Sonra)

Bu işlem aslında “belirli bir düğümden sonra ekleme” işlemidir. Dolayısıyla kritik bilgi, ekleme yapılacak yerin önceki düğümünü bilmektir.

1. Önceki düğümün geçerli olup olmadığı kontrol edilir.
2. Yeni düğüm oluşturulur.
3. Yeni düğümün next alanı, önceki düğümün eski next değerine bağlanır.
4. Önceki düğümün next alanı yeni düğüme çevrilir.

Sıra önemlidir: önce yeni düğümün bağlantısı kurulur, sonra eski düğüm yeni düğüme bağlanır.

Önemli nüans: prevNode zaten biliniyorsa bu bağlantı güncellemesi genellikle \(O(1)\)’dir. Ama önce uygun düğümü aramak gerekiyorsa toplam maliyet çoğu zaman \(O(n)\) olur.

Gerçekleme

void insertAfter(struct node *prevNode, int newData) {
    if (prevNode == NULL) {
        printf("Onceki dugum NULL olamaz.\n");
        return;
    }

    struct node *newNode = malloc(sizeof *newNode);
    if (newNode == NULL) {
        printf("Bellek ayirma basarisiz.\n");
        return;
    }

    newNode->data = newData;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

Elle İzleme: insertAfter

Başlangıç durumu:

head -> 1 -> 2 -> 3 -> NULL

found = search(head, 2) ise found, değeri 2 olan düğümü gösterir.

insertAfter(found, 99) sonrasında:

head -> 1 -> 2 -> 99 -> 3 -> NULL

Burada yapılan şey yeni düğümü “2 ile 3 arasına” eklemektir.Dikkat etmeniz gereken asıl nokta, 2 düğümünün eski next bilgisinin kaybedilmeden önce 99 düğümüne aktarılmasıdır.

Eleman Silme İçin Genel Mantık

Silme, eklemeden biraz daha risklidir; çünkü yanlış sırada işlem yaparsanız hem düğümü hem de bağlantıyı kaybedebilirsiniz.

Silmede tipik düşünce şudur:

1. Silinecek düğümü veya onun öncesini bul.
2. Gerekli bağlantıyı güncelle.
3. Düğümü free ile serbest bırak.

Kritik kural

free ettikten sonra o düğüme tekrar erişmeye çalışmayın. O bellek artık programınıza ait değildir.

1. Baştan Silme

Baştaki düğümü silmek için head değişeceği için yine işaretçinin işaretçisine ihtiyaç duyarız.

1. Liste boşsa işlem yapılmaz.
2. Eski baş düğüm geçici değişkende tutulur.
3. head, bir sonraki düğümü gösterecek şekilde güncellenir.
4. Eski baş düğüm free edilir.

Gerçekleme

void deleteFromBeginning(struct node **headRef) {
    if (*headRef == NULL) {
        return;
    }

    struct node *temp = *headRef;
    *headRef = (*headRef)->next;
    free(temp);
}

2. Sondan Silme

Tek yönlü listede son düğümü silmek için son düğümün bir öncesine kadar gitmemiz gerekir.

1. Liste boşsa çık.
2. Tek eleman varsa onu serbest bırak ve head = NULL yap.
3. Sondan bir önceki düğüme kadar ilerle.
4. Son düğümü geçici değişkende tut.
5. Önceki düğümün next alanını NULL yap.
6. Son düğümü free et.

Gerçekleme

void deleteFromEnd(struct node **headRef) {
    if (*headRef == NULL) {
        return;
    }

    if ((*headRef)->next == NULL) {
        free(*headRef);
        *headRef = NULL;
        return;
    }

    struct node *secondLast = *headRef;
    while (secondLast->next->next != NULL) {
        secondLast = secondLast->next;
    }

    struct node *temp = secondLast->next;
    secondLast->next = NULL;
    free(temp);
}

3. Aradan Silme (Verilen Düğümden Sonrakini Silme)

Tek yönlü listede aradan silme işlemi de çoğu zaman silinecek düğümün önceki düğümünü bilmeyi gerektirir.

Bu yüzden aşağıdaki fonksiyonun adı özellikle deleteAfter seçildi; çünkü fonksiyon doğrudan verilen düğümden sonraki düğümü siler.

Önemli nüans: önceki düğüm zaten elinizdeyse silme bağlantısı genellikle \(O(1)\)’dir. Ama o düğümü bulmak için listeyi dolaşmanız gerekiyorsa toplam maliyet çoğu zaman \(O(n)\) olur.

Gerçekleme

void deleteAfter(struct node *prevNode) {
    if (prevNode == NULL || prevNode->next == NULL) {
        printf("Silinecek dugum bulunamadi.\n");
        return;
    }

    struct node *temp = prevNode->next;
    prevNode->next = temp->next;
    free(temp);
}

Neden adı değişti?

Önceki haliyle fonksiyon adı deleteNode idi; ancak aslında herhangi bir düğümü değil, yalnızca verilen düğümün sonrasındaki düğümü siliyordu.

Elle İzleme: deleteAfter

Başlangıç durumu:

head -> 1 -> 2 -> 99 -> 3 -> NULL

found = search(head, 2) ise found, değeri 2 olan düğümü gösterir.

deleteAfter(found) sonrasında:

head -> 1 -> 2 -> 3 -> NULL

Bu işlemde 2 düğümünün next alanı, doğrudan 3 düğümünü gösterecek şekilde güncellenir; sonra aradaki düğüm free edilir.

Arama (Search)

Arama, geçen haftadaki temel fikirle tamamen aynıdır: düğümleri sırayla dolaşırız.

1. head’den başlanır.
2. Her düğümdeki veri key ile karşılaştırılır.
3. Eşleşme varsa düğümün adresi döndürülür.
4. Liste bitene kadar eşleşme yoksa NULL döndürülür.

Gerçekleme

struct node *search(struct node *head, int key) {
    struct node *current = head;

    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }

    return NULL;
}

Arama, istenen düğüm sonda olabilir diye genellikle en kötü durumda \(O(n)\) zaman alır.

Kullanım Mantığı: Hangi Fonksiyon Ne Bekliyor?

Bazen insertAfter veya deleteAfter gibi işlemlerden önce uygun düğümü bulmak için arama yaparız.

insertAtBeginning(&head, 4);
insertAtEnd(&head, 5);

struct node *found = search(head, 2);
if (found != NULL) {
    insertAfter(found, 6);
}

deleteFromBeginning(&head);
deleteFromEnd(&head);

Bu örnekler, iki tür parametre farkını netleştirir:

• &head: fonksiyon head’i değiştirebilir.
• head veya found: fonksiyon sadece mevcut düğümler üzerinden işlem yapar.

Zaman Karmaşıklığı Özeti

İşlem	Maliyet	Neden?
Gezme	\(O(n)\)	Tüm düğümler sırayla gezilebilir
Başa ekleme	\(O(1)\)	Doğrudan head üzerinden yapılır
Sona ekleme	\(O(n)\)	tail yoksa son düğüm aranır
Baştan silme	\(O(1)\)	Sadece head güncellenir
Sondan silme	\(O(n)\)	Sondan bir önceki düğüm aranır
insertAfter / deleteAfter	\(O(1)\) veya \(O(n)\)	Önceki düğüm biliniyorsa \(O(1)\), aranıyorsa toplam maliyet artar
Arama	\(O(n)\)	İndeksle doğrudan erişim yok

Bu tablo, geçen haftaki “bağlı listede doğrudan erişim yok” bilgisinin doğal sonucudur.

Sık Yapılan Hatalar

• malloc sonucunu kontrol etmeden alanı kullanmak
• boş liste durumunu unutarak head->next erişimi yapmak
• head değişmesi gereken yerde sadece head kopyasıyla işlem yapmak
• bağlantıyı yanlış sırada değiştirip listenin devamını kaybetmek
• free edilen düğümü tekrar kullanmak
• fonksiyon adından beklenen davranış ile gerçek davranışın uyuşmaması

Özet

• Bu hafta bağlı listede temel işlemlerin yalnızca kodunu değil, karar mantığını gördük.
• Temel ayrım şudur: işlem head’i değiştiriyorsa çoğu zaman struct node ** gerekir.
• Ekleme ve silmede asıl mesele doğru bağlantıyı doğru sırayla güncellemektir.
• Traversal ve search işlemleri, bağlı listede indeks olmadığı için çoğunlukla \(O(n)\)’dir.
• Bu temel işlemler, bağlı listelerle çalışmanın temelini oluşturur.

Bir sonraki adımda, bu işlemleri tek tek ezberlemek yerine küçük izleme örnekleri üzerinde elle yürütmek en etkili öğrenme yöntemi olacaktır.

Çalışma Soruları

• Çift yönlü bağlı liste üzerinde ekleme, silme ve arama işlemlerini kodlayın.
• Bir bağlı listede tekrar eden elemanları bulan ve silen bir fonksiyon yazın.
• İki bağlı listeyi birleştiren (concatenation) bir fonksiyon yazın.
• Bir bağlı listenin ters çevrilmiş (reversed) halini oluşturan bir fonksiyon yazın (hem iterative hem de recursive olarak).
• Bir bağlı listenin döngüsel (circular) olup olmadığını kontrol eden bir fonksiyon yazın.