Circular linked list in C

A circular linked list is a linked list in which the head node’s previous pointer points to the tail node, and the tail node’s next pointer points to the head node. This means that the list only needs to keep track of one pointer for both head and tail.

A circular linked list containing elements labelled A to F

Looping over a circular linked list is slightly different from looping over an ordinary linked list because there is no NULL node to detect, and instead you are trying to get back to where you started. There are 2 methods of doing this.

Method 1: Use a do loop

void iterate1(const circularlist *list)
{
    cnode *node = list->head;
    if (node != NULL) {
        do {
            printf("%s\n", (const char*)node->data);
            node = node->next;
        } while (node != list->head);
    }
}

Method 2: Use a counter

void iterate2(const circularlist *list)
{
    cnode *node;
    unsigned int i;
    for (i = 0, node = list->head; i < list->count; i++, node = node->next) {
        printf("%s\n", (const char*)node->data);
    }
}

Here is the header file for the circular linked list

#ifndef CIRCULARLIST_H
#define CIRCULARLIST_H

struct cnode {
	struct cnode * next;
	struct cnode * previous;
	void * data;
};
typedef struct cnode cnode;

struct circularlist {
	cnode * head;
	unsigned int count;
};
typedef struct circularlist circularlist;

typedef void (*circularlist_forfn)(void *);

circularlist * circularlist_create(void);
void circularlist_delete(circularlist * list);

void circularlist_add_head(circularlist * list, void * data);
void circularlist_add_tail(circularlist * list, void * data);
void * circularlist_remove_head(circularlist * list);
void * circularlist_remove_tail(circularlist * list);
void * circularlist_remove_node(circularlist * list, cnode * node);
void circularlist_empty(circularlist * list);

void circularlist_insert_before(circularlist * list, cnode * node, void * data);
void circularlist_insert_after(circularlist * list, cnode * node, void * data);

void circularlist_for_each(const circularlist * list, circularlist_forfn fun);
unsigned int circularlist_get_count(const circularlist * list);

#endif /* CIRCULARLIST_H */

Here is the implementation

#include <stdlib.h>

#include <circularlist.h>

static cnode * cnode_create(void * data)
{
	cnode * node = malloc(sizeof(cnode));
	if(node) {
		node->next = node;
		node->previous = node;
		node->data = data;
	}

	return node;
}

static void cnode_delete(cnode * node)
{
	free(node);
}

circularlist * circularlist_create(void)
{
	circularlist * list = malloc(sizeof(circularlist));
	if (list) {
		list->head = NULL;
		list->count = 0;
	}

	return list;
}


void circularlist_delete(circularlist * list)
{
	if (list) {
		circularlist_empty(list);
		free(list);
	}
}

void circularlist_add_head(circularlist * list, void * data)
{
	circularlist_insert_before(list, list->head, data);
	list->head = list->head->previous;
}

void circularlist_add_tail(circularlist * list, void * data)
{
	circularlist_insert_before(list, list->head, data);
}

void * circularlist_remove_head(circularlist * list)
{
	return circularlist_remove_node(list, list->head);
}

void * circularlist_remove_tail(circularlist * list)
{
	void * data = NULL;
	if (list->head) {
		data = circularlist_remove_node(list, list->head->previous);
	}
	return data;
}

void * circularlist_remove_node(circularlist * list, cnode * node)
{
	void * data = NULL;
	if (list->count > 0) {
		if (node != node->next) { /* Or, list->count > 1 */
			node->next->previous = node->previous;
			node->previous->next = node->next;
			if (node == list->head)
				list->head = list->head->next;
		}
		else {
			/* Removing the last element */
			list->head = NULL;
		}
		data = node->data;
		cnode_delete(node);
		list->count--;
	}
	return data;
}

void circularlist_empty(circularlist * list)
{
	while (circularlist_remove_tail(list) != NULL);
}

void circularlist_insert_before(circularlist * list, cnode * node, void * data)
{
	cnode * newnode = cnode_create(data);

	if (newnode) {
		if (list->count > 0) {
			newnode->next = node;
			newnode->previous = node->previous;
			newnode->previous->next = newnode;
			node->previous = newnode;
		}
		else {
			/* Adding the first element */
			list->head = newnode;
		}
		list->count++;
	}
}

void circularlist_insert_after(circularlist * list, cnode * node, void * data)
{
	circularlist_insert_before(list, node->next, data);
}

void circularlist_for_each(const circularlist * list, circularlist_forfn fun)
{
	cnode * node = list->head;

	if (node != NULL) {
		do {
			fun(node->data);
			node = node->next;
		} while (node != list->head);
	}
}

unsigned int circularlist_get_count(const circularlist *list)
{
	return list->count;
}

Here is a test program

#include <stdio.h>
#include <string.h>

#include <circularlist.h>

int main(void)
{
    char * elements[] = {"A", "B", "C", "D", "E", "F"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);
    circularlist * list;
    unsigned int i;
    cnode * node;
    unsigned int removed = 0, added = 0;

    list = circularlist_create();
    if (list) {
        /* Populate the list */
        for (i = 0; i < n; i++) {
            circularlist_add_tail(list, elements[i]);
        }

        /* Remove "C" */
        node = list->head;
        do {
            if (strcmp((const char*)node->data, "C") == 0) {
                circularlist_remove_node(list, node);
                removed = 1;
            }
            else {
                node = node->next;
            }
        } while (node != list->head && !removed);

        /* Add "X" and "Y" either side of "D" */
        node = list->head;
        do {
            if (strcmp((const char*)node->data, "D") == 0) {
                circularlist_insert_before(list, node, "X");
                circularlist_insert_after(list, node, "Y");
                added = 1;
            }
            else {
                node = node->next;
            }
        } while (node != list->head && !added);

        /* Print */
        printf("Count is %d\n", circularlist_get_count(list));
        circularlist_for_each(list, (circularlist_forfn)puts);

        circularlist_delete(list);
    }
    return 0;
}