Example of a singly-linked list in C

This is an example C program demonstrating a singly-linked list containing arbitrary data.

This singly-linked list supports addition of elements to its end with linked_list_add, and traversing the list in order with linked_list_traverse. It is also able to free all the memory allocated with linked_list_free.

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

/* 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 * next;
};

/* linked_list_t contains a linked list. */

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

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


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

static void
linked_list_init (linked_list_t * list)
{
    list->first = list->last = 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". */

static void
linked_list_add (linked_list_t * list, 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) {
        list->last->next = link;
        list->last = link;
    }
    else {
        list->first = link;
        list->last = link;
    }
}

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

/* Go along the list and operate on the data of each element with
   "callback". */


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

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

/* Free the list's memory. */

static 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);
    }
}

/* Example callback function. */

static void
print_list (void * data)
{
    printf ("%s ", (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, "this");
    linked_list_add (& list, "is");
    linked_list_add (& list, "a");
    linked_list_add (& list, "linked");
    linked_list_add (& list, "list");
    linked_list_traverse (& list, print_list);
    printf ("\n");
    linked_list_free (& list);

    return 0;
}

(download)

The output of the example looks like this:

this is a linked list 

A singly linked list is useful for the case when one wants to create a list of things and add to the end of the list. It is possible to delete elements from a singly-linked list, but a doubly-linked list makes deletion simpler.

Thanks to Bill Martin for spotting an error on this page.