Circular Doubly Linked List With Out Using Special Head or Tail Node
Circular double linked list can be traversed clockwise or anticlockwise. In this list all nodes are linked as shown in the below figure. The only difference between double linked list and circular double linked list is last node points to first node in the list, first node points to last node instead of pointing to NULLs.
here is the c structure for a node in a circular double linked list and it is same as double linked list.
struct Node { void* info; //data Node* next; //used to point to next node Node* prev; //used to point to previous node };
and in this implementation as well (earlier post double linked list also doen’t maintain special nodes), we are not using any special nodes(head or tail), so while operating on the list one must be careful to maintain logical head or tail according to the need.
here is the code for inserting, deleting nodes
//insert before a known node and return the inserted node Node *insertbefore(Node *before, void *data) { Node* n; n = (Node *) malloc (sizeof(Node)); n->info = data; //incase header node is not created if (!before) { n->prev = n; n->next = n; return n; } n->prev = before->prev; n->next = before; before->prev->next = n; before->prev = n; return n; } //insert after a known node and return the inserted node Node *insertafter(Node *after, void *data) { Node* n; n = (Node *) malloc (sizeof(Node)); n->info = data; //incase header node is not created if (!after) { n->prev = n; n->next = n; return n; } n->prev = after; n->next = after->next; if (after->prev) /*just to take care when list is broken*/ { after->next->prev = n; } after->next = n; return n; } //delete before a known node and return the node before deleted node Node *deletebefore(Node *before) { Node* tmp; tmp = before->prev; before->prev = tmp->prev; if (tmp->prev) /*just to take care when list is broken*/ { tmp->prev->next = before; } free(tmp); return before->prev; } //delete after a known node and return the node after deleted node Node *deleteafter(Node *after) { Node* tmp; tmp = after->next; after->next = tmp->next; tmp->next->prev = after; free(tmp); return after->next; } //given any node in list, deletes entire double linked list int deletelist(Node *n) { void *taddr = n; Node *tmp; Node* after = n; Node* before = n->prev; //delete all nodes after n (if any) do { tmp = after->next; free(after); after = tmp; }while (after && (taddr != after)); return 0; }
the below routine prints circular linked list, we can give any node in the list as a starting point
//given any node in list, prints entire list int printlist(Node *h) { Node* t = h; do { printf(" %d <->", t->info); t = t->next; }while(t && (t != h)); printf(" NULL\n"); return 0; }
searching a circular double linked list not different from double linked list just the difference is sentinels (nodes whose addresses are NULL) are not present in circular double linked list unless it is broken.
//given any node in list, search entire list Node *searchlist(Node *h, void *info) { Node* after = h; //search all nodes after n (if any) do { if (after->info == info) { return after; } after = after->next; }while(after && (after != h)); return NULL; }
detecting a broken link in circular double linked list…
int detectlist(Node *n) { int brokenlinks = 0; Node *tmp = n; Node* after = n->next; Node* before = n->prev; //detect abnormalities in the list (broken links) after n (if any) do { if ((after->prev != tmp) || (tmp->next != after)) { brokenlinks++; } after = after->next; tmp = tmp->next; }while(after && tmp && (after != n->next) && (tmp != n)); return brokenlinks; }
download the above program [circular double linked list.c
let me know your comments and suggestions…
Popularity: 73%
This work is licensed under a 
This work is licensed under a 