This blog is under construction

Wednesday 20 February 2013

C Program To Implement Circular Singly Linked List

If the tail node in a list gives access to the head node in the same list, then that list is called circular linked list.

                   head                         tail
                ----------------           ----------------
     +----> |data |       --|------>| data |      --|----+
     |         ----------------           ----------------     |
     |                                                                |
     +-----------------------------------------------------+


See Also:


Example Program For Circular Singly Linked List Implementation(in C):




  #include <stdio.h>
  #include <stdlib.h>

  struct node {
        int data;
        struct node *next;
  };

  struct node *head = NULL, *tail = NULL;

  struct node * createNode(int data) {
        struct node *newnode;
        newnode = (struct node *)malloc(sizeof (struct node));
        newnode->data = data;
        newnode->next = NULL;
  }

    /*
     * create dummy head and tail to make
     * insertion and deletion operation simple.
     * While processing data in our circular 
     * linked list, skip these dummies.
     */

  void createDummies() {
        head = createNode(0);
        tail = createNode(0);
        head->next = tail;
        tail->next = head;
  }

  /* insert data next to dummy head */
  void circularListInsertion(int data) {
        struct node *newnode, *temp;
        newnode = createNode(data);
        temp = head->next;
        head->next = newnode;
        newnode->next = temp;
  }

  /* Delete the node that has the given data */
  void DeleteInCircularList(int data) {
        struct node *temp0, *temp;
        if (head->next == tail && tail->next == head) {
                printf("Circular Queue/list is empty\n");
        }
        temp0 = head;
        temp = head->next;
        while (temp != tail) {
                if (temp->data == data) {
                        temp0->next = temp->next;
                        free(temp);
                        break;
                }
                temp0 = temp;
                temp = temp->next;
        }
        return;
  }

  /*
   * travese the circular linked list for
   * the given no of times.
   */
  void display(int count) {
        int n = 0;
        struct node *tmp = head;

        if (head->next == tail && tail->next == head) {
                printf("Circular linked list is empty\n");
                return;
        }

        while (1) {
                /* skip the data in dummy head and tail */
                if (tmp == head || tmp == tail) {
                        if (tmp == tail) {
                                n++;
                                printf("\n");
                                if (n == count)
                                        break;
                        } else {
                                tmp = tmp->next;
                                continue;
                        }
                } else {
                        printf("%-3d", tmp->data);
                }
                tmp = tmp->next;
        }
        return;
  }


  int main() {
        int data, ch, count;
        createDummies();
        while (1) {
                printf("1. Insertion\t2. Deletion\n");
                printf("3. Display\t4. Exit\n");
                printf("Enter ur choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter the data to insert:");
                                scanf("%d", &data);
                                circularListInsertion(data);
                                break;

                        case 2:
                                printf("Enter the data to delete:");
                                scanf("%d", &data);
                                DeleteInCircularList(data);
                                break;

                        case 3:
                                printf("No of time u wanna traverse:");
                                scanf("%d", &count);
                                display(count);
                                break;

                        case 4:
                                exit(0);

                        default:
                                printf("Pls. enter correct option\n");
                                break;
                }
        }
        return 0;
  }



  Output: (Insertion, Deletion, Traversal In Circular Singly Linked List)

  jp@jp-VirtualBox:~/cpgms/data_structures$ ./a.out
  1. Insertion 2. Deletion
  3. Display 4. Exit
  Enter ur choice:1
  Enter the data to insert:10
  1. Insertion 2. Deletion
  3. Display 4. Exit
  Enter ur choice:1
  Enter the data to insert:20
  1. Insertion 2. Deletion
  3. Display 4. Exit
  Enter ur choice:1
  Enter the data to insert:30
  1. Insertion 2. Deletion
  3. Display 4. Exit
  Enter ur choice:3
  No of time u wanna traverse:3
  30 20 10 
  30 20 10 
  30 20 10 
  1. Insertion 2. Deletion
  3. Display 4. Exit
  Enter ur choice:2
  Enter the data to delete:20
  1. Insertion 2. Deletion
  3. Display 4. Exit
  Enter ur choice:3
  No of time u wanna traverse:2
  30 10 
  30 10 
  1. Insertion 2. Deletion
  3. Display 4. Exit
  Enter ur choice:4




No comments:

Post a Comment