Related Blog Items

• Reversing a circular single linked list using pointers
• Circular Linked Lists
• Double Linked List With Out Using Special Head or Tail Node
• Reversing a double linked list
• Reversing single linked list recursively

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

30bcf5b3317f5d9c28e47d870c9a7a37001

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%

You need to log on to convert this article into PDF

Related Blog Items

• Reversing a circular single linked list using pointers
• Circular Linked Lists
• Double Linked List With Out Using Special Head or Tail Node
• Reversing a double linked list
• Reversing single linked list recursively

This entry was written by ponnada and posted on February 28, 2007 at 5:24 pm and filed under C Tidbits, Data Structures in C/C++. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.