Tek Yönlü Bağlı Listelerde Araya Eleman Ekleme

Tek yönlü bağlı listelerde araya eleman ekleme işlemi (Linked List Add Anywhere) başa eleman ekleme ve sona eleman ekleme olmayan tüm durumları kapsar. Tabii burada kriterin belirlenmesi gerekli. Örneğin belirli bir elemanın önüne ya da sonrasına eleman eklemek istediğinizi belirleyebilirsiniz. Bu durum tamamen tercihinize kalmıştır. Esas önemli olan kısım burada doğru noktaya Traverse işlemi gerçekleştirmektir. Çünkü tek yönlü bağlı listede bir elemanın önüne ve arkasına eleman eklemek farklı süreçlerdir. Biz bu makalede Tek Yönlü bağlı listelerde araya ekleme işlemi için iki durumu da inceleyeceğiz.

Eklenecek Konumu Belirleme

Herhangi bir yere ya da araya eleman ekleme işleminde kritik nokta, nereye eleman ekleneceğinin belirlenmesidir. Genelde belirli bir düğümün önüne ya da ardına eklenmesi gerektiği söylenir. Bu da traverse mantığında değişikliğe sebep olmaktadır.

Biz bu yazı dahilinde iki durumu da ele alacağız. Aklınıza şu soru gelebilir. Neden bağlı listelerde araya eleman ekleme işlemi özel bir durum ele alınmaktadır? Çünkü önüne eklenen, ve öncesine eklenen düğümler arasındaki bağ kırılmaktadır. Bu durumdan ötürü, bu kırılan bağların yerine yeni bağ kurulmalıdır.

Yukarıdaki resimde de görebileceğiniz üzere, A,B,D ve E düğümlerinden oluşan tek yönlü bağlı listedeki B Düğümünün önüne C düğümünü eklemeye kalktığımız zaman artık B Düğümü D Düğümünü değil, C Düğümünü işaret etmelidir, yani bir güncelleme işlemi yapmalıdır. C Düğümünün işaretçisi ise D düğümünü işaret etmelidir.

Araya Eleman Ekleme C Kodu (Önüne)

Bu işlemin kodunu yazacak olursak, öncelikli olarak önüne eleman eklenecek olan düğüme kadar traverse yapmamız gerekecektir. Burada traverse şartını buna göre yazmamız gerekiyor.

void addAfter(int after, struct node* tobeAdd) {
    struct node* temp = start;

    while(temp != NULL && temp->data != after) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Hata: Belirtilen eleman bulunamadi.\n");
        return;
    }

    struct node* store = temp->next;
    temp->next = tobeAdd;
    tobeAdd->next = store;
}

kodu açıklamak gerekirse, bir tane geçici bir değişken (temp) oluşturup başlangıç düğümünden başlıyoruz. Traverse yaptığımız döngü (while döngüsü) burada önemli bir noktayı işaret ediyor. Eğer verilen bir düğümün önüne (İngilizce olarak arama yapmak isterseniz Head Of diye aratabilirsiniz) eleman eklenecekse, şart temp->data != after olarak belirtilmelidir. Bu döngü sayesinde temp değeri after değerine gelmiş olur. Böylece, elimizdeki mevcut düğümün sonraki işaretçisini güncelleriz. Tabii öncelikle, önüne eleman eklenecek olan düğümün işaret ettiği düğümü saklıyoruz. (struct node* store = temp->next;) Daha sonra, araya eleman ekleme işlemini gerçekleştiriyoruz. (temp->next = tobeAdd;), en son adımda da yeni eklenen düğümün, önceki işaret edilen düğüme yönlendiriyoruz. (tobeAdd->next = store;) Bu yapıyla birlikte bağlı liste yapısını bozmamış oluyoruz. Tabii ki hata kontrolleri bu basit fonksiyonda bulunmuyor.

Belirtilen Düğümün Öncesine Eleman Eklemek

Belirtilen düğümün öncesine eleman eklemek için traverse şartını değiştirmemiz yeterli. Bu durumda önceki düğümün bilgisini kaybetmemiz durumunda geri dönemeyeceğimizi bilmemiz gerekiyor. Çünkü tek yönlü bağlı listeler yalnızca ileri doğru gider, geriye dönemeyiz. Traverse fonksiyonu içerisinde bir önceki düğümü de saklayarak sorunu çözebiliriz.

void addBefore(int before, struct node* tobeAdd) {
    struct node* temp = start;
    struct node* prev = NULL;

    while(temp->data != before) {
        prev = temp;
        temp = temp->next;
    }

    if (prev == NULL) {
        // 'before' node is the first node
        tobeAdd->next = start;
        start = tobeAdd;
    } else {
        prev->next = tobeAdd;
        tobeAdd->next = temp;
    }
}