Circular Linked List
Activity Outcomes:
This lab teaches you the following topics:
- Creation of circular linked list
- Insertion in circular linked list
- Deletion from circular linked list
- Traversal of all nodes
Introduction
A circular singly linked list is a singly linked list which has the last element linked to the first element in the list.
Being circular it really has no ends then we’ll use only one pointer pNode to indicate one element in the list – the newest element. Figure 3.1 show a model of such a list.
Lab Activities:
Activity 1:
Creation of circular linked list
read a complete detail of circular linklist here https://cuitutorial.com/courses/data-structure/lessons/circular-link-list/
Solution:
- Initially, the list is empty, i.e. pNode = NULL.
- Generate a node to insert in the list:
/* reserve space */
p = ( NodeT * ) malloc( sizeof( NodeT ) ) ; Then read the data into the node addressed by p
- Link it in the list:
p−>next = NULL;
/* node is appended to the list */
i f ( pNode == NULL )
{
/* empty list */
pNode= p;
pNode−>nex t = p;
}
else
{
/* nonempty l i s t */
p−>next =pNode−>nex t ;
pNode−>nex t = p;
pNode = p;
/* pNode points to the newest node in the l i s t */
}
Activity 2:
Accessing nodes of circular linked list
Solution:
The nodes of a list may be accessed sequentially, starting at node pNode, as follows:
NodeT *p;
p = pNode;
i f ( p != NULL )
do
{
access current node and get data ;
p = p−>next ;
}
while ( p != pNode ) ;
Another choice is to look for a key, say givenKey. Code for such list scan is given below:
NodeT *p;
p = pNode;
i f ( p != NULL )
do
{
i f ( p−>key = givenKey )
{ /* key found at address p */
return p;
}
p = p−>next ;
}
while ( p != NULL ) ;
return NULL; /* not found */
Activity 3:
Insertion in circular linked list
Solution:
A node may be inserted before a node containing a given key, or after it. Both cases imply searching for that key, and, if that key exists, creating the node to insert, and adjusting links accordingly.
Inserting Before a node with key givenKey
There are two steps to execute:
- Find the node with key givenKey:
NodeT *p, *q, *q1;
q1 = NULL; /* initialize */
q = pNode;
do
{
q1 = q;
q = q−>next ;
i f ( q−>key == givenKey ) break;
}
while ( q != pNode ) ;
- Insert the node pointed to by p, and adjust links:
i f ( q−>key == givenKey )
{
/* node with key givenKey has address q */
q1−>next = p;
p−>next = q;
}
Insertion after a node with key
Again, there are two steps to execute:
- Find the node with key givenKey:
NodeT *p, *q;
q = pNode;
do
{
i f ( q−>key == givenKey ) break;
q = q−>next ;
}
while ( q != pNode ) ;
- Insert the node pointed to by p, and adjust links:
i f ( q−>key == givenKey )
{
/* node with key givenKey has address q */
p−>next = q−>next ;
q−>next = p;
}
Activity 4:
Deleting a node from circular linked list
Solution:
Again there are two steps to take:
- Find the node with key givenKey:
NodeT *p, *q, *q1;
q = pNode;
do
{
q1 = q;
q = q−>next ;
i f ( q−>key == givenKey ) break;
}
while ( q != pNode ) ;
- Delete the node pointed to by q. If that node is pNode then we adjust pNode to point to its previous.
i f ( q−>key == givenKey )
{
/* node with key givenKey has address q */
i f ( q == q−>next )
{
/* l i s t now empty */
}
else
{
q1−>next = q−>next ;
i f ( q == pNode )
pNode = q1;
}
free ( q ) ;
Activity 5:
Complete Deletion of Circular Linked list
Solution:
For complete deletion of a list, we have to remove each node of that list, i.e. for deletion code
NodeT *p, *p1;
p = pNode;
do
{
p1 = p;
p = p−>next ;
free ( p1 ) ;
}
while ( p != pNode ) ;
pNode = NULL;
}
Home Activities:
- Write a function that deletes all those nodes from a linked list which have even/odd numbered value in their data part.
- Write a function that implements Josephus problem.
- Write a function that deletes all even positioned nodes from a linked list. Last node should also be deleted if its position is even.
Related links
Single link list Stack AVL Trees Binary search Counting Sort
Doubly link list Queue Graphs Bubble Sort Radix sort
Circular link list Binary search tree Hashing Insertion Sort Bucket Sort
Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort
At Cui tutorial, courses, past papers and final year projects
#tutorial #cui #pastpaper #courses
