Doubly Linked List C implementation

Question

I'm a C beginner. I'm studying and implementing some data structures. I'd like to get feedback about my style and decisions I made.

This is a Doubly Linked List. I decided to keep things as simple as possible writing just the basic operations for the list.

In main there is some test code along with a print function written just for testing purpose.

All the code is in one file because I'd like to store all these implementations in single files (as snippets) for future reference, this is also the reason why not all the #includes are at the top: only those strictly necessary for the implementation are at the beginning.

/*
 * Doubly Linked List C implementation.
 *
 * Conceptually similar to a Singly Linked List. In this case, for each element
 * (node) we have a data stored, a link to the next node and a link to the
 * previous node.
 * The link to the previous node of "head" will be NULL;
 * the link to the next node of "tail" will be NULL.
 *
 * It is useful to store not only the head of the list but also the tail so that
 * for example, we can traverse backwards pretty easy.
 *
 * ------     ------
 * |NULL|<----|--  |
 * ------     ------     ------
 *            | 17 |<----|--  |
 *            ------     ------     ------
 *            |  --|---->|  3 |<----|--  |
 *            ------     ------     ------     ------
 *             ^         |  --|---->| 22 |<----|--  |
 *            HEAD       ------     ------     ------
 *                                  |  --|---->| 11 |
 *                                  ------     ------     ------
 *                                             |  --|---->|NULL|
 *                                             ------     ------
 *                                              ^
 *                                             TAIL
 *
 * Search: O(n): search operations are performed in linear time.
 * Insert: O(1): since all new nodes will replace the head or the tail.
 * Delete: O(n): since we are deleting the first occurrence of a specific data.
 */


#include <stdlib.h>
#include <stdbool.h>

typedef struct node
{
        int data;
        struct node *prev;
        struct node *next;
} node;

typedef struct
{
        node *head;
        node *tail;
        unsigned int size;
} dllist;


/*
 * create_list:  returns a pointer to a new empty list or NULL if the process
 *               failed.
 */
dllist *create_list(void)
{
        dllist *new_list = malloc(sizeof(*new_list));

        if (new_list != NULL) {
                new_list->head = NULL;
                new_list->tail = NULL;
                new_list->size = 0;
        }
        return new_list;
}

/*
 * create_node:  returns a pointer to a new node (storing data) with the
 *               previous and next pointers set to NULL. If the process failed,
 *               returns NULL.
 */
node *create_node(int data)
{
        node *new_node = malloc(sizeof(*new_node));

        if (new_node != NULL) {
                new_node->data = data;
                new_node->prev = NULL;
                new_node->next = NULL;
        }
        return new_node;
}

/*
 * is_empty:  returns true if list is an empty list, false otherwise.
 */
bool is_empty(dllist *list)
{
        return list->head == NULL && list->tail == NULL && list->size == 0;
}

/*
 * insert_beginning:  inserts a new node in the list list at the beginning
 *                    replacing the head.
 *                    Returns true on success, false on failure.
 */
bool insert_beginning(dllist *list, int data)
{
        node *new_node = create_node(data);

        if (new_node != NULL) {

                if (is_empty(list)) {
                        list->head = list->tail = new_node;
                } else {
                        list->head->prev = new_node;
                        new_node->next = list->head;
                        list->head = new_node;
                }
                list->size += 1;
                return true;
        }
        return false;
}

/*
 * insert_end:  inserts a new node in the list list at the end replacing the
 *              tail.
 *              Returns true on success, false on failure.
 */
bool insert_end(dllist *list, int data)
{
        node *new_node = create_node(data);

        if (new_node != NULL) {

                if (is_empty(list)) {
                        list->head = list->tail = new_node;
                } else {
                        list->tail->next = new_node;
                        new_node->prev = list->tail;
                        list->tail = new_node;
                }
                list->size += 1;
                return true;
        }
        return false;
}

/*
 * find_node:  returns a pointer to the first occurrence of data (i.e to the
 *             first node storing data) in the list starting from the beginning,
 *             NULL if there is no node storing data.
 */
node *find_node(dllist *list, int data)
{
        node *current = list->head;

        while (current != NULL) {

                if (current->data == data) {
                        return current;
                }
                current = current->next;
        }
        return NULL;
}

/*
 * delete_node:  deletes the node node from the list list.
 */
void delete_node(dllist *list, node* node)
{
        if (node->next != NULL) {
                node->next->prev = node->prev;
        } else {
                list->tail = node->prev;
        }
        if (node->prev != NULL) {
                node->prev->next = node->next;
        } else {
                list->head = node->next;
        }
        list->size -= 1;
        free(node);
}

/*
 * delete_data:  deletes the first occurrence of data (i.e the first node
 *               storing data) in the list list starting from the beginning.
 *               Returns true if a node was deleted, false otherwise.
 */
bool delete_data(dllist *list, int data)
{
        node *to_delete = find_node(list, data);

        if (to_delete != NULL) {
                delete_node(list, to_delete);
                return true;
        }
        return false;
}

/*
 * clear_list:  delete all nodes in the list list.
 */
void clear_list(dllist *list)
{
        node *current = list->head;
        node *next;

        while (current != NULL) {
                next = current->next;
                delete_node(list, current);
                current = next;
        }
}

/*
 * free_list:  delete all nodes and the "instance" of the list list, then sets
 *             *list to NULL.
 */
void free_list(dllist **list)
{
        clear_list(*list);
        free(*list);
        *list = NULL;
}


#include <stdio.h>
#include <time.h>

void print_list(dllist *list);


int main(void)
{
        int i, to_find, random_nums[10];
        srand(time(NULL));

        dllist *l = create_list();

        puts("Inserting 0-10 from beginning...");
        for (i = 0; i < 10; i++) {
                insert_beginning(l, i);
        }
        print_list(l);

        puts("Deleting all elements...");
        clear_list(l);
        print_list(l);

        puts("Inserting 0-10 from end...");
        for (i = 0; i < 10; i++) {
                insert_end(l, i);
        }
        print_list(l);

        puts("Deleting all elements and inserting 10 random numbers...");
        clear_list(l);
        for (i = 0; i < 10; i++) {
                random_nums[i] = rand() % 100;
                insert_end(l, random_nums[i]);
        }
        print_list(l);

        for (i = 0; i < 5; i++) {

                to_find = (rand() % 2 == 0) ? rand() % 100 : random_nums[i];

                printf("Looking for %2i: %2i is ", to_find, to_find);
                if (find_node(l, to_find) != NULL) {
                        puts("in the list");
                } else {
                        puts("not in the list");
                }
        }
        puts("\nDeleting the head...");
        delete_node(l, l->head);
        print_list(l);

        puts("Deleting the tail...");
        delete_node(l, l->tail);
        print_list(l);

        puts("Deleting odd numbers...");
        for (i = 0; i < 10; i++) {
                if (random_nums[i] % 2 != 0) {
                        delete_data(l, random_nums[i]);
                }
        }
        print_list(l);

        puts("freeing the list...");
        free_list(&l);
}

void print_list(dllist *list)
{
        fputs("List: ", stdout);

        if (is_empty(list)) {
                fputs("is empty", stdout);
        } else {
                printf("size: %u elements: ", list->size);

                node *current = list->head;
                while (current != NULL) {
                        printf(" %i ", current->data);
                        current = current->next;
                }
        }
        puts("\n");
}

Answer 1

• is_empty tests too much. The conditions you test must either all be true or all be false, otherwise the list is corrupted. Pick one (and assert the remaining).

• insert_beginning

  The new_node's next shall point the head no matter what. Equally, the head must become new_node no matter what. Better make it explicit:

      new_node->next = list->head;
      if (list->head == 0) {
          list_tail = new_node;
      } else {
          list->head->prev = new_node;
      }
      list->head = new_node;
  

  The same applies to insert_end.

  PS: canonical names are prepend and append.

• new_node and delete_node better be static. The client should have no interest in managing nodes.

• Fail early. The

     if (failure_condition) {
         return false;
     }
     do_regular_stuff;
     return true;
  

  removes a level of indentation, and is much easier to follow.

Answer 2

I hereby declare you not a beginner anymore.

Your code is simple to understand, quite efficient and correct. The names you chose are nicely short and to the point. The functions are cut into the correct pieces.

There are only some nitpicks left:

• You say "numbers from 0-10", but really they are only from 0-9.
• The random numbers are not distributed evenly. Smaller numbers are picked a little more often than later numbers. Search for "c rand evenly int" to find out more.
• The output from print_list should not have a trailing space. The list elements are usually separated by a single space (currently 2).
• You already have a test program, but its output has to be inspected manually to see whether your code works. You should write tests that fail automatically when something unexpected happens. See the assert macro for more information on that topic.

All in all, very nice work.

Answer 3

I haven't had enough time to read through your code thoroughly, so I'm just pointing one thing out for right now.

For is_empty, I would assert that list->size == 0 instead of making multiple checks because when you add or take away from the list, you also change the size of the list.

Answer 4

Extra work in clear_list()

Currently, your clear_list() function calls delete_node() to delete each element of the list. This requires extra work to be done, because delete_node() does some checks to keep the head/tail/size correct on each deletion. Since you are going to delete the entire list, you can just call free() instead of delete_node(), and set head/tail/size once at the end, like this:

void clear_list(dllist *list)
{
        node *current = list->head;
        node *next;

        while (current != NULL) {
                next = current->next;
                free(current);
                current = next;
        }
        list->head = NULL;
        list->tail = NULL;
        list->size = 0;
}

A comment on your comment

One of your comments says this:

// Delete: O(n): since we are deleting the first occurrence of a specific data.

It's true that deleting a specific value takes \$O(n)\$ time. However, most of the time when I'm working with a doubly-linked list, I will already be holding a pointer to the node I want to delete. Deleting a node only requires \$O(1)\$ time. This is one of the big advantages of using a doubly-linked list as opposed to using a singly-linked list.

Use of const

Any function that doesn't need to change the list argument such as is_empty(), find_node(), and print_list(), could change their argument type from plain dllist * to const dllist *. The const keyword is useful in two ways: 1) to enforce at compile time that the argument is unmodifiable and 2) to let the reader of the code know at a glance that the argument is unmodified.