linked_list.c

/**
 * A linked list implementation.
 * 
 * Iteration is done by deferencing the head (or tail) of the list.
 * Insertions at the front or back of the list will be O(1) (which
 * is the only insertion operation supported), iteration is O(n),
 * and removal is O(n) (unless the node being removed is the head or
 * tail, which is O(1)).
 * 
 * This implementation is a doubly-linked list. It is not thread safe.
 */

#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct node {
    int val;
    struct node *prev;
    struct node *next;
} gr_linked_list_node;

typedef struct {
    size_t size;
    gr_linked_list_node *head;
    gr_linked_list_node *tail;
} gr_linked_list;

gr_linked_list_node* _linked_list_create_node(int val) {
    void *node_ptr = malloc(sizeof(gr_linked_list_node));
    if (node_ptr == NULL) {
        return NULL;
    }

    gr_linked_list_node *node = (gr_linked_list_node *)node_ptr;
    node->val = val;
    return node;
}

int linked_list_insert_head(gr_linked_list *list, int val) {
    gr_linked_list_node *node = _linked_list_create_node(val);
    if (node == NULL) {
        // TODO: Better return here
        return EXIT_FAILURE;
    }

    if (list->head != NULL) {
        // update the node
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    } else if (list->head == NULL && list->tail == NULL) {
        // list is empty, as far as we know
        list->head = list->tail = node;
        node->prev = NULL;
        node->next = NULL;
    }

    list->size++;
    return EXIT_SUCCESS;
}

int linked_list_insert_tail(gr_linked_list *list, int val) {
    gr_linked_list_node *node = _linked_list_create_node(val);
    if (node == NULL) {
        // TODO: Better return here
        return EXIT_FAILURE;
    }

    if (list->tail != NULL) {
        // update the node
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    } else if (list->head == NULL && list->tail == NULL) {
        // list is empty, as far as we know
        list->head = list->tail = node;
        node->prev = NULL;
        node->next = NULL;
    }

    list->size++;
    return EXIT_SUCCESS;
}

void linked_list_reverse(gr_linked_list *list) {
    // iterate backwards
    gr_linked_list_node *old_tail = list->tail;
    gr_linked_list_node *last_processed = NULL;
    gr_linked_list_node *next_node = list->tail;

    while (next_node != NULL) {
        // swap prev and next
        gr_linked_list_node *old_next = next_node->next;
        next_node->next = next_node->prev;
        next_node->prev = old_next;
        last_processed = next_node;
        next_node = next_node->next;
    }

    // now set the new head/tail
    list->tail = last_processed;
    list->head = old_tail;
}

void _linked_list_removal_fixup(gr_linked_list *list, gr_linked_list_node *node) {
    // fix up the pointers in the list itself
    if (node == list->head) {
        list->head = node->next;
    }
    if (node == list->tail) {
        list->tail = node->prev;
    }

    // now fix up other pointers
    if (node->next != NULL) {
        node->next->prev = node->prev;
    }
    if (node->prev != NULL) {
        node->prev->next = node->next;
    }

    // free the node and decrement the list size
    free(node);
    list->size--;
}

bool linked_list_remove_first(gr_linked_list *list, int val) {
    gr_linked_list_node *node = list->head;

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

    if (node == NULL) {
        // no element found
        return false;
    }

    _linked_list_removal_fixup(list, node);
    return true;
}

bool linked_list_remove_last(gr_linked_list *list, int val) {
    gr_linked_list_node *node = list->tail;

    while (node != NULL && node->val != val) {
        node = node->prev;
    }

    if (node == NULL) {
        // no element found
        return false;
    }

    _linked_list_removal_fixup(list, node);
    return true;
}

gr_linked_list* new_linked_list() {
    void *linked_list = malloc(sizeof(gr_linked_list));
    if (linked_list == NULL) {
        // memory allocation failed
        return NULL;
    }
    memset(linked_list, 0, sizeof(gr_linked_list));
    return (gr_linked_list*) linked_list;
}

void walk(gr_linked_list *list) {
    gr_linked_list_node *current = list->head;
    while (current != NULL) {
        printf("%d\n", current->val);
        current = current->next;
    }
}

int main(int argc, char **argv) {
    gr_linked_list* list = new_linked_list();
    assert(list != NULL);

    assert(linked_list_insert_head(list, 42) == EXIT_SUCCESS);
    assert(linked_list_insert_head(list, 666) == EXIT_SUCCESS);
    assert(linked_list_insert_tail(list, 13) == EXIT_SUCCESS);
    assert(linked_list_insert_tail(list, 17) == EXIT_SUCCESS);

    printf("moving from head to tail\n");
    walk(list);

    printf("reversing that shit\n");
    walk(list);

    printf("doing crazy shit\n");
    assert(linked_list_remove_first(list, 42));
    assert(linked_list_remove_last(list, 17));
    assert(!linked_list_remove_last(list, 17));
    walk(list);
}