Menü

Çizim ile C ++ 'da Dairesel Bağlantılı Liste Veri Yapısı

  • Ana
  • Diğer
  • Çizim ile C ++ 'da Dairesel Bağlantılı Liste Veri Yapısı

circular linked list data structure c with illustration

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

Dairesel Bağlantılı Listeye Tam Bir Genel Bakış.

Dairesel bağlantılı liste, bağlantılı listenin bir varyasyonudur. Düğümleri bir daire oluşturacak şekilde birbirine bağlanan bağlantılı bir listedir.

Dairesel bağlantılı listede, son düğümün bir sonraki göstericisi boş olarak ayarlanmamıştır, ancak ilk düğümün adresini içerir ve böylece bir daire oluşturur.

=> Sıfırdan C ++ Öğrenmek İçin Burayı Ziyaret Edin.

Dairesel bağlantılı liste

Ne öğreneceksin:

C ++ 'da Dairesel Bağlantılı Liste

Aşağıda gösterilen düzenleme, tek bağlantılı bir liste içindir.

tek bağlantılı liste

Döngüsel bağlantılı bir liste, tekil bağlantılı bir liste veya çift bağlantılı bir liste olabilir. Çift dairesel bağlantılı bir listede, ilk düğümün önceki göstericisi son düğüme bağlanırken, son düğümün sonraki göstericisi ilk düğüme bağlanır.

Temsili aşağıda gösterilmiştir.

çift ​​döngüsel bağlantılı liste

Beyanname

Döngüsel bağlantılı bir listedeki bir düğümü, aşağıda gösterildiği gibi diğer herhangi bir düğüm gibi ilan edebiliriz:

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

Döngüsel bağlantılı listeyi uygulamak için, döngüsel bağlantılı listedeki son düğüme işaret eden 'son' harici bir işaretçi tutuyoruz. Bu nedenle son-> sonraki, bağlantılı listedeki ilk düğümü gösterecektir.

Bunu yaparak, listenin başına veya sonuna yeni bir düğüm eklediğimizde, tüm listeyi geçmemize gerek kalmamasını sağlıyoruz. Bunun nedeni, sonun son düğüme işaret ederken, son-> sonraki ilk düğüme işaret etmesidir.

Harici işaretçiyi ilk düğüme işaret etseydik bu mümkün olmazdı.

Temel işlemler

Dairesel bağlantılı liste, listenin eklenmesini, silinmesini ve geçişini destekler. Şimdi operasyonların her birini ayrıntılı olarak tartışacağız.

Yerleştirme

Döngüsel bağlantılı listeye bir düğümü ya ilk düğüm (boş liste) olarak, başında, sonunda veya diğer düğümlerin arasına ekleyebiliriz. Aşağıda resimli bir temsil kullanarak bu ekleme işlemlerinin her birini görelim.

# 1) Boş bir listeye ekleyin

Boş bir listeye ekle

Dairesel listede düğüm olmadığında ve liste boş olduğunda, son işaretçi boştur, daha sonra yukarıda gösterildiği gibi son işaretçiyi düğüm N'ye göstererek yeni bir N düğümü ekleriz. N'nin bir sonraki göstericisi, sadece bir düğüm olduğu için N düğümünün kendisini gösterecektir. Böylece N, listedeki ilk ve son düğüm olur.

# 2) Listenin başına ekleyin

Listenin başına ekleyin

Yukarıdaki gösterimde gösterildiği gibi, listenin başına bir düğüm eklediğimizde, son düğümün bir sonraki göstericisi yeni düğüme N işaret eder ve böylece onu bir birinci düğüm yapar.

N-> sonraki = son-> sonraki

Son-> sonraki = N

# 3) Listenin sonuna ekleyin

son düğüm yeni düğümü işaret eder

Listenin sonuna yeni bir düğüm eklemek için şu adımları izliyoruz:

şelale modeli sistem geliştirme yaşam döngüsü

N-> sonraki = son -> sonraki;
son -> sonraki = N
last = N

# 4) Listenin arasına ekleyin

Listenin arasına ekle

N3 ve N4 arasına yeni bir N düğümü eklememiz gerektiğini varsayalım, önce listeyi çaprazlamamız ve ardından yeni düğümün, bu durumda N3'ün ekleneceği düğümü bulmamız gerekir.

Düğüm yerleştirildikten sonra aşağıdaki adımları gerçekleştiriyoruz.

N -> sonraki = N3 -> sonraki;
N3 -> sonraki = N

Bu, N3'ten sonra yeni bir N düğümü ekler.

Silme

Dairesel bağlantılı listenin silme işlemi, silinecek düğümün yerini belirlemeyi ve ardından belleğini boşaltmayı içerir.

Bunun için, curr ve prev olmak üzere iki ek işaretçi tutuyoruz ve ardından düğümü bulmak için listeyi dolaşıyoruz. Silinecek belirli düğüm, ilk düğüm, son düğüm veya aradaki düğüm olabilir. Konuma bağlı olarak akım ve önceki işaretçileri ayarlıyoruz ve ardından akım düğümünü siliyoruz.

Silme işleminin resimli bir temsili aşağıda gösterilmektedir.

silme işlemi

Geçiş

Geçiş, her bir düğümü ziyaret etme tekniğidir. Tek bağlantılı liste ve çift bağlantılı listeler gibi doğrusal bağlantılı listelerde, her düğümü ziyaret ettiğimiz ve NULL ile karşılaşıldığında durduğumuz için geçiş kolaydır.

Ancak, döngüsel bağlantılı bir listede bu mümkün değildir. Dairesel bağlantılı bir listede, ilk düğüm olan son düğümün sonundan başlayıp her düğümü geçiyoruz. Bir kez daha ilk düğüme ulaştığımızda dururuz.

Şimdi C ++ ve Java kullanan döngüsel bağlantılı liste işlemlerinin bir uygulamasını sunuyoruz. Burada ekleme, silme ve geçiş işlemlerini uyguladık. Daha net bir anlayış için, döngüsel bağlantılı listeyi şu şekilde tasvir ettik:

Geçiş

Böylelikle son düğüme (50), yine birinci düğüm olan düğümü (10) bağlarız, böylece onu dairesel bağlantılı bir liste olarak gösteririz.

#include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty(struct Node *last, int new_data) { // if last is not null then list is not empty, so return if (last != NULL) return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter(struct Node *last, int new_data, int after_item) { //return null if list is empty if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == after_item) { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << 'The node with data '< next; // Point to the first Node in the list. // Traverse the list starting from first node until first node is visited again do { cout <

data <'; p = p -> next; } while(p != last->next); if(p == last->next) coutdata==key && (*head)->next==*head) { free(*head); *head=NULL; } Node *last=*head,*d; // If key is the head if((*head)->data==key) { while(last->next!=*head) // Find the last node of the list last=last->next; // point last node to next of head or second node of the list last->next=(*head)->next; free(*head); *head=last->next; } // end of list is reached or node to be deleted not there in the list while(last->next!=*head&&last->next->data!=key) { last=last->next; } // node to be deleted is found, so free the memory and display the list if(last->next->data==key) { d=last->next; last->next=d->next; cout<<'The node with data '<

Çıktı:

Oluşturulan döngüsel bağlantılı liste aşağıdaki gibidir:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

Verileri 10 olan düğüm listeden silinir

10 silindikten sonra dairesel bağlantılı liste aşağıdaki gibidir:

20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20

Ardından, Dairesel bağlantılı liste işlemleri için bir Java uygulaması sunuyoruz.

//Java class to demonstrate circular linked list operations class Main { static class Node { int data; Node next; }; //insert a new node in the empty list static Node insertInEmpty(Node last, int new_data) { // if list is not empty, return if (last != null) return last; Node temp = new Node(); // create a new node temp.data = new_data; // assign data to new node last = temp; last.next = last; // Create the link return last; } //insert a new node at the beginning of the list static Node insertAtBegin(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); //set data for the node temp.data = new_data; temp.next = last.next; last.next = temp; return last; } //insert a new node at the end of the list static Node insertAtEnd(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); temp.data = new_data; temp.next = last.next; last.next = temp; last = temp; return last; } //insert node in between the nodes in the list static Node addAfter(Node last, int new_data, int after_item) { //if list is null, return if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == after_item) { temp = new Node(); temp.data = new_data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; { while(p != last.next); System.out.println('The node with data ' + after_item + ' not present in the list.'); return last; } //traverse the circular linked list static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println('Cicular linked List is empty.'); return; } p = last.next; // Point to first Node of the list. // Traversing the list. do{ System.out.print(p.data + '==>'); p = p.next; } while(p != last.next); if(p == last.next) System.out.print(p.data); System.out.print(' '); } //delete a node from the list static Node deleteNode(Node head, int key) { //if list is null, return if (head == null) return null; // Find the required node that is to be deleted Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf(' Given node ' + key + ' is not found' + “in the list!'); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head) { head = null; return head; } // If more than one node, check if it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } System.out.println('After deleting ' + key + ' the circular list is:'); traverse(head); return head; } // Main code public static void main(String() args){ Node last = null; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = addAfter(last, 50, 40); System.out.println('Circular linked list created is:'); traverse(last); last = deleteNode(last,40); } }

Çıktı:

Oluşturulan dairesel bağlantılı liste:

10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10

40'ı sildikten sonra döngü listesi:

10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10

Avantajlar dezavantajlar

Döngüsel bağlantılı listenin bazı avantaj ve dezavantajlarını tartışalım.

Avantajlar:

  • Herhangi bir düğüme gidebilir ve herhangi bir düğümden geçebiliriz. Aynı düğümü tekrar ziyaret ettiğimizde durmamız gerekiyor.
  • Son düğüm ilk düğüme işaret ettiğinden, son düğümden ilk düğüme gitmek yalnızca tek bir adım alır.

Dezavantajları:

  • Dairesel bağlantılı bir listeyi tersine çevirmek zahmetlidir.
  • Düğümler bir daire oluşturacak şekilde bağlandığından, listenin başlangıcı veya bitişi için uygun bir işaretleme yoktur. Bu nedenle, listenin veya döngü kontrolünün sonunu bulmak zordur. Eğer özen gösterilmezse, bir uygulama sonsuz bir döngü ile sonuçlanabilir.
  • Tek bir adımda önceki düğüme geri dönemeyiz. İlk önce tüm listeyi incelemeliyiz.

Dairesel Bağlantılı Liste Uygulamaları

  • Dairesel bağlantılı listenin gerçek zamanlı uygulaması, birden çok programı programladığı çok programlı bir işletim sistemi olabilir. Her programa, yürütülmesi için ayrılmış bir zaman damgası verilir ve ardından kaynaklar başka bir programa aktarılır. Bu bir döngüde sürekli devam eder. Bu temsil, döngüsel bağlantılı bir liste kullanılarak verimli bir şekilde elde edilebilir.
  • Birden fazla oyuncuyla oynanan oyunlar, her oyuncunun oynama şansı verilen bir düğüm olduğu döngüsel bağlantılı bir liste kullanılarak da temsil edilebilir.
  • Dairesel bir kuyruğu temsil etmek için döngüsel bağlantılı bir liste kullanabiliriz. Bunu yaparak kuyruk için kullanılan ön ve arka iki işaretçiyi kaldırabiliriz. Bunun yerine, yalnızca bir işaretçi kullanabiliriz.

Sonuç

Dairesel bağlantılı liste, düğümlerin bir daire oluşturmak için birbirine bağlandığı bir düğümler koleksiyonudur. Bu, son düğümün bir sonraki göstericisini boş olarak ayarlamak yerine, ilk düğüme bağlı olduğu anlamına gelir.

Döngüsel bağlantılı bir liste, çoklu programlama ortamındaki programlar gibi belirli bir zaman aralığından sonra tekrar tekrar tekrarlanması gereken yapıları veya etkinlikleri temsil etmede yardımcı olur. Dairesel bir kuyruk tasarlamak için de faydalıdır.

Dairesel bağlantılı listeler, ekleme, silme ve geçişler gibi çeşitli işlemleri destekler. Bu nedenle, bu eğitimde operasyonları ayrıntılı olarak gördük.

Veri yapıları ile ilgili bir sonraki konumuzda, yığın veri yapısı hakkında bilgi edineceğiz.

=> Burada C ++ Eğitim Öğreticilerinin A-Z'sini Görmek İçin Burayı Kontrol Edin.

Önerilen Kaynaklar

^