Circular Linked list in Data structures
- A circular list is a list in which the link field of the last node is made to point to the start/first node of the list.
- In a circular linked list, the last node contains a pointer to the first node of the list. We can have a circular singly linked list as well as a circular doubly linked list.
- While traversing a circular linked list, we can begin at any node and traverse the list in any direction, forward or backward, until we reach the same node where we started. Thus, a circular linked list has no beginning and no ending.
- It is just a singly linked list in which the link field of the last node contains the address of the first node of the list.
- That is, the link field of the last node does not point to NULL rather it points back to the beginning of the linked 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. We will now discuss an example where a circular linked list is used.
- When we are surfing the Internet, we can use the Back button and the Forward button to move to the previous pages that we have already visited.
- A circular linked list has no end. Therefore, it is necessary to establish the FIRST and LAST nodes in such a linked list.
In C, the structure of a doubly linked list can be given as,
struct node*next ;
typedef struct Node node ;
node * start = NULL ;
node * last = NULL ;
Inserting a New Node in a Circular Linked List
In this section, we will see how a new node is added into an already existing linked list. We will take two cases and then see how insertion is done in each case.
- The new node is inserted at the beginning of the circular linked list.
- The new node is inserted at the end of the circular linked list.
Deleting a Node from a Circular Linked List
In this section, we will discuss how a node is deleted from an already existing circular linked list. We will take two cases and then see how deletion is done in each case. Rest of the cases of deletion are same as that given for singly linked lists.
- The first node is deleted.
- The last node is deleted