Doubly linked lists in C : With open source ADT.

This article describes the the doubly linked list data structure. I have written an open source ADT, and uploaded it to my github account, as well as an example application of how you can go about using it in your applications. I use void pointers in this code, which means you can actually write your application to deal with all kinds of data, and my ADT will support adding it to a doubly liked list.


To download the code and begin using it right away, here’s the github link :

Git hub link : https://www.github.com/LeamDelaney/Doubly_Linked_List
The build command for this is : gcc list.c test.c -o test
Which will compile a basic binary application, which uses my doubly linked list ADT.

Quick introduction to doubly linked lists

Doubly linked list do exactly what you might imagine. They are actually laid out similarly to a standard linked list, except that each element contains an extra pointer, pointing to the previous element is the list. In essence, a doubly linked list is made up up elements which each has a link to both the element before it, and the element after it. Each element will each also hold a piece of data.

This allows for a little bit of extra functionality which is not provided by the standard linked list, such as traversing backwards through the list, starting at tail, moving in the direction towards head. Being able to move in more than one direction allows us to think more logically about how we might choose to get to certain places within the list, one instant example of how a doubly linked list is improved by this, is the intuitive way in which we can remove an element.

Taking a look at what makes up a doubly linked list.

Similarly to standard linked lists, a doubly linked list requires two structures. Which we will look at right now.

The element structure

Without elements, you would have no list. Imagine writing a list of your favourite movie titles on a piece of paper. Each of the titles on that piece of paper is an element. In a doubly linked list, each of those elements would have a link between the one before it, and the one after it. Here’s we we code an element structure (You can find it in dlist.h on my github example)

Doubly linked list element

typedef struct DListElement_
{
    void *data; // Data in element.
    struct DListElement_ *prev; // Pointer to previous element.
    struct DListElement_ *next; // Pointer to next element.
}DListElement;

As you can see aboove, I have used a typedef in order to define my structure as a type, which I can create again and again throughout the lifetime of my program at run-time. Without having to write a lot of duplicated code. My type is called a “DListElement”. Which obviously stands for doubly linked list element. In the code you can clearly see the void pointer to the data we choose to store in the element. Also, please note the pointers to the DListElement structs, named next & previous, which will point to other instances just like this one, in a different point in the list and may have different data.

The doubly linked list structure

If we continue on with the thought process of imagining our list as a piece of paper with our favourite movie titles on it, then the list structure would be the paper. The data stored in this structure is actually quite minimal. As shown below :

/* Structure for the doubly linked list. */
typedef struct DList_
{
    int size; // Sise of the list at any given time.

    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);

    DListElement *head; // Pointer to element at HEAD.
    DListElement *tail; // Pointer to element at TAIL.
}DList;

The code above shows that the doubly linked list structure in this example is actually exactly the same as the one I gave you in the standard linked list. I can see you now, reading this, in disbelief, at how you can have a different kind of list, without even changing the list itself! That’s because the magic happens in that extra pointer we talked about in the element structure.

Great, but how do I use it?

Just like in the standard linked list article, I have provided you with an ADT which I have lovingly written, the header file, “dlist.h”, contains the interface which you can use. I have also commented it fully, so that you can understand how a doubly linked list works. The interface excerpt from that file is shown below :

Interface for the doubly linked list

/*********************************************************************
* INTERFACE FOR DOUBLY LINKED LIST
*********************************************************************/

/* Function : dlist_init
*
* Description : dlist_init, used to initialize the doubly linked list.
* The argument passed to it is a pointer to a DList struct.
* This function ***MUST*** be called on the list before the
* list can perform any other operation.
*
* Destroy??? The destroy argument is what we use to allow a developer
* to point to their own function which can be used to free
* up data that they have allocated within list elements.
* If your doubly linked list contains data that should not
* be freed when the list_destroy is called, pass NULL into
* this argument instead.
*/
void
dlist_init(DList *list, void (*destroy)(void *data));

/* Function : dlist_destroy
* Description : This function programatically destroys the list which
* is passed into it with a pointer. Once this operation has
* been performed on a list, no other operation should be
* carried out, unless dlist_init is used again. The function
* passed as destroy during the dlist_init will fire once for
* each element in the doubly linked list as it is removed.
* Assuming that the argument was not NULL.
*/
void
dlist_destroy(DList *list);

/* Function : dlist_insert_next
* Description : The dlist_insert_next function allows a developer to
* insert an element right after the position of the one as
* defined by "element" in the arguments. If this function is
* called to operate on an empty list, element could actually
* point to anywhere, but NULL should be used for the sake of
* good practice.
*
*/
int
dlist_insert_next(DList *list, DListElement *element, const void *data);

/* Function : dlist_insert_previous
* Description : The dlist_insert_prev function allows a developer to
* insert an element right pefore the position of the one as
* defined by "element" in the arguments.If this function is
* called to operate on an empty list, element could actually
* point to anywhere, but NULL should be used for the sake of
* good practice.
*/
int
dlist_insert_prev(DList *list, DListElement *element, const void *data);

/* Function : dlist_remove
* Description : The dlist_remove function removes the element which is
* passed as "element" from the doubly linked list passed as
* "list". When this function returns, data will point to the
* data which was stored in the element that was removed. It
* is the responsibility of the developer to manage the code
* here and clean up this memory.
*/
int
dlist_remove(DList* list, DListElement *element, void **data);

/* Function : dlist_size
* Description : the dlist_size function returns the value "size" which
* is stored inside "list"
*/
int
dlist_size(DList* list);

/* Function : dlist_is_head
 * Description : The dlist_is_head function returns an integer of 0 or
 * 0 or 1. A return value of '1' will confirm that "element" is at the
 * head position of "list", and 0 if it is not.
 */
int
dlist_is_head(DListElement *element);

/* Function : dlist_is_tail
 * Description : The dlist_is_tail function returns an integer of 
 * 0 or 1. A return value of '1' will confirm that "element" is at the
 * tail position of "list", and 0 if it is not.
 */
int
dlist_is_tail(DListElement *element);

/* Function : dlist_head
 * Description : The dlist_head function will return the element which
 * is at the head of "list".
 */
DListElement*
dlist_head(DList *list);

/* Function : dlist_tail
 * Description : The dlist_tail function will return the element which
 * is at the tail of "list".
 */
DListElement *
dlist_tail(DList *list);

/* Function : dlist_next
 * Description : The dlist_next function will return the element which
 * comes AFTER the element defined in the argument "element".
 */
DListElement*
dlist_next(DListElement *element);

/* Function : dlist_prev
 * Description : the dlist_prev function will return the element which
 * comes BEFORE the element defined in the argument "element".
 */
DListElement*
dlist_prev(DListElement *element);

/* Function : dlist_data
 * Description : The dlist_data function will return the pointer to  
 * the data which is stored inside an element within the doubly linked
 * list.
 */
void*
dlist_data(DListElement* element);

Oh, and one more thing, just like I intend doing with all code like this, here is the code listing of the example application I have added to the github :

#include "dlist.h"
#include <stdio.h>
/* Function prototypes */
void destroy(void *data);

int main(void)
{
    /* Setting up function pointers for the destroy, for later */
    void (*onDestroy)(void*);
    onDestroy = &destroy;

    printf("----------------------------------------------------\n");
    printf("---- Doubly Linked List Example Program ----\n");
    printf("----------------------------------------------------\n");

    /* Create a new doubly linked list */
    DList myList;

    /* Initialize the doubly linked list */
    dlist_init(&myList, onDestroy);

    /* Print the size of the linked list to screen
     * Remember, it will be '0' for now */
    printf("List size at beginning : %d\n", dlist_size(&myList));

    /* Adding an element to the list
     * When there are currently no elements, then the element will be
     * added as both head AND tail of the list. */

    /* As an example, my element will just contain a char* with the 
     * value "ElementOne". You can add anything, the data is actually 
     * a void pointer. */
    dlist_insert_next(&myList, NULL, "ElementOne");

    /* printing out the new size of the list, now that the new element
     * has been added to the list. */
    printf("List size after adding element : %d\n", 
           dlist_size(&myList));

    /* Get the head of the list */
    DListElement *tempElement = dlist_head(&myList);

    /* Adding a new element, after head. I am still using a simple 
     * char*, but you can use whatever you like. */
    dlist_insert_next(&myList, tempElement, "ElementTwo");

    /* Iterate forward in the list, and add a new element AFTER 
     * elementTwo */
    tempElement = dlist_next(tempElement);
    dlist_insert_next(&myList, tempElement, "ElementThree");

    tempElement = dlist_next(tempElement);

    /* Add an element BEFORE elementThree */

    dlist_insert_prev(&myList, 
                      tempElement, 
                      "ElementBetweenTwoAndThree");

    /* Printing all elements, iterating from head to tail (forwards) */
    printf("----------------------------------------------------\n");
    printf("----    Printing doubly linked list forwards    ----\n");
    printf("----------------------------------------------------\n");
    int i = 0;
    tempElement = dlist_head(&myList);

    for (i; i < dlist_size(&myList); i++)
    {
        printf("Data in element %d : %s\n", 
               i, 
               (char*)dlist_data(tempElement));

         tempElement = dlist_next(tempElement);
    }

    /* Printing all elements, iterating from head to tail (Backwards) */

    printf("----------------------------------------------------\n");
    printf("----   Printing doubly linked list backwards    ----\n");
    printf("----------------------------------------------------\n");
    i = dlist_size(&myList) - 1;
    tempElement = dlist_tail(&myList);

    for (i; i >= 0; i--)
    {
        printf("Data in element %d : %s\n", i, 
               (char*)dlist_data(tempElement));

        tempElement = dlist_prev(tempElement);
    }

    tempElement = dlist_head(&myList);
    tempElement = dlist_next(tempElement);
    tempElement = dlist_next(tempElement);

    dlist_remove(&myList, tempElement, &tempElement->data);

    printf("----------------------------------------------------\n");
    printf("----   Removed the BetweenTwoAndThree Element   ----\n");
    printf("----    Printing doubly linked list forwards    ----\n");
    printf("----------------------------------------------------\n");
    i = 0;
    tempElement = dlist_head(&myList);

    for (i; i < dlist_size(&myList); i++)
    {
        printf("Data in element %d : %s\n", i, 
               (char*)dlist_data(tempElement));

        tempElement = dlist_next(tempElement);
    }

    printf("List size : %d\n", dlist_size(&myList));

    /* Finished playing around now, Time to destroy the list */
    dlist_destroy(&myList);
    return 0;
}
void destroy(void *data)
{
    printf ("%s would be destroyed here, if you code that logic\n",
            (char*)data);
}

I had to edit some of the commands and format the code differently in this blog article in order to deal with web formatting. The code in the actual test.c file will be easier to read in places.

To build : gcc dlist.c test.c -o test

Thanks for reading.

Léam

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>