CIRCULAR LINKED LIST

C I R C U L A R S I N G LY
LINKED LIST
CIRCULAR LINKED LIST
• In a circular linked list, the last node contains a pointer to the first
node of the list.

• The only downside of a circular linked list is the complexity of

iteration.
• Note that there are no NULL values in the NEXT part of any of
the nodes of list.
• Circular linked lists are widely used in operating systems for task
maintenance.
CIRCULAR SINGLY LINKED LIST
• In a circular Singly linked list, the last
node of the list contains a pointer to
the first node of the list.

• We traverse a circular singly linked list

until we reach the same node where
we started. Hint: Circular linked list are mostly used in task
maintenance in operating systems. There are many
examples where circular linked list are being used in
computer science including browser surfing where a
• The circular singly liked list has no record of pages visited in the past by the user, is
beginning and no ending. There is no maintained in the form of circular linked lists and can be
null value present in the next part of accessed again on clicking the previous button.
any of the nodes.
MEMORY REPRESENTATION OF CIRCULAR
LINKED LIST • In the image, memory representation of a
circular linked list containing marks of a student
in 4 subjects. However, the image shows a
glimpse of how the circular list is being stored
in the memory.

• The start or head of the list is pointing to the

element with the index 1 and containing 13
marks in the data part and 4 in the next part.
Which means that it is linked with the node
that is being stored at 4th index of the list.

• However, due to the fact that we are

considering circular linked list in the memory
therefore the last node of the list contains the
address of the first node of the list.
INSERTION: CIRCULAR SINGLY LINKED LIST AT
BEGINNING
//allocate the memory space for the new node
struct node *ptr = (struct node *)malloc(sizeof(struct node));

Scenario 1: Empty List

// make the head pointer point to this node

// The only node of the list (which is just inserted into the list) will point to itself only
if(head == NULL) {
head = ptr;
ptr -> next = head;
}
INSERTION: CIRCULAR SINGLY LINKED LIST AT
BEGINNING
Scenario 2: Already filled List  head != NULL

temp = head;

//traverse the list in order to

reach the last node of the
list

//At the end of the loop, the

pointer temp would point to
the last node of the list
while(temp->next != head)
temp = temp->next;
void insertAtBeginning(int value) {
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode -> data = value;

if(head == NULL) {
head = newNode;
newNode -> next = head;
}
else {
struct Node *temp = head;
while(temp -> next != head)
temp = temp -> next;
newNode -> next = head;
head = newNode;
temp -> next = head;
}

printf("\nInsertion success!!!");
}
INSERTION: CIRCULAR SINGLY LINKED LIST AT
END
Scenario 1: Empty List The same with slide 64

Scenario 2: Already filled List

temp = head;

//we need to traverse the list in order to reach the last node of the list
while(temp->next != head)
temp = temp->next;

temp -> next = ptr;

ptr->next = head;
void insertAtEnd(int value) {
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode -> data = value;

if(head == NULL) {
head = newNode;
newNode -> next = head;
}
else {
struct Node *temp = head;
while(temp -> next != head)
temp = temp -> next;
temp -> next = newNode;
newNode -> next = head;
}

printf("\nInsertion success!!!");
}
DELETION: CIRCULAR SINGLY LINKED LIST AT
BEGINNING
Scenario 1: The list contains single node  head → next == head
//delete the entire list and make the head pointer free.
if(head->next == head) {
head = NULL;
free(head);
}

Scenario 3: The list contains more than one node

ptr = head; //ptr is the temporary pointer to traverse in the list
while(ptr -> next != head)
ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
void deleteBeginning() {
if(head == NULL)
printf("List is Empty!!! Deletion not possible!!!");

else {
struct Node *temp = head;

if(temp -> next == head) //That means there is only one node
{
head = NULL;
free(head);
}
else
temp = temp-> next;

temp-> next = head-> next;

free(head);
head = temp-> next;

printf("\nDeletion success!!!");
}
}
DELETION: CIRCULAR SINGLY LINKED LIST AT
END
Scenario 1: The list contains single node  head → next == head
if(head->next == head) {
head = NULL;
free(head);
}

Scenario 2: The list contains more than one node

//need to keep track of the second last node of the list. For this purpose, the two pointers ptr
and preptr are defined
ptr = head;
while(ptr ->next != head) {
preptr=ptr;
ptr = ptr->next;
}

preptr->next = ptr -> next;

free(ptr);
void deleteEnd() {
if(head == NULL)
printf("List is Empty!!! Deletion not possible!!!");
else {
struct Node *temp1 = head, temp2;
if(temp1 -> next == head) {
head = NULL;
free(head);
}
else{
while(temp1 -> next != head){
temp2 = temp1;
temp1 = temp1 -> next;
}
temp2 -> next = head;
free(temp1);
}
printf("\nDeletion success!!!");
}
}
C I R C U L A R D O U B LY
LINKED LIST
CIRCULAR DOUBLY LINKED LIST
• doesn't contain NULL in any of the node.
• The last node of the list contains the address of the first node of the list. The first node of the
list also contain address of the last node in its previous pointer.
MEMORY MANAGEMENT OF CIRCULAR
DOUBLY LINKED LIST• The variable head contains the address of the first
element of the list i.e. 1 hence the starting node of
the list contains data A is stored at address 1.

• Since, each node of the list is supposed to have

three parts therefore, the starting node of the list
contains address of the last node i.e. 8 and the
next node i.e. 4.

• The last node of the list that is stored at address 8

and containing data as 6, contains address of the
first node of the list as shown in the image i.e. 1.

• In circular doubly linked list, the last node is

identified by the address of the first node which is
stored in the next part of the last node therefore
the node which contains the address of the first
node, is actually the last node of the list.
INSERTION: CIRCULAR DOUBLY LINKED LIST AT
BEGINNING
• Allocate the memory space for the new node ptr by using the following statement.
ptr = (struct node *)malloc(sizeof(struct node));

Senerio 1: List is empty  head == NULL

head = ptr;

ptr -> next = head;

ptr -> prev = head;
INSERTION: CIRCULAR DOUBLY LINKED LIST AT
BEGINNING
Scenario 2: contains more than one element in the list:
temp = head;
//we need to reach the last node of the list through traversing the list
while(temp -> next != head) {
temp = temp -> next;
}

temp -> next = ptr;

ptr -> prev = temp;
head -> prev = ptr;
ptr -> next = head;
head = ptr;
void insertBegining(int item) {
struct node *ptr = (struct node *)malloc(sizeof(struct node));
struct node *temp;
ptr->data=item;

if(head==NULL) {
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else {
temp = head;
while(temp -> next != head) {
temp = temp -> next;
}
temp -> next = ptr;
ptr -> prev = temp;
head -> prev = ptr;
ptr -> next = head;
head = ptr;
}
printf("Node Inserted"); }
INSERTION: CIRCULAR DOUBLY LINKED LIST AT
END
Scenario 1: the list contains more than one element
void insertion_last(int item) {
struct node *ptr = (struct node *) malloc(sizeof(struct node));
struct node *temp;
ptr->data=item;

if(head == NULL) {
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else {
temp = head;
while(temp->next !=head) {
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
head -> prev = ptr;
ptr -> next = head;
}
printf("\nNode Inserted\n"); }
DELETION: CIRCULAR DOUBLY LINKED LIST AT
BEGINNING
Scenario 1: The node which is to be deleted can be the only node present in the linked list.
head → next == head //needs to be completely deleted
head = NULL;
free(head);

Scenario 2: The list contains more than one element in the list

temp = head;
// reach the last node of the list
while(temp -> next != head) {
temp = temp -> next;
}
temp -> next = head -> next;
head -> next -> prev = temp;
free(head);
head = temp -> next;
void deletion_beginning() {
struct node *temp;

if(head->next == head) {
head = NULL;
free(head);
printf("\nNode Deleted\n");
}
else {
temp = head;
while(temp -> next != head) {
temp = temp -> next;
}
temp -> next = head -> next;
head -> next -> prev = temp;
free(head);
head = temp -> next;
printf("\nNode Deleted\n");
}
DELETION: CIRCULAR DOUBLY LINKED LIST AT
END
The node which is to be deleted can be the The list contains more than one element in the list
only node present in the linked list head →
temp = head;
next == head
while(temp -> next != head) {
head = NULL;
temp = temp -> next;
free(head);
}
void deletion_last() {
struct node *ptr;

if(head->next == head) {
head = NULL;
free(head);
printf("\nNode Deleted\n");
}
else {
ptr = head;
if(ptr->next != head)
{
ptr = ptr -> next;
}
ptr -> prev -> next = head;
head -> prev = ptr -> prev;
free(ptr);
printf("\nNode Deleted\n");
}
}