EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Circular Linked List in Data Structure
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Circular Linked List in Data Structure

By Savi JaggaSavi Jagga

Circular Linked List in Data Structure

Introduction to Circular Linked List

A circular linked list data structure is formed to store the collection of elements, by pointing the start element’s location to next of the last element, which is known to form a circular linked list. Most operating system operations are required to be performed repeatedly, thus needing to be maintained in a queue where it can wait if any of the required resources are currently acquired by other ongoing processes. Instead of maintaining FIRST and the LAST pointer, only one pointer needs to be maintained HEAD to detect the visited node.

Circular Linked List in Data Structure 2

Types of Circular Linked List in Data Structure

Circular Linked list is a linked list with no end thus used to perform various continuous operations. With this one HEAD pointer of Node, a type is maintained to identify if all the list nodes have been visited. A circular linked list can be easily made by allocating the first node’s address to the next of the last node. Below is the pseudo-code for its nodes.

There are 2 Types of Circular Linked Lists:

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

  • Singly Circular Linked List
  • Doubly Circular Linked List

1. Singly Circular Linked List

The type of circular linked list whose every node has a pointer to its next node only is known as a singly circular linked list.

Doubly

Syntax:

struct Node{
char data;
struct Node* next;
}

Here next is the pointer that points to the next node in the list.

All in One Data Science Bundle(360+ Courses, 50+ projects)
Python TutorialMachine LearningAWSArtificial Intelligence
TableauR ProgrammingPowerBIDeep Learning
Price
View Courses
360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (86,171 ratings)

2. Doubly Circular Linked List

The type of circular linked list whose every node contains the pointer that points to its next and the next node in the list. And since it is a circular list, the last node contains the first node’s address in its next pointer, and the first node contains the address of the last node in the previous pointer.

Doubly Circular Linked List

Syntax:

struct Node{
char data;
struct Node* next;
struct Node* prev;
}

Here, a pointer points to the previous node in the linked list and next pointer points to the next node in the list. Such type of linked list in implementation of various other complex data structures.

Operations of Circular Linked List in Data Structure

Operations that can be performed on a circular linked list:

1. Insertion

INSERTFROMSTART(A,n,Head,LOC)

  • Create a node T.
  • Insert data to be inserted such as, T[data] =data and T[next] = HEAD[next].
  • IF HEAD =NULL, i.e. empty list, Set HEAD =T and exit.
  • Else if LOC = length of A, ie. Insertion of the last node, then traverse till last of list A using ptr and then T->next = ptr->next, ptr->next =T.
  • Else if LOC =1, in the beginning, T->next =HEAD and HEAD=T.
  • Else if traverse to the LOC and T->next = A[LOC] ->next A[LOC] -> next =T.

This algorithm takes a circular linked list A and HEAD pointer as well as n as a data to be inserted and LOC points to the location where n needs to be inserted. Here we assume, that LOC has been calculated by traversing the whole list once and maintaining a counter LOC that is updated till we find the node after which we need to insert a new node. Then a new node T is created. The first list is checked if it is null then, HEAD is updated, and it indicates there is only one element in the list after insertion. Otherwise, relevant pointers are updated to insert the node at the beginning or end or in between.

2. Deletion

DELETE(A,n,HEAD,LOC)

  • Check if list A is empty the return -1 [UnderFlow].
  • Otherwise call traverse the list to location  LOC of a node with Node[data]=n.
  • If LOC =-1, return -1 and exit.
  • Else If LOC == 1 .ie first node:- Set Head =NULL and exit.
  • Else A[LOC -1]->next = A[LOC]->next.

This algorithm checks first if the given list is empty then indicates, and Underflow situation otherwise checks at which location deletion needs to be performed and update the pointer accordingly.

3. Traversal

TRAVERSE(A, HEAD)

  • take a ptr =HEAD
  • Repeat Steps 3 and 4 till ptr->next !=HEAD
  • Print[ptr]
  • ptr=ptr->next

This algorithm is used to traverse the whole circular linked list and perform a print operation for each node using a pointer ptr that points to the current node of the list. The condition ptr->next !=HEAD is used to observe if any node is not traversed twice.

Benefits of Circular Linked List in Data Structure

  1. One can start traversal of the complete linked list from any node since all nodes are lined, and there is no endpoint. While traversal, we need to observe not to traverse one node twice.
  2. Such data structure is most often used for implementing a queue, and since it is a circular list, only one pointer needs to be maintained, i.e. HEAD to store the last inserted node that marks as REAR and FRONT can easily be found.
  3. Doubly Circular linked lists can also be used to implement various complex data structures such as Fibonacci Heap.
  4. OS also uses it to maintain the execution of the various process to run the list continuously. A continuous queue is maintained running with a continuous loop, where each process enters once the CPU is busy and not available. Such a queue is also known as the waiting queue. Various other queues such as priority queue or resources queue are also maintained using this data structure.
  5. Such data structure can also be used in case of multiplayer games where all the players are entered in a continuous circular linked list and the pointer gets incremented once every player’s chance is over.
NOTE: This type of list must be traversed carefully so that one may not end up in an infinite loop.

Conclusion

A circular linked list is a type of data structure where a loop is maintained used by storing the first node of the list in the last node of the linked list, thus named circular. Such a list helps build a continuous loop used in various games or complex data structures such as the Fibonacci series.

Recommended Articles

This is a guide to Circular Linked List in Data Structure. Here we discuss Circular Linked List operations in Data Structure and its types along with its Code Implementation. You can also go through our other suggested articles to learn more –

  1. Stack in Data Structure?
  2. Linked List in Data Structure
  3. Doubly linked list in Data Structure
  4. Working of Linked List in C
Popular Course in this category
All in One Data Science Bundle (360+ Courses, 50+ projects)
  360+ Online Courses |  1500+ Hours |  Verifiable Certificates |  Lifetime Access
4.7
Price

View Course

Related Courses

Oracle DBA Database Management System Training (2 Courses)4.9
SQL Training Program (7 Courses, 8+ Projects)4.8
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more