Skip to main content

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.

Comments

Popular posts from this blog

BMI Calculator using Python and Tkinter

Body Mass Index can be calculated using a simple formula kg/m 2 , where the weight is represented in kilograms (kg) and the height is represented in metres (m). The article presents code to create a simple GUI to calculate BMI based on user input values. The GUI is implemented using tkinter and tkinter.ttk libraries in Python language.

Using hilite.me API in Python

hilite.me is a light weight website made by Alexander Kojevnikov , used to format source code from various programming languages into formatted HTML snippets which can be added to blogs, articles, and other web pages as needed. I personally use the API to format the source code snippets in this blog, and it has greatly reduced the time taken to complete an article, much thanks to the creator. In this article, an automated way of using the hilite.me API through Python and a simple HTML document is created with formatted code snippets.

Tic-tac-toe game using Python and tkinter

Tic-tac-toe is a popular two player game where each player tries to occupy an empty slot in a 3x3 board until one of them wins or the entire board is filled without any winner. The winner has to occupy three continuous cells in any direction, including the two diagonals. In this article, a version of the tic-tac-toe game is coded using Python and tkinter library.