What is Doubly Circular Linked list? Implement Doubly Circular Linked list with example.

Doubly Circular linked list

Doubly Circular linked list has both the properties of doubly linked list and circular linked list. Two consecutive elements are linked by previous and next pointer and the last node points to first node by next pointer and also the previous pointer of the head node points to the tail node. This two way pointer linking has eliminated all the short comings of all previous linked lists which have been discussed in the previous sections. Node traversal from any direction is possible and also jumping from head to tail or from tail to head is only one operation: head pointer previous is tail and also tail pointer next is head. Find the visual representation of the doubly circular linked list in the below figure.

Doubly Circular linked list - pictorial view

Doubly Circular Linked list

Doubly Circular linked list - Data Structure


typedef struct _dslist_node
{
  int node_value;              /* Data value */
  struct _dslist_node * prev;  /* pointer to previous node */
  struct _dslist_node * next;  /* pointer to next node */

}dslist_node;

Advantages

  1. List can be traversed bothways from head to tail as well as tail to head
  2. Being a circular linked list tail can be reached with one operation from head node

Disadvantages

  1. It takes slightly extra memory in each node to accomodate previous pointer

Practical Applications

  1. Managing songs playlist in media player applications
  2. Managing shopping cart in online shopping

Doubly Circular linked list source code

This is a minimal demo application to show the functionalities of doubly circular linked list. We are taking user's input to pupulate the nodes in the list. List is getting populated with the logic add at tail like a queue. We quit the node addition iteration as user press (n) and jumps to the display nodes section. This linked list can be iterated from head to tail as well as from tail to head. We are displaying list with these two iteration logic and finally freeing the list by deleting each node one by one. Deletion process can be from head to tail or vice versa and we are showing head to tail login here.

#include <stdio.h>
#include <conio.h>

/* Doubly Circular linked list node */
typedef struct _dslist_node
{
  int node_value;              /* Data value */
  struct _dslist_node * prev;  /* pointer to previous node */
  struct _dslist_node * next;  /* pointer to next node */

}dslist_node;

int main(int argc, char *argv[])
{
  int key, i;
  dslist_node *head, *temp, *current, *tail;
  /* Initial condition for doubly circular linked list */
  head = NULL;
  tail = NULL;
  temp = NULL;
  current = NULL;
  printf ("Doubly circular linked list demo application\n");
  do
  {
    /* Populating doubly circular linked list till user escapes */
    printf ("Add a node [y/n] : ");
    key = getch();
    if(key == 'y')
    {
      temp = (dslist_node *)malloc(sizeof(dslist_node));
      if(temp != NULL)
      {
        printf ("Value of this node : ");
        scanf ("%d", &temp->node_value);
        /* Head null means list is empty */
        if(head == NULL)
        {
          /* First node so, head = tail */
          current = temp;
          head = temp;
          head->next = head;
          head->prev = head;
        }
        else /* means list has head */
        {
          /* temp is the new tail */
          current->next = temp;
          temp->prev = current;
          temp->next = head;
          head->prev = temp;
          current = temp;
        }
      }
      else
      {
        printf ("Memory allocation error!");
        return -1;
      }
    }
    else /* User has given (n) exit population */
    {
      break;
    }
  } while (1);

  /* head to tail iteration */
  tail = current;
  current = head;
  i = 0;
  printf ("List Contains(sequence head to tail):\n");
  do
  {
    printf ("Node %d, Value: %d\n", i + 1, current->node_value);
    i++;
    current = current->next;
  } while (current != head);

  /* tail to head iteration */
  current = tail;
  i = 0;
  printf ("List Contains(sequence tail to head):\n");
  do
  {
    printf ("Node %d, Value: %d\n", i + 1, current->node_value);
    i++;
    current = current->prev;
  }while (current != tail);

  /* Free a doubly linked list */
  current = head;
  while(current)
  {
    temp = current;
    current = current->next;
    free (temp);
    if(current == tail)
    {
      break;
    }
  }
  return 0;
}

Program Output

Doubly circular linked list demo application
Add a node [y/n] : y
Value of this node : 1
Add a node [y/n] : y
Value of this node : 10
Add a node [y/n] : y
Value of this node : 100
Add a node [y/n] : n
List Contains(sequence head to tail):
Node 1, Value: 1
Node 2, Value: 10
Node 3, Value: 100
List Contains(sequence tail to head):
Node 1, Value: 100
Node 2, Value: 10
Node 3, Value: 1

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions