CEG's Linux User Group

  • Increase font size
  • Default font size
  • Decrease font size
Home Labs Circularly Singly Linked List

Circularly Singly Linked List

Monday, 15 June 2009 18:43 Pallavi C
E-mail Print
User Rating: / 4
PoorBest 
Article Index
Circularly Singly Linked List
Source Code
Documentation
Test Cases
Compatibility & References
All Pages

CIRCULARLY SINGLY LINKED LIST

Introduction :

A singly linked circular list is a linked list where the last node in the list points to the first node in the list. A circular list does not contain NULL pointers. A good example of an application where circular linked list should be used is a timesharing problem solved by the operating system. In a timesharing environment, the operating system must maintain a list of present users and must alternately allow each user to use a small slice of CPU time, one user at a time. The operating system will pick a user, let him/her use a small amount of CPU time and then move on to the next user, etc. For this application, there should be no NULL pointers unless there is absolutely no one requesting CPU time.

 

The insert, delete and search operations are similar to the singly linked list. In circular linked list, we should always maintain that the next node of the tail is linked to the head after the insertion and deletion operations.

Advantages:

  • Given any node, we can traverser the entire list.

  • Certain operations, such as concatenation and splitting of string, is more efficient with circular linked list.

Disadvantage:

  • Danger of an infinite loop ! (The header node is used to prevent infinite loop)

Circularly singly linked list operations :

* Inserting a node (new) in the beginning when the list is empty

cirlist1

* Inserting a node (new) in the beginning when the list is not empty

cirlist2

* Inserting a node (new) in the end of the list


cirlist3

Let end1 and end2 be the position of the end pointer before and after insertion respectively.

 

* Inserting a node (new) in the middle of the list

cirlist4

To insert a node in the middle, the list is traversed till the position where the node to be inserted is reached using a temp node. Here, the above code inserts the new node after the temp node.

* Deleting a node from the list

To delete a node in the end, traverse the list till the last node is reached using temp pointer. The pointer prev is made to point the node before the node which is to be deleted. The deletion of 4 is shown below.

cirlist5



Code :


#include<stdlib.h>
#include<stdio.h>
struct listnode
{
int info;
struct listnode *next;
};
typedef struct listnode *node;
typedef node list;

node new1,prev,temp,end;

list makeempty(list header)
{
header->next=header;
return header;
}

int isempty(list header)
{
return header->next==header;
}

list create()
{
list header;
header=malloc(sizeof(struct listnode));
if(header==NULL)
{
printf("out of space");
return NULL;
}
makeempty(header);
return header;
}

list insertbeg(list header,int x)
{
node new1=malloc(sizeof(struct listnode));
if(new1==NULL)
{
printf("out of space");
return header;
}
new1->info=x;
if(isempty(header))
{
new1->next=header;
header->next=new1;
end=new1;
}
else
{
new1->next=header->next;
header->next=new1;
}
return header;
}

list insertend(list header,int x)
{
int i;
node new1=malloc(sizeof(struct listnode));
if(new1==NULL)
{
printf("out of space");
return header;
}
new1->info=x;
if(isempty(header))
{
new1->next=header;
header->next=new1;
end=new1;
}
else
{
end->next=new1;
new1->next=header;
end=new1;
}
return header;
}

list insertmid(list header,int x,int pos)
{
int i;
if(pos<1)
{
printf("Error");
return header;
}
new1=malloc(sizeof(struct listnode));
if(new1==NULL)
{
printf("out of space");
return header;
}
new1->info=x;
if(isempty(header))
{
new1->next=header;
header->next=new1;
end=new1;
}
else if(pos==1)
{
new1->next=header->next;
header->next=new1;
}
else
{
temp=header->next;
i=1;
while(inext!=header)
{
temp=temp->next;
i++;
}
if(temp->next==header)
{
end->next=new1;
new1->next=header;
end=new1;
}
else
{
new1->next=temp->next;
temp->next=new1;
}
}
return header;
}
void display(list header)
{
if(isempty(header))
printf("no element in the list");
else
{
printf("\nList is\n");
temp=header->next;
while(temp!=header)
{
printf("%d\t",temp->info);
temp=temp->next;
}
printf("\n");
}
}
list deletee(list header,int x)
{
if(isempty(header))
printf("underflow");
else
{
prev=header;
temp=header->next;
while(temp!=header&&temp->info!=x)
{
prev=temp;
temp=temp->next;
}
if(temp==header)
printf("element not found");
else
prev->next=temp->next;
if(temp->next==header)
end=prev;
free(temp);
}
return header;
}
int search(list header,int x)
{
int count=0;
if(isempty(header))
{
printf("\n No element in list");
}
else
{
temp=header->next;
while(temp!=header)
{
if(temp->info==x)
count++; temp=temp->next;
}
if(count==0)
{
printf("Element not found");
}
else
{
printf("\n Element found");
printf("\n No. of occurrences : %d",count);
}
}
return header;
}
void deletelist(list header)
{
while(!isempty(header))
{
temp=header->next;
header->next=temp->next;
free(temp);
}
}
void main()
{
list header;
int j,k,n;
header=create();
while(1)
{
printf("OPTIONS :\n1.Insert begin\n2.Insert middle\n3.Insert end\n4.Delete\n5.Search\n6.Exit\n Enter choice : ");
scanf("%d",&n);
switch(n)
{
case 1:
printf("Enter element : ");
scanf("%d",&j);
header=insertbeg(header,j);
display(header);
break;
case 2:
printf("Enter element : ");
scanf("%d",&j);
printf("Enter position : ");
scanf("%d",&k);
header=insertmid(header,j,k);
display(header);
break;
case 3:
printf("Enter element : ");
scanf("%d",&j);
header=insertend(header,j);
display(header);
break;
case 4:
printf("Enter element : ");
scanf("%d",&j);
header=deletee(header,j);
display(header);
break;
case 5:
printf("Enter element : ");
scanf("%d",&j);
header=search(header,j);
display(header);
break;
case 6: printf("\n End");
exit(0);
default:printf("\n Invalid choice");
}
}
deletelist(header);
}

 

Goal of the code :

The aim of this code is to perform basic operations of circularly linked list such as

  1. Inserting element at the beginning of the list

     

  2. Inserting element at the middle of the list at a position specified by the user

     

  3. Inserting element at the end of the list

     

  4. Deleting an element from the list

     

  5. Searching for an element in the list

     

 

Variables Used :

§ header-This is a dummy node which points to the first node of the list.

§ new1 -This points to the new node to be inserted

§ temp -This is the temporary node used for traversing the list

§ prev -This pointer is used to track the node(i.e. to find the node previous to the node to be deleted)

§ end -This pointer points to the last node of the list

§ info -This variable stores the element in the information part of the node

§ next -This points the next node in the list

§ x -This variable stores the element to be inserted (used in functions)

§ j -This variable stores the element to be inserted or deleted (used in main() )

§ pos -This variable stores the position where the element is to be inserted (used in insertmid() function)

§ k -This variable stores the position where the element is to be inserted (used in main() )

§ n -This variable stores the user's choice and is used in switch-case to transfer the control to corresponding function

 

Functions Used :

 

Functions
Use
makeempty()
To empty the list
isempty()
To check whether the list is empty or not
create()
It allocates memory and thus creates a new list
insertbeg()
To insert a node at the beginning of the list
insertmid()
To insert a node at the middle
insertend()
To insert a node into the list at the end
display()
To display the contents of the list
deletee()
To delete a specific node
search()
To search for a specific node
deletelist()
To delete the entire list
main()
To input values from the user and to call other functions

 

Implementation:

§ In the main(), a list is created using create() function.

§ In case of 'Insert begin' and 'Insert end', the element to be inserted is got from the user and the insertion operation is performed using insertbeg() and insertend() functions respectively.

§ In case of 'Insert middle', the element to be inserted and the position of the new node are got from the user and the insertion operation is performed using insertmid() function.

§ In case of 'Delete', the element to be deleted is got from the user and then deletion operation is performed using deletee() function.

§ In case of 'Search', the element to be searched for is got from the user and its availability is printed using search() function.

 


Test cases :


The output of the above code is as shown below

OPTIONS :
1.Insert begin
2.Insert middle
3.Insert end
4.Delete
5.Search
6.Exit
Enter choice : 1
Enter element : 1

List is
1

OPTIONS :
1.Insert begin
2.Insert middle
3.Insert end
4.Delete
5.Search
6.Exit
Enter choice : 3
Enter element : 3

List is
1            3

OPTIONS :
1.Insert begin
2.Insert middle
3.Insert end
4.Delete
5.Search
6.Exit
Enter choice : 2
Enter element : 2
Enter position : 2

List is
1            2            3

OPTIONS :
1.Insert begin
2.Insert middle
3.Insert end
4.Delete
5.Search
6.Exit
Enter choice : 4
Enter element : 1

List is
2           3

OPTIONS :
1.Insert begin
2.Insert middle
3.Insert end
4.Delete
5.Search
6.Exit
Enter choice : 5
Enter element : 2
Element found
No. of occurrences : 1
List is
2          3

OPTIONS :
1.Insert begin
2.Insert middle
3.Insert end
4.Delete
5.Search
6.Exit
Enter choice : 6

End

 


 

Compatibility :

Compatible with all computers which is capable of running gcc-4.4.0. The program has been tested with the above version of gcc as of June 15.

 

References :

http://www.algorithmist.com/index.php/Linked_List#Circular_Lists

http://www.cs.usask.ca/content/resources/tutorials/csconcepts/2000_1/Tutorial/clist.html

 

**********

< Prev   Next >
Last Updated on Tuesday, 16 June 2009 17:46  
Please register or login to add your comments to this article.