Sıralı Bağlı Liste (Öncelik Kuyruğu)

Bağlı listelere elemanları baştan veya sondan ekleyebilirsiniz. Bu sizin tasarladığınız liste ile ilgilidir. Ancak bu listede aramak yapmak veya listeyi sıralamak istediğiniz zaman işler biraz karışır çünkü bağlı listelerde doğrusal hareket edersiniz. Bundan dolayı her defasında bağlı listenin bir sonraki düğümüne ilerlersiniz.

Böyle bir duruma ilk baştan bir çözüm bulmak isterseniz imdadınıza Öncelik Kuyruğu (Priority queue) adı verilen teknik yetişir. Bu teknikte amaç, listeye elemanları eklerken listenin sıralı düzenini bozmadan bu eklemeyi yapmaktır. Böylece listeye tüm elemanları eklediğinizde elinizde sıralı bir liste olacaktır. Bununla ilgili örnek bir uygulamaya ait kodları aşağıya ekliyorum. Bu kodda rastgele 0-100 arasında oluşturulan 25 sayı bir bağlı listeye sıralı bir şekilde ekleniyor ve sonra bu sıralı liste ekrana yazdırılıyor. Sorularınız olursa yardımcı olmaya çalışırım. Tüm okuyucularıma sağlık ve mutluluk dilerim.

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

struct yiginDugumu {
    int                 data;
    struct yiginDugumu* sonraki;
};

void ListeyeEkle(struct yiginDugumu** ilkDugum, int data);

int main()
{
    struct yiginDugumu* basDugum = NULL;
    struct yiginDugumu* say;
    int i;

    srand(time(NULL));

    for (i=0; i<25; i++){
        ListeyeEkle(&basDugum, rand() % 99 +1);
    }

    for (i=0, say=basDugum; say != NULL; i++, say = say->sonraki) {
        printf("%d-> %d\n", i, say->data);
    }

    return 0;
}

void ListeyeEkle(struct yiginDugumu** ilkDugum, int data)
{
    struct yiginDugumu* gecerliDugum = *ilkDugum;
    struct yiginDugumu* yeniDugum;
    struct yiginDugumu* oncekiDugum = NULL;

    yeniDugum = malloc(sizeof(struct yiginDugumu));
    yeniDugum->data = data;
    yeniDugum->sonraki = NULL;

    while (gecerliDugum != NULL && gecerliDugum->data < data) {
        oncekiDugum = gecerliDugum;
        gecerliDugum = gecerliDugum->sonraki;
    }

    if (oncekiDugum == NULL) {
        *ilkDugum = yeniDugum;
    }
    else {
        oncekiDugum->sonraki = yeniDugum;
    }

    yeniDugum->sonraki = gecerliDugum;
}