In this tutorial you will learn about C Programming – What is Circular Linked List, Adding Nodes to Circular Linked Lists, Traversing a Circularly Linked List and working with Circularly Linked List Example.
Circular linked lists are usually used for a queue or stack type situation, or for implementing a round robin algorithm in system level programming. You could also use one for a multiplayer game where you were keeping track of player’s turns where it just repeats until the game ends.
They are exactly the same as a singly linked list, but instead of setting the next pointer in the last node of the list to NULL, you set it to point to head. Hence the name circular. Instead of a head pointer, they commonly use a tail pointer instead to keep track of the last node.
struct cllnode {
char name[4];
struct cllnode *next;
};
It should be familiar from the previously introduced linear linked list, just a data portion and the next pointer.
Adding Nodes to Circular Linked Lists
Adding nodes and creating new circularly linked lists is very similar to the linear ones we learned previously. Let’s look at our example to illustrate.
void addNode(struct cllnode *newnode) {
//List is empty. Create new list.if (tail == NULL) {
tail = newnode;
newnode->next = tail;
} else {
//List isn't empty so add at the tail. Remember "first in first out."newnode->next = tail->next;
tail->next = newnode;
tail = newnode;
}}
That addNode function is all it takes to handle both the empty and non-empty singularly linked list cases when adding new nodes. You add at the back of the list in this linked list case and that’s one of the reasons these are used for modeling queues and FIFO stacks.
Just as in the singularly linked list case you first check if the list pointer (no matter what you are calling it) is NULL. Then set the tail equal to the new node being added and make its pointer point back at itself, thus completing the circle.
When there are nodes in the list, you first set the new node’s next pointer to tail->next because you are adding it just after tail, not at tail. You may be able to see why we use tail pointers rather than head pointers for circularly linked lists. The head would be 2 pointers away from where we perform insertions.
After that, you set tail’s next pointer to the new node and set tail equal to the new node. Viola, we have inserted a new node at the end of the list, and tail is now pointing at it.
Traversing a Circularly Linked List
Traversing a circularly linked list is a little different than the regular type, due to the fact that there is no NULL termination to tell you when to stop. However, we can just use the tail pointer for this purpose as well.
As we see in this snippet of our example program, it’s not any more difficult to traverse, it’s just different
if (tail != NULL) {
current = tail->next;
while (current != tail) {
...
current = current->next;
}current = tail;
...
}
We begin with the familiar check for the list’s existence. If we have a list, we set the current pointer to the node after tail. From here we can just go through the nodes until we return to tail, so we use a while loop to do that. The traversal is the same as before in that you just set the current pointer to the next one at the end of the wile loop.
Now if you want to do something when you get to the tail you must do it after the while loop traversal, because our condition stopped the traversal at the node just before tail and started just after it. As you can see we had to add an addition print out block after the while loop to be able to see the last node’s information printed out.
This example models a turn based game with four players. It creates a circularly linked list of the four players, and starts traversing through the list for each player’s turn, giving them a prompt when it reaches them.
Note the first player joins gets their turn first, and the last player gets his turn at the end. This is the queue behavior of the circularly linked list.
#include <stdio.h>#include <stdlib.h>struct cllnode {
char name[4];
struct cllnode *next;
};
//The circular linked list tail pointer.struct cllnode *tail = NULL;
void addNode(struct cllnode *newnode) {
//List is empty. Create new list.if (tail == NULL) {
tail = newnode;
newnode->next = tail;
} else {
//List isn't empty so add at the tail. Remember "first in first out."newnode->next = tail->next;
tail->next = newnode;
tail = newnode;
}}void main() {
int i;
char players[4][4] = {
"Bob", "Tom", "Tim", "Joe"
};
//Use this node for traversing the list.struct cllnode *current;
//Create a circularly linked list for the playersfor (i = 0; i < 4; i++) {
//Create node for each of the players in the players array.struct cllnode *newnode;
newnode = (struct cllnode *)malloc(sizeof(struct cllnode));
strcpy(newnode->name, players[i]);
//Add the 4 players to the queue.addNode(newnode);
}//Check that list isn't empty.if (tail != NULL) {
//Set node to the first item in the list.current = tail->next;
//Go around the loop until we return to the tail pointer.while (current != tail) {
printf("It's your turn: ");
puts(current->name);
printf("n");
sleep(3);
//traverse the list.current = current->next;
}//Have to print tail separately.current = tail;
printf("It's your turn: ");
puts(current->name);
printf("n");
sleep(3);
//Clean up current.current = NULL;
}}
When you compile and run this example, you should see the first message saying that it’s the first player’s turn. The program will pause for 3 seconds before moving on through the rest of the players’ turns.
The output of the above code if unmodified should look like this after it finishes.
