ICS121 – Data Structures I

Module 1 – Circular and Doubly Circular

Dr. E.Silambarasan
Assistant Professor
Department of Cyber Security
Indian Institute of Information technology, Kottayam
Circular Linked List:
Representation of Node:
struct node
{
int data;
struct node *next;
}
Insertion Operation: head = ptr;
Insertion at Beginning: ptr -> next = head;
struct node *ptr,*temp; }
int item; else
ptr = (struct node *)malloc(sizeof(struct {
node));
temp = head;
if(ptr == NULL)
while(temp->next != head)
Write “OVERFLOW";
temp = temp->next;
else
ptr->next = head;
{
temp -> next = ptr;
Read item;
head = ptr;
ptr -> data = item;
}
if(head == NULL)
}
{
Insertion Operation: head = ptr;
Insertion at Last: ptr -> next = head;
struct node *ptr,*temp; }
int item; else
ptr = (struct node *)malloc(sizeof(struct {
node));
temp = head;
if(ptr == NULL)
while(temp -> next != head)
Write "OVERFLOW";
temp = temp -> next;
else
temp -> next = ptr;
{
ptr -> next = head;
Read item;
}
ptr->data = item;
}
if(head == NULL)
{
Deletion: ptr = head;
Deletion at Beginning: while(ptr -> next != head)
struct node *ptr; ptr = ptr -> next;
if(head == NULL) ptr->next = head->next;
Write "UNDERFLOW"; free(head);
else if(head->next == head) head = ptr->next;
{ }
head = NULL;
free(head);
}
else
{
Deletion: while(ptr ->next != head)
Deletion at Last: {
struct node *ptr, *ptr1; ptr1=ptr;
if(head==NULL) ptr = ptr->next;
Write "UNDERFLOW"; }
else if (head ->next == head) ptr1->next = ptr -> next;
{ free(ptr);
head = NULL; }
free(head);
}
else
{
ptr = head;
Searching: {
struct node *ptr; if(ptr->data == item)
Int item, i=0,flag=1; {
ptr = head; Write "item found at location
“;
if(ptr == NULL)
flag=0;
Write "Empty List";
break;
else
}
{
else
Read search item;
flag=1;
if(head ->data == item)
i++;
{
ptr = ptr -> next;
write "item found at location “;
}
flag=0;
}
}
if(flag != 0)
else
Write "Item not found";
{
}
while (ptr->next != head)
Tracing: Write ptr -> data;
struct node *ptr; }
ptr=head;
if(head == NULL)
write "nothing to print";
else
{
while(ptr -> next != head)
{
write ptr -> data;
ptr = ptr -> next;
}
Doubly Circular Linked List:
Representation of Node:
struct node
{
int data;
struct node *next;
struct node *prev;
}
Insertion Operation: ptr -> next = head;
Insertion at Beginning: ptr ->prev = head;
struct node *ptr,*temp; }
int item; else
ptr = (struct node *)malloc(sizeof(struct {
node));
temp = head;
if(ptr == NULL)
while(temp -> next != head)
Write "OVERFLOW";
temp = temp -> next;
else
temp -> next = ptr;
{
ptr ->prev = temp;
Read item;
head ->prev = ptr;
ptr->data=item;
ptr -> next = head;
if(head==NULL)
head = ptr;
{
}
head = ptr;
}
Insertion Operation: ptr -> next = head;
Insertion at Last: ptr ->prev = head;
struct node *ptr,*temp; }
int item; else
ptr = (struct node *) malloc(sizeof(struct {
node));
temp = head;
if(ptr == NULL)
Write "OVERFLOW"; while(temp->next !=head)
else temp = temp->next;
{ temp->next = ptr;
Read item; ptr ->prev=temp;
ptr->data=item; head ->prev = ptr;
if(head == NULL) ptr -> next = head;
{ }
head = ptr; }
Deletion: temp = head;
Deletion at Beginning: while(temp -> next != head)
struct node *temp; temp = temp -> next;
if(head == NULL) temp -> next = head -> next;
Write " UNDERFLOW"; head -> next ->prev = temp;
else if(head->next == head) free(head);
{ head = temp -> next;
head = NULL; }
free(head);
}
else
{
Deletion: ptr = head;
Deletion at Last: if(ptr->next != head)
struct node *ptr; ptr = ptr -> next;
if(head == NULL) ptr ->prev -> next = head;
write " UNDERFLOW"; head ->prev = ptr ->prev;
else if(head->next == head) free(ptr);
{ }
head = NULL;
free(head);
}
else
{
Searching: {
struct node *ptr;
Int item, i=0,flag=1; if(ptr->data == item)
ptr = head; {
if(ptr == NULL) Write "item found at location;
write “Empty List"; flag=0;
else break;
{ }
Read search item; else
if(head ->data == item) flag=1;
{ i++;
write "item found at location”; ptr = ptr -> next;
flag=0; }
} }
else if(flag != 0)
{ Write "Item not found";
while (ptr->next != head)
Tracing: }
struct node *ptr;
ptr=head;
if(head == NULL)
Write “empty list";
else
{
while(ptr -> next != head)
{
write ptr -> data;
ptr = ptr -> next;
}
write ptr -> data;