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

__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 lis**t */ *

*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*

*givenKey*

There are two steps to execute:

**Find the node with key***givenKey*:

*NodeT ***p*, **q*, **q1*;

*q1* = *NULL*; */*** **i**n**i**t**i**a**l**i**ze */*

* 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