Circularly linked lists

CIRCULAR LINKED LIST

In circular linked list the pointer of the last node points to the first node. Circular linked list can be implemented as Singly linked list and Doubly linked list with or without headers.

Advantages of Circular Linked List

It allows to traverse the list starting at any point.

It allows quick access to the first and last records.

C PROGRAM FOR CIRCULAR LINKED LISTS

#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;

}