Circular doubly linked list in C

 A linked list data structure can be doubly-linked as well as circular. In this article, a simple implementation of doubly linked list in C language is presented.

Environment

The source code is written and executed in the following environment,

• Operating System - Windows 11
• Compiler - GCC 8.1.0
• Editor - Visual Studio code

The first step is to define the data structure. For a circular doubly linked list there is just one structure defined which is type casted and re-used as a head of the linked list.

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

struct entry {
   int data;
   struct entry *prev;
   struct entry *next;
};

typedef struct entry head;
typedef struct entry entry;

There are three functions written to initialize the head, allocating and initializing an entry with the given input data. Since the list is circular, the initial state of the list is just the head pointing to itself in both forward and reverse directions.

void init_head(head *h)
{
   h->next = h;
   h->prev = h;
}

void init_entry(entry *e, int data)
{
   e->data = data;
   e->next = NULL;
   e->prev = NULL;
}

entry* alloc_entry(int data)
{
   entry *e = malloc(sizeof(*e));
   if (e != NULL) {
      init_entry(e, data);
   }
   return e;
}

To check if the list is empty, a comparison is made to check whether the list is in the initial state ie., head pointing to itself.

int is_empty(head *h)
{
   return (h->next == h && h->prev == h);
}

Coming to insertion of the elements to the list, two separate functions are provided to add elements to the first or last position of the list. These operations are done on constant time ie. O(1) time. For adding at the first of the list, the entry is linked just next to the head and for adding at the last of the list, the entry is hooked to the previous of the list. Every insertion adjusts four pointers in the list.

void add_at_first(head *h, entry *e)
{
   e->next = h->next;
   e->prev = h;
   h->next->prev = e;
   h->next = e;
}

void add_at_last(head *h, entry *e)
{
   e->prev = h->prev;
   e->next = h;
   h->prev->next = e;
   h->prev = e;
}

On the contrary, three separate functions are added for removing elements from the list. One to remove from the first of the list, one to remove from the last of the list and one to remove any element as long the element pointer is known. Every deletion adjusts only two pointers in the list and also happens in O(1) time.

int remove_first(head *h)
{
   entry *e = h->next;
   int data = e->data;

   e->next->prev = h;
   h->next = e->next;
   free(e);
   return data;
}

int remove_last(head *h)
{
   entry *e = h->prev;
   int data = e->data;

   e->prev->next = h;
   h->prev = e->prev;
   free(e);
   return data;
}

int list_remove(entry *e)
{
   int data = e->data;
   e->next->prev = e->prev;
   e->prev->next = e->next;
   free(e);
   return data;
}

There are two functions added to print the list to verify our tests. One that prints using the next pointer and the other that prints the list using the previous pointer. By traversing the list in both the directions, any broken links can be identified using the test.

void print_list_reverse(head *h)
{
   entry *e = h->prev;
   printf("Contents (Reverse): ");
   while (e != h) {
      printf("%d -> ", e->data);
      e = e->prev;
   }
   printf("\n");
}

void print_list(head *h)
{
   entry *e = h->next;
   printf("Contents (Forward): ");
   while (e != h) {
      printf("%d -> ", e->data);
      e = e->next;
   }
   printf("\n");
   print_list_reverse(h);
}

A set of unit tests are coded, to verify all the coded procedures. The tests include insertion at either ends, deletion at either ends and deletion in between the list.

void list_add_first_test(head *h, int data)
{
   entry *e = alloc_entry(data);
   add_at_first(h, e);
   print_list(h);
}

void list_add_last_test(head *h, int data)
{
   entry *e = alloc_entry(data);
   add_at_last(h, e);
   print_list(h);
}

void list_remove_fist_test(head *h, int expected)
{
   int data = remove_first(h);
   assert(data == expected);
   print_list(h);
}

void list_remove_last_test(head *h, int expected)
{
   int data = remove_last(h);
   assert(data == expected);
   print_list(h);
}

void run_unit_tests(head *h)
{
   init_head(h);
   print_list(h);
   list_add_first_test(h, 10);
   list_add_last_test(h, 20);
   list_add_first_test(h, 30);
   list_add_last_test(h, 40);
   list_add_first_test(h, 50);
   list_add_last_test(h, 60);
   list_remove_fist_test(h, 50);
   list_remove_last_test(h, 60);
   list_remove(h->next->next);
   print_list(h);
}

int main()
{
   head h;
   run_unit_tests(&h);
   return 0;
}

Running the unit tests generated the following output,

Contents (Forward):
Contents (Reverse):
Contents (Forward): 10 ->
Contents (Reverse): 10 ->
Contents (Forward): 10 -> 20 ->
Contents (Reverse): 20 -> 10 ->
Contents (Forward): 30 -> 10 -> 20 ->
Contents (Reverse): 20 -> 10 -> 30 ->
Contents (Forward): 30 -> 10 -> 20 -> 40 ->
Contents (Reverse): 40 -> 20 -> 10 -> 30 ->
Contents (Forward): 50 -> 30 -> 10 -> 20 -> 40 ->
Contents (Reverse): 40 -> 20 -> 10 -> 30 -> 50 ->
Contents (Forward): 50 -> 30 -> 10 -> 20 -> 40 -> 60 ->
Contents (Reverse): 60 -> 40 -> 20 -> 10 -> 30 -> 50 ->
Contents (Forward): 30 -> 10 -> 20 -> 40 -> 60 ->
Contents (Reverse): 60 -> 40 -> 20 -> 10 -> 30 ->
Contents (Forward): 30 -> 10 -> 20 -> 40 ->
Contents (Reverse): 40 -> 20 -> 10 -> 30 ->
Contents (Forward): 30 -> 20 -> 40 ->
Contents (Reverse): 40 -> 20 -> 30 ->

Thanks for reading. Please leave comments/suggestions if any.