Related Blog Items

• Reversing a circular single linked list using pointers
• Circular Doubly Linked List With Out Using Special Head or Tail Node
• Detecting a loop in single linked list
• Reversing single linked list recursively
• Linked Lists

Please visit my earlier post linked lists for basics of linked lists. Visit this post for circular double linked lists

What is circular linked list?

Circular Linked lists are chain of records/nodes, one record/node points to the next, and last node/record pointing to the first node instead of pointing to a sentinel. Record/node holds the data.

Why circular linked lists?

Circular linked lists can be traversed from anywhere (given any node) in the list, which gives flexibility and it also enahnces efficiencies of some operations however it complicates operations by inducing special cases to deal with circularity of list

How circular linked lists look like?

Operations On Circular Linked Lists:

Inserting a Node:

//insert after a known node and return the inserted node
Node *insert(Node *after, void *data)
{
  Node* n;
  n = (Node *) malloc (sizeof(Node));
  n->info = data;

  //incase header node is not created
  if (!after)
  {
    n->next = n;
    return n;
  }

  n->next = after->next;
  after->next = n;

  return n;
}

Deleting a Node:

//delete after a known node and return the node after deleted node
Node *delete(Node *after)
{
  Node* tmp;

  if (!after || (after == after->next))
  {
    return NULL;
  }

  tmp = after->next;

  after->next = tmp->next;
  free(tmp);

  return after->next;

}

Printing Circular list:

//given a node in list, prints entire list after the node
int printlist(Node *h)
{
  Node* t = h;
 
  while(t)
  {
    printf(" %d <->", t->info);
    t = t->next;
    if (t == h)
    {
      printf(" Circular\n");
      return 0;
    }
  }
 
  printf(" NULL\n");
  return 0;
}

Searching Circular List:

//given any node in list, search entire list
Node *searchlist(Node *h, void *info)
{
  Node* after = h;
 
  //search all nodes after n (if any)
  while(after)
  {
    if (after->info == info)
    {
      return after;
    }
    after = after->next;
    if (after == after->next)
    {
      break;
    }
  }
 
 
  return NULL;
}

Destroy Circular List

destroylist(Node **n)
{
  Node *tmp, *h;
 
  if (!n || !*n)
  {
    return;
  }
 
  h = *n;
 
  while(*n)
  {
    tmp = (*n)->next;  
    free(*n);
    *n = tmp;
    if (*n == h)
    {
      break;
    }
  }
 
  *n = NULL;
}

Reverse Circular List:

void reverse(Node** headRef)
{
  Node* result = NULL;
  Node* current = *headRef;
  Node* next;
 
  while (current != NULL)
  {
    next = current->next; // tricky: note the next node
    current->next = result; // move the node onto the result
    result = current;
    current = next;
    if (current == *headRef)
    {
      break;
    }
  }
  (*headRef)->next = result;
  *headRef = result;
}

Download full source code here

Popularity: 46%

You need to log on to convert this article into PDF

Related Blog Items

• Reversing a circular single linked list using pointers
• Circular Doubly Linked List With Out Using Special Head or Tail Node
• Detecting a loop in single linked list
• Reversing single linked list recursively
• Linked Lists

This entry was written by ponnada and posted on May 17, 2007 at 5:54 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.