Dairesel Bağlantılı Liste: Avantajları ve Dezavantajları

Dairesel Bağlantılı Liste Nedir?

Dairesel bağlantılı liste, her düğümün yeniden bağlanabileceği şekilde düzenlenmiş bir düğüm dizisidir.tracKendi kendine referans veren bir öğedir. Her "düğüm", yakın çevresindeki bir veya iki düğüme işaretçi içeren, kendi kendine referans veren bir öğedir.

Aşağıda 3 düğümlü dairesel bağlantılı bir listenin gösterimi bulunmaktadır.

Burada, her düğümün yeniden oluşturulduğunu görebilirsiniz.tracKendi kendine yetebilir. Yukarıda gösterilen örnek, dairesel tek yönlü bağlantılı bir listedir.

Not: En basit dairesel bağlantılı liste, bir sonraki işaretçisi olan tek bir düğümden oluşur. tracAşağıda gösterildiği gibi, kendi haline geri döner.

Temel OperaDairesel Bağlantılı Listelerdeki Bağlantılar

Dairesel bağlantılı listeler üzerinde gerçekleştirilebilecek üç temel işlem şunlardır:

1. sokma
2. Silme ve
3. Geçişi

• Ekleme, bir düğümü dairesel bağlantılı listede belirli bir konuma yerleştirme işlemidir.
• Silme, mevcut bir düğümün bağlantılı listeden kaldırılması işlemidir. Düğüm, değerinin ortaya çıkmasıyla veya konumuyla tanımlanabilir.
• Dairesel bağlantılı listenin dolaştırılması, bağlantılı listenin tüm içeriğinin görüntülenmesi ve yeniden görüntülenmesi işlemidir.tracKaynak düğüme geri dönüyor.

Sonraki bölümde, dairesel tek yönlü bağlantılı listede ekleme işleminin nasıl çalıştığı ve mümkün olan iki tür ekleme açıklanmaktadır.

sokma Operayon

Öncelikle, bir sonraki işaretçisi kendisine geri dönen bir düğüm oluşturursunuz, aşağıda gösterildiği gibi. Bu başlangıç ​​düğümü olmadan, ilk ekleme listedeki ilk düğüm olur.

Daha sonra iki olasılık var:

• Dairesel bağlantılı listenin mevcut konumuna ekleme. Bu, normal tek yönlü bağlantılı listenin başına veya sonuna eklemeye karşılık gelir; dairesel bağlantılı listede başlangıç ​​ve son aynı noktadır.
• Dizine alınmış bir düğümden sonra ekleme. Düğüm, öğe değerine karşılık gelen bir dizin numarasıyla tanımlanmalıdır.

Dairesel bağlantılı listenin başına veya sonuna, yani ilk düğümün eklendiği konuma düğüm eklemek için aşağıdaki adımları izleyin:

• Mevcut düğümle mevcut kendi kendine bağlantıyı kesmeniz gerekecek
• Yeni düğümün bir sonraki işaretçisi mevcut düğüme bağlanacaktır.
• Son düğümün bir sonraki işaretçisi eklenen düğüme işaret edecektir.

NOT: Çemberin başlangıcını veya sonunu işaretleyen işaretçi herhangi bir düğüme yeniden atanabilir. Bu makalede daha sonra açıklanacağı gibi, geçiş yine aynı düğüme geri dönecektir.

(a) i-iii'deki adımlar aşağıda gösterilmiştir:

(Mevcut düğüm)

) 1 Adım Mevcut bağlantıyı kes

) 2 Adım Bir ileri bağlantı oluşturun (yeni düğümden mevcut düğüme)

) 3 Adım İlk düğüme bir döngü bağlantısı oluşturun

Daha sonra, bir düğümden sonra eklemeyi deneyeceksiniz.

Örneğin, başlangıç ​​noktasının "VALUE0" değerine sahip düğüm olduğunu varsayarak, "VALUE0" değerini tutan düğümden sonra "VALUE2" ifadesini ekleyin.

• Birinci ve ikinci düğümler arasındaki bağlantıyı koparın ve "VALUE2" değerine sahip düğümü aralarına yerleştirin.
• Birinci düğümün sonraki işaretçisi yeni düğüme, yeni düğümün sonraki işaretçisi ise daha önce ikinci düğüm olan düğüme bağlanır.
• Düzenlemenin geri kalanı değişmeden kalır. Tüm düğümler yeniden oluşturulur.trackendilerine yetebilirler.

NOT: Düzenleme döngüsel olduğundan, hangi konumu seçerseniz seçin, düğüm ekleme prosedürü aynıdır. Döngüyü kapatan işaretçi, listedeki diğer işaretçiler gibi davranır.

Bu aşağıda gösterilmiştir:

(Diyelim ki sadece iki düğüm var. Bu önemsiz bir durum)

) 1 Adım Bağlı düğümler arasındaki iç bağlantıyı kaldırın

) 2 Adım Sol taraftaki düğümü yeni düğüme bağlayın

) 3 Adım Yeni düğümü sağ taraftaki düğüme bağlayın.

silme Operayon

Üç düğümlü dairesel bağlantılı bir liste varsayalım. İki silme durumu şöyledir:

• Geçerli öğenin silinmesi
• Bir öğeden sonra silme.

Başlangıçta/sonda silme:

1. Son düğümden ilk düğüme geçin.
2. Sondan silme işlemi yalnızca son düğümden ilk düğüme kadar tek bir gezinme adımı gerektirir.
3. Son düğüm ile ilk düğüm arasındaki bağlantıyı silin.
4. Son düğümü ilk düğümün bir sonraki öğesine bağlayın.
5. İlk düğümü serbest bırakın.

(Mevcut kurulum)

) 1 Adım Dairesel bağlantıyı kaldırın

) 2 Adım İlk ve sonraki arasındaki bağlantıyı kaldırın, son düğümü, ilk düğümü takip eden düğüme bağlayın

) 3 Adım İlk düğümü serbest bırak/tahsisten çıkar

Bir düğümden sonra silme:

1. Silinecek düğüme ulaşana kadar ilerleyin.
2. Önceki düğüme bir işaretçi yerleştirerek sonraki düğüme geçin.
3. Önceki düğümü, bir sonraki işaretçiyi kullanarak mevcut düğümden sonraki düğüme bağlayın.
4. Geçerli (bağlantısı kesilmiş) düğümü serbest bırakın.

) 1 Adım Diyelim ki “VALUE1” olan bir düğümü silmemiz gerekiyor.

) 2 Adım Önceki düğüm ile mevcut düğüm arasındaki bağlantıyı kaldırın, ardından önceki düğümü doğrudan mevcut düğümün sonraki işaretçisinin gösterdiği düğüme (VALUE1'den sonraki düğüm) bağlayın.

) 3 Adım Geçerli düğümü serbest bırakın veya serbest bırakın.

Dairesel Bağlantılı Listenin Geçişi

Son işaretçiden başlayarak dairesel bağlantılı bir listede gezinmek için öncelikle son işaretçinin NULL olup olmadığını kontrol edin. NULL değilse, listenin yalnızca bir eleman içerip içermediğini kontrol edin. Aksi takdirde, aşağıdaki animasyonda gösterildiği gibi, son işaretçiye tekrar ulaşana kadar geçici bir işaretçiyle listede gezinin.

Dairesel Bağlantılı Listenin Avantajları

Dairesel bağlantılı listelerin bazı avantajları şunlardır:

1. Kodda NULL atamasına gerek yoktur. Dairesel liste, tamamen serbest bırakılmadıkça hiçbir zaman NULL işaretçisine işaret etmez.
2. Dairesel bağlantılı listeler, başlangıç ​​ve bitiş noktalarının çakışması nedeniyle liste sonu işlemleri için avantajlıdır. Algorithms Örneğin, döngüsel zamanlama, askıda kalan veya NULL işaretçilerle karşılaşmadan, kuyruğa alınmış süreçler arasında sorunsuz bir şekilde geçiş yapabilir.
3. Dairesel bağlantılı liste, tek yönlü bağlantılı listenin tüm normal işlemlerini destekler. çift ​​bağlantılı liste Hatta bir öğeyi bulmak için tam uzunlukta bir tarama yapma ihtiyacını bile ortadan kaldırabilir; en kötü durumda, hedef başlangıç ​​işaretçisinin karşısında yer alır, bu nedenle listenin en fazla yarısının taranması gerekir.

Dairesel Bağlantılı Listenin Dezavantajları

Dairesel bağlantılı liste kullanmanın dezavantajları şunlardır:

1. Dairesel listeler daha karmaşıktır tek bağlantılı listeler.
2. RevDairesel bir listenin tersine çevrilmesi, tek veya çift yönlü bağlantılı bir listenin tersine çevrilmesinden daha karmaşıktır.
3. Döngü sonlandırma işlemi dikkatli bir şekilde ele alınmazsa, dolaşım kodu sonsuz bir döngüye girebilir.
4. Listenin sonunu bulmak ve doğru döngü kontrol koşullarını yazmak daha zordur.
5. Başa ekleme işlemi, uygulama açısından son düğüme ulaşmak için listenin tamamını dolaşmayı gerektirir.

Dairesel Bağlantılı Liste Olarak Tek Bağlantılı Liste

Aşağıdaki C kodunu okumanız ve uygulamanız önerilir. Bu kod, dairesel tek yönlü bağlantılı liste ile ilgili işaretçi aritmetiğini göstermektedir.

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

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

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

Kodun açıklaması:

1. Kodun ilk iki satırı gerekli olan başlık dosyalarıdır.
2. Sonraki bölümde, her bir öz referanslı düğümün yapısı tanımlanır. Bu düğüm, yapıyla aynı türde bir değer ve bir işaretçi içerir.
3. Her yapı örneği, aynı türdeki diğer yapı nesnelerine bağlanır.
4. Aşağıdakiler için farklı fonksiyon prototipleri vardır:
   1. Boş bir bağlantılı listeye öğe ekleme
   2. Şuraya ekleme: şu anda işaret edildi dairesel bağlantılı listenin konumu.
   3. Belirli bir noktadan sonra ekleme endeksli bağlantılı listedeki değer.
   4. Belirli bir sürenin ardından Kaldırma/Silme endeksli bağlantılı listedeki değer.
   5. Dairesel bağlantılı bir listenin şu anda işaret edilen konumundan kaldırılıyor
5. Son işlev, her bir öğeyi bağlantılı listenin herhangi bir durumunda dairesel bir geçiş yoluyla yazdırır.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

Kodun açıklaması:

1. `addToEmpty` kodu için, `malloc()` fonksiyonunu kullanarak boş bir düğüm ayırın.
2. Gelen verileri geçici düğüme yerleştirin.
3. Geçici düğümü son düğüme atayın ve sonraki işaretçisini kendisine ayarlayın, böylece tek düğüm kendisine geri işaret etsin.
4. Son işaretçiyi main() / uygulama bağlamına geri döndürün.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

Kodun açıklaması

1. Liste boşsa, addToEmpty() fonksiyonuna devredin ve kontrolü geri alın.
2. Mevcut düğümün ardından yerleştirilecek geçici bir düğüm oluşturun.
3. Yukarıdaki şemada gösterildiği gibi işaretçileri birbirine bağlayın.
4. Önceki fonksiyonda kullanılan kalıpla eşleşen son işaretçiyi döndürün.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

Kodun açıklaması:

1. Liste boşsa, arama anahtarını yok sayın, geçerli öğeyi listedeki tek düğüm olarak ekleyin ve kontrolü geri verin.
2. Do-while döngüsünün her yinelemesinde, önceki işaretçi en son geçilen sonucu tutar.
3. Ancak o zaman bir sonraki geçiş adımı gerçekleşir.
4. Hedef veri bulunduğunda veya temp tekrar son işaretçiye ulaştığında do-while döngüsü sona erer. Aşağıdaki kod bloğu, bulunan öğeyle ne yapılacağına karar verir.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

Kodun açıklaması:

1. Listedeki tüm öğeler taranmış ancak öğe bulunamamışsa, "Öğe bulunamadı" mesajı görüntülenmeli ve kontrol çağırana geri verilmelidir.
2. Hedef düğüm bulunursa, eklenecek değer için yeni bir düğüm tahsis edin.
3. Link Önceki düğümü yeni düğüme bağlayın ve yeni düğümün sonraki işaretçisini temp (gezinti değişkeni) ile ilişkilendirin.
4. Bu işlem, yeni öğeyi dairesel bağlantılı listede hedef düğümün hemen sonrasına yerleştirir. Ardından kontrol çağırana geri döner.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

Kodun açıklaması

1. Son (mevcut) düğümü kaldırmak için öncelikle listenin boş olup olmadığını kontrol edin. Eğer boşsa, hiçbir öğe kaldırılamaz.
2. Sıcaklık değişkeni bir bağlantı ilerlemesini sağlar.
3. Son işaretçiyi ilk düğümden sonraki düğüme bağlayın.
4. Bağlantısı kesilmiş düğümü serbest bırakmak için geçici işaretçiyi serbest bırakın.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

Kodun açıklaması

1. Önceki kaldırma fonksiyonunda olduğu gibi, öncelikle listenin boş olup olmadığını kontrol edin. Eğer boşsa, hiçbir öğe kaldırılamaz.
2. İki işaretçileri silinecek öğeyi bulmak için belirli konumlar atanır.
3. İşaretçiler birbiri ardına ilerletilir (önceki izler geçicidir).
4. Hedef öğe bulunana veya bir sonraki işaretçi son düğüme tekrar ulaşana kadar gezinme devam eder.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

Programın açıklaması

1. Bağlantılı listenin tamamı tarandıktan sonra hedef bulunamazsa, "Öğe bulunamadı" mesajı görüntülenir.
2. Aksi takdirde, öğe 3. ve 4. adımlarda bağlantısı kesilir ve serbest bırakılır.
3. Önceki işaretçi, temp'in sonraki işaretçisinin (silinecek olan düğümden sonraki düğüm) işaret ettiği düğüme bağlıdır.
4. Ardından geçici işaretçi serbest bırakılır.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

Kodun açıklaması

1. Düğüm sayısı sıfır ise, tepe noktası geçişi mümkün değildir; kullanıcının önce bir düğüm tahsis etmesi veya eklemesi gerekir.
2. Yalnızca bir düğüm varsa, döngüye gerek yoktur; düğümün içeriği doğrudan yazdırılır ve while döngüsü çalışmaz.
3. Birden fazla düğüm varsa, temp son öğeye kadar her öğeyi yazdırır.
4. Son elemana ulaşıldığı anda döngü sona erer ve fonksiyon kontrolü main() fonksiyonuna geri döndürür.

Dairesel Bağlantılı Liste Uygulamaları

• Sistem süreçlerinde döngüsel çizelgelemenin ve yüksek hızlı grafiklerde döngüsel çizelgelemenin uygulanması.
• Bilgisayar ağlarında token-ring zamanlama.
• Dijital mağaza panoları gibi sürekli veri akışı gerektiren ekran ünitelerinde kullanılır.

SSS