5
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.