Veri Yapıları ve Programlama

6 - Bağlı Listede Ekleme, Silme ve Arama

Emre Can Yılmaz

[email protected]

Ondokuz Mayıs Üniversitesi

2026

Bu Hafta: Bağlı Listede Temel İşlemler

Geçen hafta bağlı listenin temel yapısını görmüştük. Bu hafta, var olan bir bağlı liste üzerinde işlem yapmaya odaklanacağız.

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

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

Bu işlemleri tek yönlü bağlı liste üzerinde ele alacağız. Burada kurduğunuz mantık, daha sonra çift yönlü ve dairesel bağlı listeler için de temel oluşturur.

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.

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

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

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, bağlı listedeki birçok işlemin temel kalıbıdı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.

Arama (Search)

Arama, traversal mantığının özel bir kullanımından ibarettir.

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 en kötü durumda genellikle \(O(n)\) zaman alır.

Arama Sonucunu Kullanma

Arama çoğu zaman tek başına yapılmaz; bir sonraki işleme hazırlık için yapılır.

struct node *found = search(head, 2);

if (found != NULL) {
    printf("Dugum bulundu: %d\n", found->data);
}

Buradaki önemli fikir şudur:

• arama başarılıysa bir düğümün adresini elde ederiz,
• bu adres daha sonra insertAfter veya deleteAfter gibi işlemlerde kullanılabilir.

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.

Ekleme işlemine başlamadan önce şu üç noktayı düşünmek gerekir:

• Liste boş olabilir mi?
• Bu işlem head değerini değiştirebilir mi?
• Ekleme yapılacak konum gerçekten belli mi?

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.

Temel ayrım

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, bağlı listede neden bazen tail tutulduğunu 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 edilmesi 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.

Silme işlemine başlamadan önce yine şu noktaları kontrol etmek gerekir:

• Liste boş olabilir mi?
• Bu işlem head değerini değiştirebilir mi?
• Silinecek düğüm ya da onun öncesi gerçekten bulundu mu?

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);
}

Baştan Silme: Önce / Sonra

Önce:
head -> 1 -> 2 -> 3 -> NULL

temp = head
head = head->next
free(temp)

Sonra:
head -> 2 -> 3 -> NULL

Burada kritik nokta şudur: önce yeni head belirlenir, sonra eski baş düğüm serbest bırakılır.

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);
}

Sondan Silme: Önce / Sonra

Önce:
head -> 1 -> 2 -> 3 -> NULL

secondLast, 2 düğümünü gösterene kadar ilerler
temp = 3 düğümü
secondLast->next = NULL
free(temp)

Sonra:
head -> 1 -> 2 -> NULL

Neden son düğümü değil, bir önceki düğümü buluyoruz?

Tek yönlü bağlı listede her düğüm yalnızca kendisinden sonrakini bilir. Bu yüzden son düğümü listeden koparmak için, onun öncesindeki düğüme ulaşmamız gerekir.

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);
}

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.

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);
}

found = search(head, 2);
if (found != NULL) {
    deleteAfter(found);
}

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 mevcut düğümler üzerinden işlem yapar.

Zaman Karmaşıklığı Özeti

İşlem	Maliyet	Neden?
Gezme	\(O(n)\)	Tüm düğümler sırayla gezilebilir
Arama	\(O(n)\)	İstenen düğüm sonda olabilir
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

Bu tablo, bağlı listede doğrudan erişim olmamasının 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.

Bağlı liste sorularında asıl başarı, kodu ezberlemekten çok “hangi bağlantı şimdi değişecek?” sorusunu doğru cevaplamaktır.

Çalışma Soruları: Temel

• Başa ekleme, sona ekleme ve baştan silme işlemlerini kullanarak küçük bir bağlı liste oluşturun.
• Bir bağlı listede verilen değeri arayan ve düğüm bulunduysa adresini döndüren bir fonksiyon yazın.
• Bir bağlı listedeki eleman sayısını bulan bir fonksiyon yazın.
• Bir bağlı listeyi ekrana düzgün biçimde yazdıran bir fonksiyon yazın.

Çalışma Soruları: Bir Sonraki Adım

• 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ş halini oluşturan bir fonksiyon yazın.
• Aynı ters çevirme işlemini recursive olarak da yazmayı deneyin.
• Bir bağlı listenin döngüsel (circular) olup olmadığını kontrol eden bir fonksiyon yazın.
• Aynı temel işlemleri çift yönlü bağlı liste için uyarlayın.