Linked deque implementation in C

Question

I wrote a deque implementation in C for storing char *. It uses a doubly linked list, but I'm calling it a deque since it can only push/pop from the head and tail of the list.

I don't have much experience writing C (I'm more of a Python guy) so please let me know what can be improved! I am already aware of the following:

• there are no comments (I've tried to use self-explanatory names)
• the testing isn't particularly rigorous

linkedlist.h

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H
#include <stdlib.h>

struct ll_node {
    struct ll_node *prev;
    struct ll_node *next;
    char           *data;
};

struct linkedlist {
    struct ll_node *head;
    struct ll_node *tail;
    size_t         length;
};

void ll_node_init(struct ll_node *node, char *data);
void ll_init(struct linkedlist *ll);
void ll_destroy(struct linkedlist *ll);
void ll_push_head(struct linkedlist *ll, char *data);
void ll_push_tail(struct linkedlist *ll, char *data);
char *ll_pop_head(struct linkedlist *ll);
char *ll_pop_tail(struct linkedlist *ll);

#endif

linkedlist.c

#include <stdlib.h>
#include "linkedlist.h"

void ll_node_init(struct ll_node *node, char *data) {
    node->prev = NULL;
    node->next = NULL;
    node->data = data;
}

void ll_init(struct linkedlist *ll) {
    ll->head = NULL;
    ll->tail = NULL;
    ll->length = 0;
}

void ll_destroy(struct linkedlist *ll) {
    struct ll_node *node = ll->head;
    struct ll_node *next;

    while(node != NULL) {
        next = node->next;
        free(node);
        node = next;
    }
}

void ll_push_head(struct linkedlist *ll, char *data) {
    struct ll_node *node = malloc(sizeof(struct ll_node));
    ll_node_init(node, data);

    if(ll->head != NULL) {
        ll->head->prev = node;
    }

    if(ll->tail == NULL) {
        ll->tail = node;
    }

    node->next = ll->head;
    ll->head = node;
    ll->length++;
}

void ll_push_tail(struct linkedlist *ll, char *data) {
    struct ll_node *node = malloc(sizeof(struct ll_node));
    ll_node_init(node, data);

    if(ll->tail != NULL) {
        ll->tail->next = node;
    }

    if(ll->head == NULL) {
        ll->head = node;
    }

    node->prev = ll->tail;
    ll->tail = node;
    ll->length++;
}

char *ll_pop_head(struct linkedlist *ll) {
    struct ll_node *node = ll->head;
    char *data;

    if(node == NULL) {
        return NULL;
    }

    if(node == ll->tail) {
        ll->tail = NULL;
    }

    ll->head = node->next;
    ll->length--;

    data = node->data;
    free(node);

    return data;
}

char *ll_pop_tail(struct linkedlist *ll) {
    struct ll_node *node = ll->tail;
    char *data;

    if(node == NULL) {
        return NULL;
    }

    if(node == ll->head) {
        ll->head = NULL;
    }

    ll->tail = node->prev;
    ll->length--;

    data = node->data;
    free(node);

    return data;
}

ll_test.c

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "linkedlist.h"

int main(int argc, char *argv[]) {
    struct linkedlist ll;
    char *data;
    ll_init(&ll);

    ll_push_head(&ll, "Alice");
    ll_push_tail(&ll, "Bob");
    ll_push_tail(&ll, "Charlotte");
    ll_push_head(&ll, "Daniel");
    assert(ll.length == 4);

    assert(strcmp(ll_pop_head(&ll), "Daniel") == 0);
    assert(strcmp(ll_pop_tail(&ll), "Charlotte") == 0);
    assert(strcmp(ll_pop_tail(&ll), "Bob") == 0);
    assert(strcmp(ll_pop_tail(&ll), "Alice") == 0);
    assert(ll.length == 0);

    ll_destroy(&ll);
    return 0;
}

Answer 1

Looks good. Few notes:

• There is no reason to #include <stdlib.h> in both linkedlist.h and linkedlist.c. Pick one (I recommend linkedlist.c).

• Allocation of a struct llnode instance definitely belongs to ll_node_init, and its signature should be

  static struct ll_node * ll_node_init(char * data);
  

  Notice static: there is no reason to expose struct ll_node to the client.

• Maintain your invariants. It is clear that if (ll_head != NULL) then ll_tail != NULL, and vice versa. For example, push_head should have

      if (ll->head != NULL) {
          assert(ll->tail != NULL);
          ll->head->prev = node;
      } else {
          assert(ll->tail == NULL);
          ll->tail = node;
      }
  

• The code doesn't really care what kind of data it queues. You may consider making the structure more generic with void * data.

Answer 2

Bug

When you pop the head node, you never set the new head node's prev pointer to NULL. Same with with popping the tail node: you never set the new tail node's next pointer to NULL.

This can cause a problem later on. Suppose you had the following two element list:

NULL <- A <-> B -> NULL

where head points to A and tail points to B. Now you pop the head node:

(A freed) <- B -> NULL

At this point, both head and tail point to B, but you never set its prev pointer to NULL so it is still pointing at the A node that was freed.

Now if you pop the tail node, your new tail node will be the freed A node, which is a problem.