सर्कुलर लिंक्ड सूची लिंक्ड सूची का एक रूपांतर है जिसमें पहला तत्व अंतिम तत्व की ओर इशारा करता है और अंतिम तत्व पहले तत्व की ओर इशारा करता है। सिंगली लिंक्ड सूची और डबल लिंक्ड सूची दोनों को सर्कुलर लिंक्ड सूची में बनाया जा सकता है।
डबल लिंक्ड सूची में, अंतिम नोड का अगला पॉइंटर पहले नोड की ओर इशारा करता है और पहले नोड का पिछला पॉइंटर अंतिम नोड की ओर इशारा करता है जिससे दोनों दिशाओं में सर्कुलर बनता है।

उपरोक्त चित्रण के अनुसार, निम्नलिखित महत्वपूर्ण बिंदुओं पर विचार किया जाना चाहिए।
- डबल लिंक्ड सूची में अंतिम लिंक का अगला सूची के पहले लिंक की ओर इशारा करता है।
- पहले लिंक का पिछला डबल लिंक्ड सूची के अंतिम की ओर इशारा करता है।
एल्गोरिदम
displayForward(): Begin
ptr := head
जबकि ptr := null, करें
print ptr->key, ptr->data
ptr := ptr->next
किया
End
displayBackward(): Begin
ptr := last
जबकि ptr := null, करें
print ptr->key, ptr->data
ptr := ptr->prev
किया
End
insertFirst(key, data): Begin
कुंजी और डेटा के साथ नया नोड बनाएं
यदि सूची खाली है, तो
last := node
अन्यथा
head->prev := node
अंत यदि
node->next := head
head := node
End
insertLast(key, data): Begin
कुंजी और डेटा के साथ नया नोड बनाएं
यदि सूची खाली है, तो
last := node
अन्यथा
last->next := node
node->prev := last
अंत यदि
last := node
End
insertAfter(key, newKey, data): Begin
current := head
यदि head null है, तो false लौटाएं
जबकि current की कुंजी key नहीं है, करें
यदि current->next null नहीं है, तो
false लौटाएं
अन्यथा
current := current का next
अंत यदि
किया
newKey और data के साथ नया नोड बनाएं
यदि current = last, तो
node का next := null
last := node
अन्यथा
node का next := current का next
current के next का prev := node
अंत यदि
node का prev := current
current का next := node
true लौटाएं
End
deleteFirst(): Begin
tempNode := head
यदि head का next null है, तो
last := null
अन्यथा
head के next का prev := null
अंत यदि
head := head का next
tempNode लौटाएं
End
deleteLast(): Begin
tempNode := last
यदि head का next null है, तो
head := null
अन्यथा
last के prev का next := null
अंत यदि
last := last का prev
tempNode लौटाएं
End
deleteNode(key): Begin
curr := head और prev := null
यदि head null है, तो
null लौटाएं
अंत यदि
जबकि curr की कुंजी key के समान नहीं है, करें
यदि curr का next null है, तो
null लौटाएं
अन्यथा
prev := curr
curr := curr का next
अंत यदि
किया
यदि curr head है, तो head := head का next, अन्यथा prev के curr का next = curr का next
यदि curr last है, तो last := curr का prev, अन्यथा curr के next का prev = curr का prev
curr लौटाएं
End
उदाहरण
#include <iostream>
using namespace std;
class node {
public:
int data;
int key;
node *next;
node *prev;
};
// यह लिंक हमेशा पहले लिंक की ओर इशारा करता है
node *head = NULL;
// यह लिंक हमेशा अंतिम लिंक की ओर इशारा करता है
node *last = NULL;
node *current = NULL;
// सूची खाली है या नहीं
bool isEmpty() {
return head == NULL;
}
int length() {
int length = 0;
node *current;
for (current = head; current != NULL; current = current->next) {
length++;
}
return length;
}
// सूची को पहले से अंत तक प्रदर्शित करें
void displayForward() {
// शुरुआत से शुरू करें
node *ptr = head;
// सूची के अंत तक नेविगेट करें
printf("\n[ ");
while (ptr != NULL) {
printf("(%d,%d) ", ptr->key, ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
// सूची को अंत से पहले तक प्रदर्शित करें
void displayBackward() {
// अंत से शुरू करें
node *ptr = last;
// सूची की शुरुआत तक नेविगेट करें
printf("\n[ ");
while (ptr != NULL) {
// डेटा प्रिंट करें
printf("(%d,%d) ", ptr->key, ptr->data);
// अगले आइटम पर जाएं
ptr = ptr->prev;
}
}
// लिंक को पहले स्थान पर डालें
void insertFirst(int key, int data) {
// एक लिंक बनाएं
node *link = new node();
link->key = key;
link->data = data;
if (isEmpty()) {
// इसे अंतिम लिंक बनाएं
last = link;
} else {
// पहले prev लिंक को अपडेट करें
head->prev = link;
}
// इसे पुराने पहले लिंक की ओर इंगित करें
link->next = head;
// पहले को नए पहले लिंक की ओर इंगित करें
head = link;
}
// लिंक को अंतिम स्थान पर डालें
void insertLast(int key, int data) {
// एक लिंक बनाएं
node *link = new node();
link->key = key;
link->data = data;
if (isEmpty()) {
// इसे अंतिम लिंक बनाएं
last = link;
} else {
// लिंक को नया अंतिम लिंक बनाएं
last->next = link;
// पुराने अंतिम नोड को नए लिंक के prev के रूप में चिह्नित करें
link->prev = last;
}
// अंतिम को नए अंतिम नोड की ओर इंगित करें
last = link;
}
// पहला आइटम हटाएं
node* deleteFirst() {
// पहले लिंक का संदर्भ सहेजें
node *tempLink = head;
// यदि केवल एक लिंक है
if (head->next == NULL) {
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
// हटाए गए लिंक को लौटाएं
return tempLink;
}
// अंतिम स्थान पर लिंक हटाएं
node* deleteLast() {
// अंतिम लिंक का संदर्भ सहेजें
node *tempLink = last;
// यदि केवल एक लिंक है
if (head->next == NULL) {
head = NULL;
} else {
last->prev->next = NULL;
}
last = last->prev;
// हटाए गए लिंक को लौटाएं
return tempLink;
}
// दी गई कुंजी के साथ लिंक हटाएं
node* del(int key) {
// पहले लिंक से शुरू करें
node* current = head;
node* previous = NULL;
// यदि सूची खाली है
if (head == NULL) {
return NULL;
}
// सूची के माध्यम से नेविगेट करें
while (current->key != key) {
// यदि यह अंतिम नोड है
if (current->next == NULL) {
return NULL;
} else {
// वर्तमान लिंक का संदर्भ संग्रहीत करें
previous = current;
// अगले लिंक पर जाएं
current = current->next;
}
}
// एक मिलान मिला, लिंक अपडेट करें
if (current == head) {
// पहले को अगले लिंक की ओर इंगित करने के लिए बदलें
head = head->next;
} else {
// वर्तमान लिंक को बायपास करें
current->prev->next = current->next;
}
if (current == last) {
// अंतिम को पिछले लिंक की ओर इंगित करने के लिए बदलें
last = current->prev;
} else {
current->next->prev = current->prev;
}
return current;
}
bool insertAfter(int key, int newKey, int data) {
// पहले लिंक से शुरू करें
node *current = head;
// यदि सूची खाली है
if (head == NULL) {
return false;
}
// सूची के माध्यम से नेविगेट करें
while (current->key != key) {
// यदि यह अंतिम नोड है
if (current->next == NULL) {
return false;
} else {
// अगले लिंक पर जाएं
current = current->next;
}
}
// एक लिंक बनाएं
node *newLink = new node();
newLink->key = newKey;
newLink->data = data;
if (current == last) {
newLink->next = NULL;
last = newLink;
} else {
newLink->next = current->next;
current->next->prev = newLink;
}
newLink->prev = current;
current->next = newLink;
return true;
}
int main() {
insertFirst(1, 10);
insertFirst(2, 20);
insertFirst(3, 30);
insertFirst(4, 1);
insertFirst(5, 40);
insertFirst(6, 56);
printf("\nसूची (पहले से अंत): ");
displayForward();
printf("\n");
printf("\nसूची (अंत से पहले): ");
displayBackward();
printf("\nसूची, पहला रिकॉर्ड हटाने के बाद: ");
deleteFirst();
displayForward();
printf("\nसूची, अंतिम रिकॉर्ड हटाने के बाद: ");
deleteLast();
displayForward();
printf("\nसूची, कुंजी(4) के बाद सम्मिलित करें: ");
insertAfter(4, 7, 13);
displayForward();
printf("\nसूची, कुंजी(4) हटाने के बाद: ");
del(4);
displayForward();
}
आउटपुट
सूची (पहले से अंत): [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ] सूची (अंत से पहले): [ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ] सूची, पहला रिकॉर्ड हटाने के बाद: [ (5,40) (4,1) (3,30) (2,20) (1,10) ] सूची, अंतिम रिकॉर्ड हटाने के बाद: [ (5,40) (4,1) (3,30) (2,20) ] सूची, कुंजी(4) के बाद सम्मिलित करें: [ (5,40) (4,1) (7,13) (3,30) (2,20) ] सूची, कुंजी(4) हटाने के बाद: [ (5,40) (7,13) (3,30) (2,20) ]