Example of a doubly-linked list in C

This is an example C program for a doubly-linked list. It illustrates traversing the list in either order and deleting elements from the list. To run the example program, compile it with DLLTEST defined:

cc -DDLLTEST dll.c

#include <stdlib.h>
#include <stdio.h>
#ifdef DLLTEST
/* strchr, declared in string.h, is used in the examples. */
#include <string.h>
#define HEADER
#else
#include "dll.h"
#endif 
#ifdef HEADER

/* The type link_t needs to be forward-declared in order that a
   self-reference can be made in "struct link" below. */

typedef struct link link_t;

/*  _ _       _    
   | (_)_ __ | | __
   | | | '_ \| |/ /
   | | | | | |   < 
   |_|_|_| |_|_|\_\ */
                

/* A link_t contains one of the links of the linked list. */

struct link {
    const void * data;
    link_t * prev;
    link_t * next;
};

/*  _ _       _            _     _ _     _   
   | (_)_ __ | | _____  __| |   | (_)___| |_ 
   | | | '_ \| |/ / _ \/ _` |   | | / __| __|
   | | | | | |   <  __/ (_| |   | | \__ \ |_ 
   |_|_|_| |_|_|\_\___|\__,_|___|_|_|___/\__|
                           |_____|            */


/* linked_list_t contains a linked list. */

typedef struct linked_list
{
    int count;
    link_t * first;
    link_t * last;
}
linked_list_t;

#endif /* def HEADER */

/* The following function initializes the linked list by putting zeros
   into the pointers containing the first and last links of the linked
   list. */

void
linked_list_init (linked_list_t * list)
{
    list->first = list->last = 0;
    list->count = 0;
}

/*            _     _ 
     __ _  __| | __| |
    / _` |/ _` |/ _` |
   | (_| | (_| | (_| |
    \__,_|\__,_|\__,_| */
                   

/* The following function adds a new link to the end of the linked
   list. It allocates memory for it. The contents of the link are
   copied from "data". */

void
linked_list_add (linked_list_t * list, const void * data)
{
    link_t * link;

    /* calloc sets the "next" field to zero. */
    link = calloc (1, sizeof (link_t));
    if (! link) {
        fprintf (stderr, "calloc failed.\n");
        exit (EXIT_FAILURE);
    }
    link->data = data;
    if (list->last) {
        /* Join the two final links together. */
        list->last->next = link;
        link->prev = list->last;
        list->last = link;
    }
    else {
        list->first = link;
        list->last = link;
    }
    list->count++;
}

/*      _      _      _       
     __| | ___| | ___| |_ ___ 
    / _` |/ _ \ |/ _ \ __/ _ \
   | (_| |  __/ |  __/ ||  __/
    \__,_|\___|_|\___|\__\___| */
                           


void
linked_list_delete (linked_list_t * list, link_t * link)
{
    link_t * prev;
    link_t * next;

    prev = link->prev;
    next = link->next;
    if (prev) {
        if (next) {
            /* Both the previous and next links are valid, so just
               bypass "link" without altering "list" at all. */
            prev->next = next;
            next->prev = prev;
        }
        else {
            /* Only the previous link is valid, so "prev" is now the
               last link in "list". */
            prev->next = 0;
            list->last = prev;
        }
    }
    else {
        if (next) {
            /* Only the next link is valid, not the previous one, so
               "next" is now the first link in "list". */
            next->prev = 0;
            list->first = next;
        }
        else {
            /* Neither previous nor next links are valid, so the list
               is now empty. */
            list->first = 0;
            list->last = 0;
        }
    }
    free (link);
    list->count--;
}

/*  _                                     
   | |_ _ __ __ ___   _____ _ __ ___  ___ 
   | __| '__/ _` \ \ / / _ \ '__/ __|/ _ \
   | |_| | | (_| |\ V /  __/ |  \__ \  __/
    \__|_|  \__,_| \_/ \___|_|  |___/\___| */
                                       


void
linked_list_traverse (linked_list_t * list, void * data,
                      void (*callback) (void *, void *))
{
    link_t * link;

    for (link = list->first; link; link = link->next) {
        callback (data, (void *) link->data);
    }
}

                                  
/*  _ __ _____   _____ _ __ ___  ___ 
   | '__/ _ \ \ / / _ \ '__/ __|/ _ \
   | | |  __/\ V /  __/ |  \__ \  __/
   |_|  \___| \_/ \___|_|  |___/\___| */
                                  


void
linked_list_traverse_in_reverse (linked_list_t * list, void * data,
                                 void (*callback) (void *, void *))
{
    link_t * link;

    for (link = list->last; link; link = link->prev) {
        callback (data, (void *) link->data);
    }
}

/*  _                                     
   | |_ _ __ __ ___   _____ _ __ ___  ___ 
   | __| '__/ _` \ \ / / _ \ '__/ __|/ _ \
   | |_| | | (_| |\ V /  __/ |  \__ \  __/
    \__|_|  \__,_| \_/ \___|_|  |___/\___|
                                          
     ___         _      _      _       
    ( _ )     __| | ___| | ___| |_ ___ 
    / _ \/\  / _` |/ _ \ |/ _ \ __/ _ \
   | (_>  < | (_| |  __/ |  __/ ||  __/
    \___/\/  \__,_|\___|_|\___|\__\___| */
                                    


void
linked_list_traverse_delete (linked_list_t * list, int (*callback) (void *))
{
    link_t * link;
    link_t * next;

    for (link = list->first; link; link = next) {
	next = link->next;
        if (callback ((void *) link->data)) {
            linked_list_delete (list, link);
        }
    }
}

/*   __               
    / _|_ __ ___  ___ 
   | |_| '__/ _ \/ _ \
   |  _| | |  __/  __/
   |_| |_|  \___|\___| */
                   


/* Free the list's memory. */

void
linked_list_free (linked_list_t * list)
{
    link_t * link;
    link_t * next;
    for (link = list->first; link; link = next) {
        /* Store the next value so that we don't access freed
           memory. */
        next = link->next;
        free (link);
    }
}

#ifdef DLLTEST

/* Example traverse delete function - delete everything. */

static int
delete_all (void * data)
{
    return 1;
}

/* Example traverse delete function - delete things with an "a" in
   them. */

static int
delete_a (void * data)
{
    return (int) strchr ((char *) data, 'a');
}

/* Example callback function. */

static void
print_list (void * user_data, void * data)
{
    printf ("\t%s\n", (char *) data);
}

/* Make a list of words and then print them out. */

int main ()
{
    linked_list_t list;

    linked_list_init (& list);
    linked_list_add (& list, "dingo");
    linked_list_add (& list, "kangaroo");
    linked_list_add (& list, "koala");
    linked_list_add (& list, "kookaburra");
    linked_list_add (& list, "tasmanian devil");
    linked_list_add (& list, "wallabee");
    linked_list_add (& list, "wallaroo");
    linked_list_add (& list, "wombat");
    printf ("Australian animals, in reverse alphabetical order:\n");
    linked_list_traverse_in_reverse (& list, 0, print_list);
    printf ("\n");
    linked_list_traverse_delete (& list, delete_a);
    printf ("These Australian animals don't have an 'a' in their names:\n");
    linked_list_traverse (& list, 0, print_list);
    printf ("\n");
    linked_list_traverse_delete (& list, delete_all);
    printf ("All the Australian animals are now extinct:\n");
    linked_list_traverse (& list, 0, print_list);
    printf ("\n");
    linked_list_free (& list);

    return 0;
}

#endif /* def DLLTEST */

(download)

The output of the example looks like this:

Australian animals, in reverse alphabetical order:
	wombat
	wallaroo
	wallabee
	tasmanian devil
	kookaburra
	koala
	kangaroo
	dingo

These Australian animals don't have an 'a' in their names:
	dingo

All the Australian animals are now extinct:

Doubly-linked lists are similar to singly-linked lists but they also make it easy to traverse the list in either direction. They also make it easier to delete elements from the list.

Acknowledgements: Nicolas Chaufette found an error in the code.

Web links

• Support Australian Wildlife Conservancy

  To help prevent real Australian animals from becoming extinct, support the Australian Wildlife Conservancy.