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.