Circular linked lists - Attributes, Implementation and Uses

What is a Circular Linked List

A Circular Linked List is a linked list in which the last node in the list points to the first node in the list. This property makes it circular.

This is shown in the figure below - the last node in the linked list points to the head node of the list, making it circular.

A Circular Linked list

Uses of a Circular Linked List

1. Circular linked lists are a natural option to represent something circular or a set of objects that form a loop. 
2. In a circular linked lists you can have easy access to end of the list. This gives you flexibility to add or delete elements at both ends of the list in a quick manner. This attribute comes in handy in a variety of situations.
3. Another attribute of a circular linked list is that a pointer to any node in the list gives you the ability to traverse the whole length of the list. This flexibility is not available in a normal single linked list where one needs the pointer to the head of the list to traverse the whole length of the linked list.
4. An interesting feature of a circular linked list is that one can create two circular linked list out of a single circular linked list in constant time. This can be done by simply swapping the next pointers of the two nodes that would form the tail nodes of the newly constructed circular linked lists. In a similar manner, if you swap the next pointers of a last nodes of two separate circular linked lists, you are merging the two lists into a single circular linked list in a constant time operation.
5. Circular linked lists can be normally used where a resource needs to shared among a number of users in a round robin manner. 
6. A good example of this is how an operating system can schedule CPU resources among processes in round robin manner.

          Another example is a multi-player game where the chance to play the game passes around                     the players in round robin manner.

Linux Kernel Implementation of a Circular linked list

Linux kernel code uses circular linked lists extensively and so the circular linked list implementation in the linux kernel is a good case study in implementation and usage of a circular linked list.

Linux kernel implements a doubly linked circular linked list.

The definition of the list structure in linux looks like this 

struct list_head {
 struct list_head *next, *prev;
};

The list head structure shown above represents the link of a particular node in the list. To implement a circular linked list using this, one needs to embed this structure in another structure that would hold the information associated with the node.

e.g.
Let's say, you want to build a circular linked list in which each node would store an integer as information. Let's call this list circular_int_list. Using Linux Kernel's list_head, you would declare your list structure as follows

typedef struct circular_int_list
{
        int info;
        struct list_head list;
};

This structure represents a single node in the linked list. Linux implementation provides a number of functions to manipulate and use a linked list. Let's go through them one by one and at the same time performing certain operations on our circular linked list shown above.

So, let's say you want to start off by creating the first node in the list. The steps for this are:

1. Allocate memory for the node
2. Call linux Kernel's INIT_LIST_HEAD() function, passing it the address of the list element of your node. This function initializes the circular linked list. This means that the node is now the first element in the list. Since this is a doubly circular linked list, the node is also the last element in the list and the prev and next pointer of the list structure point to the node itself.

The code for above steps is given below:

/* Step 1
 * Declare the list and allocate memory 
 * for the first node
 */
struct circular_int_list *mylist;
mylist = (struct circular_int_list *) malloc(sizeof(struct circular_int_list));

/* Step 2
 * Call the INIT_LIST_HEAD() to initalize the list 
 */
INIT_LIST_HEAD(&(mylist->list));

The code for INIT_LIST_HEAD() is simple and is shown below:

void INIT_LIST_HEAD(struct list_head *list)
{
 list->next = list;
 list->prev = list;
}

Side Note: All the linux kernel code shown here can be found online and the relevant links are provided at the end of this post.

Now let's look at functions used for adding a new node to the list:
To add an new element to the list, list_add() function is provided. It's first argument is pointer to the new node that is to be added and second argument is pointer to the node in the list after which you want to add the new node. Point to note here is that you can provide any node in the list and the new node is going to be added after that node.
If you always provide the same node to insert after, you get insertion of the new nodes in stack fashion.

e.g.

list_add(&(newnode->list), &(mylist->list));

Implementation of list_add() function is given below:

void list_add(struct list_head *new, struct list_head *head)
{
 __list_add(new, head, head->next);
}

void __list_add(struct list_head *new,
         struct list_head *prev,
         struct list_head *next)
{
 next->prev = new;
 new->next = next;
 new->prev = prev;
 prev->next = new;
}

There is also a function list_add_tail(). This inserts the new node just behind the head. Use this function if you want to implement a queue.

For deleting a node from the list, there is list_del() function. The only argument it needs is the pointer to the node which you want to remove from the list.

list_del(&(newnode->list));

Implementation of the list_del() function is given below:

void list_del(struct list_head *entry)
{
 __list_del(entry->prev, entry->next);
 entry->next = LIST_POISON1; 
 entry->prev = LIST_POISON2;
}

void __list_del(struct list_head * prev, struct list_head * next)
{
 next->prev = prev;
 prev->next = next;
}

LIST_POISON1 and LIST_POISON2 are non null pointers that would result in page-faults in case somebody tries to access them.

Linux kernel provides many different ways in which you can iterate over a given list. Let's look here at one of them: list_for_each_entry().

If I wanted to print integer values stored as information in the list I have defined above, here is how I would use the list_for_each_entry macro to traverse the list :

struct mylist *listnode;

list_for_each_entry(listnode,&mylist, list)
{
        printf("%d \n",listnode->info);
}

As you can see, the code above is clean and elegant.

The list_for_each_entry() macro is implemented as shown below:-

#define list_for_each_entry(pos, head, member)    \
 for (pos = list_entry((head)->next, typeof(*pos), member); \
      &pos->member != (head);  \
      pos = list_entry(pos->member.next, typeof(*pos), member))

#define list_entry(ptr, type, member) \
 container_of(ptr, type, member)

#define container_of(ptr, type, member) ({   \
 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
 (type *)( (char *)__mptr - offsetof(type,member) );})

list_entry() macro used above gives back the structure that contains the element given to it as its first argument.  It internally uses the container_of() macro.

These are just some of the many different operations that linux kernel allows on its circular linked list. For those who revel in reading code, I would greatly recommend going through the entire list file.

Linux kernel implementation of circular linked list seems to have been made in such a manner that the list structure and list operations themselves remain an abstraction don't meddle with the information stored in each node.
The generic nature allows for the same list structure to be used in different types of situations without ever changing how the list operations are done.
You can embed the list_head structure in any structure and you have got a linked list, a circular one at that !

Linked lists are widely used in Linux code. You would find a single structure containing multiple list_head structures, indicating that a single node is part of multiple linked lists. This is quite good, since the information resides at only one place in memory while it is part of multiple linked lists.

e.g. The task_struct structure in linux kernel, the structure that stores all the information of a process, contains multiple linked lists inside itself. The kernel itself uses one of these lists to manage different tasks.

struct task_struct 
{
        .
        .

        /*
         * List of tasks 
         */
 struct list_head tasks;

 /*
  * children/sibling forms the list of my natural children
  */
 struct list_head children; /* list of my children */
 struct list_head sibling;  /* linkage in my parent's children list */
        .
        .
        .
};

We have looked at circular linked lists - its uses and one of its most used implementations in the software world. To those who are interested, I would strongly recommend browsing linux kernel code to discover more.

References:

1. Code : Linux Kernel Code (version 3.9.8)
2. Book : Linux Kernel Development by Robert Love
3. Linked list Wikipedia Article