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

Dairesel Bağlantılı Liste Nedir?

Dairesel bağlantılı liste, her bir düğümün kendisine kadar izlenebileceği şekilde düzenlenmiş bir düğüm dizisidir. Burada bir “düğüm”, yakın çevresindeki bir veya iki düğüme işaret eden, kendine referans veren bir öğedir.

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

Dairesel Bağlantılı Liste

Burada her düğümün kendisine göre izlenebildiğini görebilirsiniz. Yukarıda gösterilen örnek dairesel, tek bağlantılı bir listedir.

Not: En basit dairesel bağlantılı liste, gösterildiği gibi yalnızca kendisini izleyen bir düğümdür.

Dairesel Bağlantılı Liste

Basic OperaDairesel Bağlantılı listelerdeki bağlantılar

Döngüsel bağlantılı listedeki temel işlemler ş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.
  • Döngüsel bağlantılı listenin geçişi, bağlantılı listenin tüm içeriğinin görüntülenmesi ve kaynak düğüme geri gidilmesi işlemidir.

Bir sonraki bölümde, bir düğümün eklenmesini ve Dairesel Tek Bağlantılı Listede mümkün olan ekleme türlerini anlayacaksınız.

sokma Operayon

Başlangıçta, bu resimde gösterildiği gibi kendisine işaret eden bir düğüm oluşturmanız gerekir. Bu düğüm olmadan ekleme ilk düğümü oluşturur.

sokma Operayon

Daha sonra iki olasılık var:

  • Dairesel bağlantılı listenin geçerli konumuna ekleme. Bu, düzenli tekil bağlantılı listenin sonunun başına eklemeye karşılık gelir. Dairesel bağlantılı listede başlangıç ​​ve bitiş aynıdı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/sonuna, yani ilk düğümün eklendiği konuma eklemek için,

  • 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: Belirteç yöneticisi veya dairenin başlangıcı/sonu olan işaretçi değiştirilebilir. İleride tartışılacağı gibi, geçişte yine aynı düğüme dönecektir.

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

sokma Operayon

(Mevcut düğüm)

sokma Operayon

AŞAMA 1) Mevcut bağlantıyı kes

sokma Operayon

AŞAMA 2) Bir ileri bağlantı oluşturun (yeni düğümden mevcut düğüme)

sokma Operayon

AŞAMA 3) İlk düğüme bir döngü bağlantısı oluşturun

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

Örneğin “VALUE2” düğümünün sonuna “VALUE0” ekleyelim. Başlangıç ​​noktasının “VALUE0” olan düğüm olduğunu varsayalım.

  • Birinci ve ikinci düğüm arasındaki çizgiyi kesmeniz ve arasına “VALUE2” olan düğümü yerleştirmeniz gerekecektir.
  • İlk düğümün bir sonraki işaretçisi bu düğüme bağlanmalı ve bu düğümün sonraki işaretçisi önceki ikinci düğüme bağlanmalıdır.
  • Düzenlemenin geri kalanı değişmeden kalır. Tüm düğümler kendilerine göre geri izlenebilir.

NOT: Döngüsel bir düzenleme olduğundan, bir düğüm eklemek herhangi bir düğüm için aynı prosedürü içerir. Bir döngüyü tamamlayan işaretçi, diğer düğümler gibi döngüyü tamamlar.

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

sokma Operayon

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

sokma Operayon

AŞAMA 1) Bağlı düğümler arasındaki iç bağlantıyı kaldırın

sokma Operayon

AŞAMA 2) Sol taraftaki düğümü yeni düğüme bağlayın

sokma Operayon

AŞAMA 3) Yeni düğümü sağ taraftaki düğüme bağlayın.

silme Operayon

3 düğümlü dairesel bağlantılı bir liste varsayalım. Silinen haller aşağıda belirtilmiştir:

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

Başlangıçta/sonda silme:

  1. Son düğümden ilk düğüme geçin.
  2. Sondan silmek için son düğümden ilk düğüme kadar yalnızca bir geçiş adımı olmalıdır.
  3. Son düğüm ile sonraki 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.

silme Operayon

(Mevcut kurulum)

silme Operayon

1 ADIM) Dairesel bağlantıyı kaldırın

silme Operayon

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

silme Operayon

AŞAMA 3) İlk düğümü serbest bırakın/serbest bırakın

Bir düğümden sonra silme:

  1. Bir sonraki düğüm silinecek düğüm olana 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.

silme Operayon

AŞAMA 1) Diyelim ki “VALUE1” olan bir düğümü silmemiz gerekiyor.

silme Operayon

AŞAMA 2) Önceki düğüm ile geçerli düğüm arasındaki bağlantıyı kaldırın. Önceki düğümünü, geçerli düğümün işaret ettiği sonraki düğüme (VALUE1 ile) bağlayın.

silme Operayon

AŞAMA 3) 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 bir bağlantılı listeyi dolaşmak için son işaretçinin kendisinin NULL olup olmadığını kontrol edin. Bu koşul yanlışsa, yalnızca bir öğe olup olmadığını kontrol edin. Aksi takdirde, aşağıdaki GIF'te gösterildiği gibi son işaretçiye tekrar ulaşılana kadar veya gerektiği kadar çok kez geçici bir işaretçi kullanarak dolaşın.

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

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ğlı listeler başlangıç ​​ve bitişin aynı olması nedeniyle son işlemler için avantajlıdır. Algorithms Round Robin zamanlaması gibi, sarkan veya NULL referanslı işaretçilerle karşılaşmadan döngüsel bir şekilde sıraya konan işlemleri düzgün bir şekilde ortadan kaldırabilir.
  3. Dairesel bağlantılı liste aynı zamanda tek bağlantılı listenin tüm normal işlevlerini de yerine getirir. Aslında dairesel çift ​​bağlantılı listeler Aşağıda tartışılan yöntem, bir elemanın yerini belirlemek için tam uzunlukta bir geçiş yapılması ihtiyacını bile ortadan kaldırabilir. Bu öğe en fazla başlangıcın tam tersi olacak ve bağlantılı listenin yalnızca yarısını tamamlayacaktır.

Dairesel Bağlantılı Listenin Dezavantajları

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

  1. Dairesel listeler, aşağıdakilere kıyasla karmaşıktır: tek bağlantılı listeler.
  2. RevDairesel listenin tersi, tekli veya çiftli listelerle karşılaştırıldığında karmaşıktır.
  3. Dikkatli kullanılmazsa kod sonsuz bir döngüye girebilir.
  4. Listenin sonunu ve döngü kontrolünü bulmak daha zordur.
  5. Başlangıçta ekleme yaparak, son düğümü bulmak için tüm listeyi geçmemiz gerekir. (Uygulama Perspektifi)

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

Aşağıdaki kodu okuyup uygulamaya çalışmanız önerilir. Dairesel bağlantılı listelerle ilişkili işaretçi aritmetiğini sunar.

#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()
{
...

Tek Bağlantılı Liste

Kodun açıklaması:

  1. Kodun ilk iki satırı gerekli olan başlık dosyalarıdır.
  2. Bir sonraki bölümde her bir kendine referanslı düğümün yapısı açıklanmaktadır. Yapıyla aynı türden bir değer ve işaretçi içerir.
  3. Her yapı, aynı türdeki yapı nesnelerine tekrar tekrar 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)

Tek Bağlantılı Liste

Kodun açıklaması:

  1. addEmpty kodu için malloc işlevini kullanarak boş bir düğüm ayırın.
  2. Bu düğüm için verileri geçici değişkene yerleştirin.
  3. Tek değişkeni geçici değişkene atayın ve bağlayın
  4. Son öğeyi main()/uygulama bağlamına 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;
…

Tek Bağlantılı Liste

Kodun açıklaması

  1. Eklenecek öğe yoksa boş bir listeye eklemeyi ve kontrolü döndürmeyi unutmayın.
  2. Geçerli öğenin arkasına yerleştirilecek geçici bir öğe oluşturun.
  3. İşaretçileri gösterildiği gibi bağlayın.
  4. Önceki fonksiyonda olduğu gibi 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");
...

Tek Bağlantılı Liste

Kodun açıklaması:

  1. Listede öğe yoksa verileri yok sayın, geçerli öğeyi listedeki son öğe olarak ekleyin ve kontrolü döndürün
  2. Do-while döngüsündeki her yineleme için, son geçilen sonucu tutan bir önceki işaretçinin olduğundan emin olun.
  3. Ancak o zaman bir sonraki geçiş gerçekleşebilir.
  4. Veri bulunursa veya temp son işaretçiye geri dönerse do-while sonlandırılır. Kodun bir sonraki bölümü öğeyle ne yapılması gerektiğine 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)
...

Tek Bağlantılı Liste

Kodun açıklaması:

  1. Listenin tamamı geçildiyse ancak öğe bulunamazsa, bir "öğe bulunamadı" mesajı görüntüleyin ve ardından kontrolü arayana verin.
  2. Bir düğüm bulunursa ve/veya düğüm henüz son düğüm değilse yeni bir düğüm oluşturun.
  3. Link önceki düğüm ile yeni düğüm. Geçerli düğümü temp (geçiş değişkeni) ile bağlayın.
  4. Bu, öğenin dairesel bağlantılı listede belirli bir düğümden sonra yerleştirilmesini sağlar. Arayan kişiye geri dönün.
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)

Tek Bağlantılı Liste

Kodun açıklaması

  1. Yalnızca son (geçerli) düğümü kaldırmak için bu listenin boş olup olmadığını kontrol edin. Eğer öyleyse, hiçbir öğe kaldırılamaz.
  2. Temp değişkeni yalnızca bir bağlantı ileri doğru gider.
  3. Son işaretçiyi ilkinden sonraki işaretçiye bağlayın.
  4. Sıcaklık işaretçisini serbest bırakın. Bağlantısız son işaretçiyi serbest bırakır.
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");
...

Tek Bağlantılı Liste

Kodun açıklaması

  1. Önceki kaldırma işlevinde olduğu gibi, öğe olup olmadığını kontrol edin. Eğer bu doğruysa, hiçbir öğe kaldırılamaz.
  2. İşaretçiler silinecek öğeyi bulmak için belirli konumlar atanır.
  3. İşaretçiler birbiri ardına ileri düzeydedir. (önceki sıcaklığın arkasında)
  4. İşlem, bir öğe bulunana veya sonraki öğe son işaretçiye geri dönene kadar 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;	

Tek Bağlantılı Liste

Programın açıklaması

  1. Bağlantılı listenin tamamını dolaştıktan sonra öğe bulunursa, öğenin bulunamadığını belirten bir hata mesajı görüntülenir.
  2. Aksi takdirde eleman 3. ve 4. adımlarda bağlantısı koparılıp serbest bırakılır.
  3. Önceki işaretçi, silinecek öğenin (temp) “sonraki” olarak gösterdiği adrese bağlanır.
  4. Bu nedenle sıcaklık işaretçisi serbest bırakılır ve 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;
    }
}

Tek Bağlantılı Liste

Kodun açıklaması

  1. Sıfıra ihtiyaç duyulursa göz atma veya geçiş mümkün değildir. Kullanıcının bir düğüm tahsis etmesi veya eklemesi gerekir.
  2. Yalnızca bir düğüm varsa, geçiş yapmaya gerek yoktur, düğümün içeriği yazdırılabilir ve while döngüsü yürütülmez.
  3. Birden fazla düğüm varsa geçici öğe, son öğeye kadar tüm öğeyi yazdırır.
  4. Son öğeye ulaşıldığı anda döngü sona erer ve işlev, çağrıyı ana işleve 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 jeton halkalarının planlanması.
  • Sürekli veri geçişi gerektiren mağaza panoları gibi görüntüleme birimlerinde kullanılır.