इससे पहले के article मे , linked list का basic,advantage और disadvantage को पढ़ा|अब इस article मे ,linked लिस्ट के types को पढेगे|
linked list तीन प्रकार की होती है :-
1. circular linked list
2. Two way या doubly linked list
3. Circular doubly linked list
Circular linked list :
circular linked list एसी linked list होती जिनका न तो begining होता है ना ही end होता है |इस लिस्ट का last node हमेशा पहले node के address को contain करता है |
Requirement of Circular linked list
Circular linked list को दो वजह से use किया जाता है :-
1.Circular linked list का use एसी प्रोब्लेम को solve करने के किया जाता है जो inheritance है जैसे board game :इस game मे प्रत्येक turn के साथ next-player turn associate होता है|इस game को Circular linked list से solve किया जाता है क्योकि Circular linked list मे , कोई भी node null pointer नहीं रखता है |
2.Circular linked list का use buffer मे किया जा सकता है |jitter buffer एक एस buffer है जो की नेटवर्क से packets लेता है उन packets को एक order मे arrang करता है जो की किसी ऑडियो और विडियो को play करने के लिए use किया जाता है | लेकिन packets की speed बहुत slow होती है |
इसलिए इस operation के लिए Circular linked list का use करते है जिसमे मे की inserting और deletion constant होता है |
3.Circular linked list का use time sharing operation मे भी हो सकता है |Time sharing operation मे , cpu को सभी operation को एक fixed cpu time assign करना होता है और उन सभी operation के sequence और assign time को maintain करने के लिए Circular linked list का use किया जाता है |
4.Circular linked list का use queue और stack data struture create करने के लिए भी किया जाता है |
Circular linked list के types :
Circular linked list भी two प्रकार के होती है :-
1.Singly Circular linked list
इस प्रकार की linked लिस्ट मे , linked लिस्ट का last element ,first element का address contain करता है |
2.doubly Circular linked list
इस प्रकार मे , दो pointer variable होते है |इन दोनों pointer variable के बीच मे , item के लिए space होता है |first pointer variable node से पहले वाले node के address को hold करता है और last pointer variable age वाले node के address को hold करता है |
Circular linked list के operation :
Circular linked list मे तीन operation मुख्य होते है :-
1.Inserting in doubly Circular linked list
void insert_first(int add, int item)
{
struct node *n = (struct node*) malloc(sizeof(struct node)); // Dynamic memory allocation
n->add = add; // data ‘ add ‘ assign
n->item= item; // data ‘item’ assign
if (isEmpty()) // condition is check
{
head = n;
head->next = head;
}
else
{
n->next = head; //point it to old first node
head = n; //point first to new first node
}
}
इस उदाहरण मे , pointer variable मे dynamic memory एलोकेशन से return value assign होती है |
उसके बाद pointer variable के member ‘add’ पर variable add की value store हो जाती है |और member ‘item मे variable item की value store हो जाती है |
उसके बाद condition check होती हिया की node का pointer variable empty है या नहीं |
अगर empty है तब उसके pointer variable ‘head ‘ के first pointer variable मे pointer variable ‘n’ का address assign हो जाता है |pointer variable ‘head’ के next position पर next node का address store हो जाता है |
Deleting in doubly Circular linked list
struct node * delete_First()
{
struct node *add = first; //save reference to first address
if(first->next == first)
{
first = NULL;
return add;
}
first = first->next; //mark next to first address as first
return add; //return the deleted address
}
इस उदहारण से , first element को डिलीट किया गया है |सबसे पहले pointer variable ‘add’ मे first node के address को सेव करते है |
अगर first node का next pointer ,first node के address को ही contain करता है तब first node के address को null set कर देते है और pointer variable ‘add’ के address को return कर देगा |
और अगर नहीं होता तब pointer variable ‘first’ के first address को pointer variable ‘first’ के next address को assign कर देते है जिससे pointer variable ‘first डिलीट हो जाता है |
Displaying in doubly Circular linked list
void display_list() {
struct node *n = head;
if(head != NULL) //start from the first node
{
while(n->next != n)
{
printf(“(%d,%d) “,n->add,n->item);
n = n->next;
}
}
}
इस उदाहरण मे , pointer variable ‘n’ को linked लिस्ट क head node के address से initial कर देते है |
अगर head node null नहीं होते तब तक while loop चलता रहता है |Pointer Revisited
pointer का use linked लिस्ट को processing करने मे अहम रोल होता है |अगर किसी variable को pointer के तरह declare करते है तब pointer variable उस data variable के address को hold करता है |जब किसी linked list को प्रोसेस करते है तब pointer variable को use करते है |अगर ‘p’ एक pointer variable है तब
‘*p’ : इस syntax से pointer variable की value को define करता है |
Sbistudy
