How many null pointers in circular linked list

A circular linked list has one slight modification over the singly linked list, the last element in the list points back to the first of the list. This allows for reaching the first element without starting over while traversing. There is no NULL pointer to mark the end of a linked list.

Table of Contents Show

Defining the Node
Insertion at the end of the list
Insertion at the beginning of the list
Insertion after an element in the list
Deletion from the end of the list
Deletion from the beginning of the list
Deletion of a specific element in the list
Applications in Programming

Circular Linked List
Lasindi [Publidomain]

Any node in a Circular Linked List can be taken as a starting point. The whole list can be traversed by starting from this one node.

Defining the Node

struct Node { int data; struct Node *next; } *head = NULL;

The few basic operations in a linked list including adding, deleting and modifying.

Insertion at the end of the list

New data can be added to the end of the linked list by creating a new node with the data to be used, traversing to the end of the list and then appending this data to the end.

Steps

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 successful"); }

Insertion at the beginning of the list

New data can be added to the beginning of the linked list by creating a new node with the data to be used, replacing the head pointer to the new node and replacing the connections.

Steps

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 successful"); }

Insertion after an element in the list

New data can be added at any position in the list by traversing to that position using a loop, creating a new Node and then manipulating the links to insert it at that position.

Steps

void insertAfter(int value, int location) { 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 -> data != location) { if(temp -> next == head) { printf("Given node is not found in the list"); } else { temp = temp -> next; } } newNode -> next = temp -> next; temp -> next = newNode; printf("\nInsertion successful"); } }

Deletion from the end of the list

New data can be added to the end of the linked list by creating a new node with the data to be used, traversing to the end of the list and then appending this data to the end.

Steps

void deleteEnd() { if(head == NULL) printf("List is Empty"); else { struct Node *temp1 = head, *temp2; if(temp1 -> next == head) { head = NULL; free(temp1); } else{ while(temp1 -> next != head){ temp2 = temp1; temp1 = temp1 -> next; } temp2 -> next = head; free(temp1); } printf("\nDeletion successful"); } }

Deletion from the beginning of the list

New data can be added to the beginning of the linked list by creating a new node with the data to be used, replacing the head pointer to the new node and replacing the connections.

Steps

void deleteBeginning() { if(head == NULL) printf("List is Empty"); else { struct Node *temp = head, *last = NULL; if(temp -> next == head) { head = NULL; free(temp); } else{ while(temp -> next != head) temp = temp -> next; last = temp; temp = head; head = head -> next; free(temp); last -> next = head; } printf("\nDeletion successful"); } }

Deletion of a specific element in the list

New data can be deleted at any position in the list by traversing to that position using a loop, deleting the required Node and then manipulating the links to make the list continuous.

Steps

void deleteSpecific(int delValue) { if(head == NULL) printf("List is Empty"); else { struct Node *temp1 = head, *temp2; while(temp1 -> data != delValue) { if(temp1 -> next == head) { printf("\nGiven node is not found in the list"); } else { temp2 = temp1; temp1 = temp1 -> next; } } if(temp1 -> next == head){ head = NULL; free(temp1); } else{ if(temp1 == head) { temp2 = head; while(temp2 -> next != head) temp2 = temp2 -> next; head = head -> next; temp2 -> next = head; free(temp1); } else { if(temp1 -> next == head) { temp2 -> next = head; } else { temp2 -> next = temp1 -> next; } free(temp1); } } printf("\nDeletion successful"); } }

Applications in Programming

Operating Systems: The Operating System keeps track of all the currently running processes in the system in a circular list. These processes are given a fixed time slot by the processor to perform its operations. The circular list allows the OS to repeatedly iterate over the linked list until all the processes have completed execution.
Implementing Circular Queue: A circular queue reduces the complexity of maintaining 2 pointers in the regular linear queue.

We have discussed singly and doubly linked lists in the following posts.

Introduction to Linked List & Insertion
Doubly Linked List Introduction and Insertion

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

Advantages of Circular Linked Lists:
1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.

2) Useful for implementation of queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.

3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.

4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

Next Posts :
Circular Linked List | Set 2 (Traversal)
Circular Singly Linked List | Insertion

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem

Article Tags :

Practice Tags :