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 it here.

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.

Nicolas Chaufette found an error in the code.

Web links


Copyright © Ben Bullock 2009-2014. All rights reserved. For comments, questions, and corrections, please email Ben Bullock (benkasminbullock@gmail.com). / Privacy / Disclaimer