Veri Yapıları ve Programlama

6 - Bağlı Liste İşlemleri

Emre Can Yılmaz

[email protected]

Ondokuz Mayıs Üniversitesi

2025

Bağlı Liste İşlemleri - Giriş

Geçen hafta bağlı listelerin ne olduğunu, türlerini ve temel yapısını öğrendik. Bu hafta, bağlı listeler üzerinde gerçekleştirebileceğimiz temel işlemleri inceleyeceğiz:

• Gezme (Traversal)
• Ekleme (Insertion)
  • Başa Ekleme
  • Sona Ekleme
  • Araya Ekleme
• Silme (Deletion)
  • Baştan Silme
  • Sondan Silme
  • Aradan Silme
• Arama (Search)

Bu işlemler, tek yönlü bağlı listeler üzerinde gösterilecek, ancak temel prensipler diğer türler için de geçerlidir.

Bağlı Liste Hakkında Hatırlanması Gerekenler

• head, bağlı listenin ilk düğümüne işaret eder.
• next, son düğümün işaret ettiği adres NULL’dur, bu nedenle bir sonraki geçerli düğüm NULL ise, bağlı listenin sonuna ulaşmış oluruz.

Tüm örneklerde, bağlı listenin aşağıdaki gibi düğüm yapısına sahip üç düğüm 1 ---> 2 ---> 3 olduğunu varsayacağız:

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

Bağlı Listeyi Gezme (Traversal)

• Bağlı listenin tüm elemanlarını ziyaret etme işlemidir.
• head’den başlayarak, her düğümün next işaretçisini takip ederek son düğüme (NULL işaretçisine sahip olan) kadar ilerleriz.

Gerçekleme

void printList(struct node *head) {
    struct node *temp = head;
    printf("Liste: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

Kullanımı

  printList(head); // Listeyi yazdırma

Eleman Ekleme (Insertion)

1. Başa Ekleme

Yeni bir düğüm oluşturulur ve listenin başına eklenir. head işaretçisi güncellenir.

1. Yeni düğüm için bellek ayır.
2. Yeni düğümün data alanına veriyi ata.
3. Yeni düğümün next işaretçisini, mevcut head’i gösterecek şekilde ayarla.
4. head işaretçisini yeni düğümü gösterecek şekilde güncelle.

Gerçekleme

void insertAtBeginning(struct node **headRef, int newData) {
    // 1. Yeni düğüm için bellek ayır
    struct node *newNode = malloc(sizeof(struct node));

    // 2. Veriyi ata
    newNode->data = newData;

    // 3. Yeni düğümün next'i eski head olsun
    newNode->next = *headRef;

    // 4. head'i yeni düğüme güncelle
    *headRef = newNode;
}

Kullanımı

    insertAtBeginning(&head, 4); // Başa 4 ekle
    printList(head);

İşaretçinin İşaretçisi

head değişkeninin kendisini değiştirebilmek için, head’in adresini fonksiyona geçirmemiz gerekiyor. İşte bu yüzden struct node **headRef kullanıyoruz. headRef, head işaretçisinin adresini tutan bir işaretçi (pointer to a pointer).

• headRef: head’in adresini tutan değişken.
• *headRef: headRef’in gösterdiği adresteki değer, yani head’in kendisi.
• **headRef: *headRef in değeri olan head’ın gösterdiği değeri ifade eder.

Fonksiyon içinde *headRef = newNode; yaptığımızda, aslında şunu demiş oluyoruz: “headRef’in gösterdiği adrese (yani head’in kendisine) newNode’un adresini ata.” Bu sayede, main fonksiyonundaki orijinal head değişkeni de güncellenmiş oluyor.

2. Sona Ekleme

Yeni bir düğüm oluşturulur ve listenin sonuna eklenir.

1. Yeni düğüm için bellek ayır.
2. Yeni düğümün data alanına veriyi ata.
3. Yeni düğümün next işaretçisini NULL yap (çünkü son düğüm olacak).
4. Eğer liste boşsa (head NULL ise), head’i yeni düğüm yap ve fonksiyondan çık.
5. Liste boş değilse, son düğüme kadar ilerle (next’i NULL olan düğüm).
6. Son düğümün next işaretçisini yeni düğümü gösterecek şekilde ayarla.

Gerçekleme

void insertAtEnd(struct node **headRef, int newData) {
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = newData;
    newNode->next = NULL;

    if (*headRef == NULL) { // Liste boşsa
        *headRef = newNode;
        return;
    }

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

Kullanımı

    insertAtEnd(&head, 5); // Sona 5 ekle
    printList(head);

3. Araya Ekleme

Yeni bir düğüm, listede belirli bir konumdan sonraya eklenir.

1. Yeni düğüm için bellek ayır.
2. Yeni düğümün data alanına veriyi ata.
3. Yeni düğümün ekleneceği konumdan önceki düğüme kadar ilerle (bu düğüme prevNode diyelim).
4. Eğer prevNode NULL ise, bu konuma ekleme yapılamaz (hata mesajı verilebilir veya başa ekleme yapılabilir), fonksiyondan çık.
5. Yeni düğümün next işaretçisini, prevNode’un next’ini gösterecek şekilde ayarla.
6. prevNode’un next işaretçisini yeni düğümü gösterecek şekilde ayarla.

Gerçekleme

void insertAfter(struct node *prevNode, int newData) {
    if (prevNode == NULL) {
        printf("Önceki düğüm NULL olamaz.\n");
        return;
    }
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = newData;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

Kullanımı

    insertAfter(two, 6); // 'two' düğümünden sonra 6 ekle
    printList(head);

Eleman Silme (Deletion)

1. Baştan Silme

Listenin başındaki düğüm silinir. head işaretçisi güncellenir.

1. Eğer liste boşsa (head NULL ise), yapılacak bir şey yok, fonksiyondan çık.
2. head’i geçici bir değişkende sakla (temp).
3. head’i, head’in next’ine eşitle (yani bir sonraki düğüme).
4. temp’i serbest bırak (free).

Gerçekleme

void deleteFromBeginning(struct node **headRef) {
    if (*headRef == NULL) {
        return; // Liste boş
    }
    struct node *temp = *headRef;
    *headRef = (*headRef)->next;
    free(temp);
}

Kullanımı

    deleteFromBeginning(&head); // Baştan sil
    printList(head);

2. Sondan Silme

Listenin sonundaki düğüm silinir.

1. Eğer liste boşsa, yapılacak bir şey yok, fonksiyondan çık.
2. Eğer listede tek eleman varsa (head->next NULL ise), head’i NULL yap, düğümü serbest bırak ve fonksiyondan çık.
3. Sondan bir önceki düğüme kadar ilerle (secondLast).
4. Son düğümü (secondLast->next) geçici bir değişkende sakla (temp).
5. secondLast->next’i NULL yap.
6. temp’i serbest bırak.

Gerçekleme

void deleteFromEnd(struct node **headRef) {
    if (*headRef == NULL) {
        return; // Liste boş
    }
    if ((*headRef)->next == NULL) { // Tek eleman
        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);
}

Kullanımı

    deleteFromEnd(&head); // Sondan sil
    printList(head);

3. Aradan Silme

Belirli bir düğüm (ne baş ne de son) listeden silinir.

1. Silinecek düğümün önceki düğümüne kadar ilerle (prevNode).
2. Eğer prevNode veya prevNode->next NULL ise, silme yapılamaz (hata mesajı ver), fonksiyondan çık.
3. Silinecek düğümü (prevNode->next) geçici bir değişkende sakla (temp).
4. prevNode->next’i, temp->next’e eşitle (yani silinecek düğümü atla).
5. temp’i serbest bırak.

Gerçekleme

void deleteNode(struct node **headRef, struct node *prevNode)
{
    if(prevNode == NULL || prevNode->next == NULL)
    {
        printf("Silinecek elemanın öncesi veya silinecek eleman yok.\n");
        return;
    }

    struct node *temp = prevNode->next; //Silinecek eleman
    prevNode->next = temp->next; //Önceki elemanın next'i, silinecek elemanın next'i yapılıyor.
    free(temp); //Silinecek eleman siliniyor.

}

Kullanımı

Önce two’yu bulup, sonra silmek için one’ı (önceki düğüm) parametre olarak vermeliyiz.

    //Önce arama yaparak 'two' düğümünün adresini bulmalıyız.
    deleteNode(&head, one); //'one' düğümünden sonrasını, yani 'two'yu sil
    printList(head);

Arama (Search)

Belirli bir veriyi içeren düğümü bulma işlemidir.

1. head’den başla.
2. Her düğümdeki data’yı aranan veriyle (key) karşılaştır.
3. Eşleşme bulunursa, düğümün adresini döndür.
4. Sona gelinirse (NULL) ve eşleşme bulunamazsa, NULL döndü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;
}

Kullanımı

    struct node *found = search(head, 2); // 2'yi ara
    if (found != NULL) {
        printf("Buldum! Adres: %p, Deger: %d\n", found, found->data);
    } else {
        printf("Bulunamadı.\n");
    }

Özet

• Bağlı liste işlemleri: Gezme, ekleme (başa, sona, araya), silme (baştan, sondan, aradan) ve arama.
• Her işlemin nasıl çalıştığını adım adım ve kod örnekleriyle gördük.
• Bu temel işlemler, bağlı listelerle çalışmanın temelini oluşturur. Daha karmaşık algoritmalar ve veri yapıları bu işlemler üzerine kurulur.

Ç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).
• Bağlı listeler, döngüsel (circular) olup olmadığını kontrol eden bir fonksiyon yazın.