In the previous post on singly and doubly linked lists, recall that the collections last nodes next pointers were always NULL. This is because they had nothing to point to. But what if this is not what we wanted? What if when we get to the last node, we wanted to point the next pointer back to the head node, like a photo gallery application (when we get to the last picture, the next picture should be the first). This is where circular linked lists come from (they allow us to rotate through our collection). This means that circular linked lists have no end. One must be careful if they are going to iterate through the collection, or you could end up in an infinite loop.

So in a circular linked list, there are no nodes with a NULL pointer. For eg, in a case where there is only one node (the head node), the next pointer points back to itself. Remember in previous posts that i said when a collection is empty and you add a new node, their next and previous pointers are NULL? Well in this type of linked list, they point back to itself, well until we change its pointers.

What about the previous node of the head? Remember it was NULL in previous posts? There is another type of linked list called doubly circular linked list (i know, the names are getting ridiculous). In a doubly circular linked list, the previous pointer of the head points to the tail node. Let’s look at a diagram.

In figure A we see a circular linked list, where the tail nodes next pointer, points back to the head. In figure B we see a doubly circular linked list, where head’s previous point back to the tail.

Here are some pointers to working with circular linked lists. Start off with a doubly linked list implementation. From there, the only things that change are the pointers of the head and/or tail of the collection. These are no longer NULL. When implementing methods like removeHead, removeTail, addToHead and addToTail all you have to do is take account of these new pointer references and re-position them. Another thing to be careful about is when iterating through the node collection. Since there is no end, you can run into an infinite loop. For example beginning a search from the head, you need to always check to see if the current nodes next element is not the head. If it is, then you would have reached the end and you need to stop the loop (you started from the head, no need to search again)

We will not be writing any code in this post. We have already seen how to do everything in the previous posts. Now that you know what a circular linked list is, you can augment your doubly linked list to have this functionality. My advice is do what i did. First draw the diagram. For example, lets assume you have a diagram of adding a node to the end of a circular linked list collection. (Try to draw it now) With the above diagram in mind, imagine that you add that you add a new node to the end of the collection. Because that new node is unaware of the other nodes in the collection, it has a pointer back to itself (lonely node it is). What we do first is update the next pointer of the new node to the head node of the collection. Since we are adding the node to the end of the list, we need to point the next pointer to the head. Then we need to find the current tail of the collection. We traverse all the nodes till we get to it, then we update its next pointer of the tail to the newly added node (making the newly added node the tail). Thats it! Drawing diagrams always help solve problems. So give this a try. Make sure you have all the code from the previous posts and build on top of that to create your circular linked list.

This brings us to an end of the linked lists tutorial series. I really hope you enjoyed them. Lets move onto other data structures. Feel free to reach out on twitter as well ( @scriptonian ) if you have any questions.