C Circular Linked Lists

Page 1 of 2

Author: Brian Moriya Published on: 26th Jun 2011

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.

Ads

A cingularly linked list node looks exactly the same as a linear singly linked list. Here's the node for the example programming example.

Sample Code

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.

Sample Code

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

Sample Code

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.

Ads

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.

1 2

Read Next: C Programming - Data Types : Part 2

This tutorial is part of a C Tutorials tutorial series. Read it from the beginning and learn yourself.

C Tutorials