Deque in C

A deque or double-ended queue is a data structure that allows efficient addition and removal at either end. It may also support accessing elements by index, as this implementation does.

This deque is implemented as a dynamic array of fixed-size arrays. The first array is filled from right to left, and the last one from left to right, as shown in the following diagram:

Diagram showing the deque implementation

When an array at either end becomes full, a new one is added, and when one is emptied, it is removed.

Here is the header file:

#ifndef DEQUE_H
#define DEQUE_H

#include <dynarray.h>

typedef struct {
	dynarray *arrays;
	unsigned int arraysize;
	unsigned int front;
	unsigned int back;
	unsigned int firstempty;
	unsigned int lastempty;
	unsigned int count;
} deque;

typedef void (*deque_forfn)(void*);

deque * deque_create(void);
void deque_delete(deque * queue);
void deque_push_front(deque * queue, void * data);
void deque_push_back(deque * queue, void * data);
void * deque_pop_front(deque * queue);
void * deque_pop_back(deque * queue);
void * deque_get_at(const deque *queue, unsigned int index);
void * deque_set_at(deque *queue, unsigned int index, void * data);
void * deque_peek_front(const deque * queue);
void * deque_peek_back(const deque * queue);
void deque_for_each(const deque * queue, deque_forfn fun);

#endif /* DEQUE_H */

The implementation:

#include <stdlib.h>

#include <deque.h>

deque * deque_create(void)
{
	deque *queue = malloc(sizeof(deque));
	if (queue) {
		queue->arrays = dynarray_create(0);
		queue->arraysize = 4;
		queue->firstempty = 1;
		queue->lastempty = 1;
		queue->count = 0;
		dynarray_add_head(queue->arrays, malloc(queue->arraysize * sizeof(void*)));
	}
	return queue;
}

void deque_delete(deque * queue)
{
	if (queue) {
		dynarray_for_each(queue->arrays, free);
		dynarray_delete(queue->arrays);
		free(queue);
	}
}

void deque_push_front(deque * queue, void * data)
{
	unsigned int index;
	if (queue->count == 0) {
		/* Adding the first element */
		index = queue->arraysize / 2;
	}
	else if (queue->firstempty) {
		/* There is an empty array at the beginning */
		index = queue->arraysize - 1;
	}
	else if (queue->front == 0) {
		/* Beginning array is full - add another */
		dynarray_add_head(queue->arrays, malloc(queue->arraysize * sizeof(void*)));
		index = queue->arraysize - 1;
	}
	else {
		index = queue->front - 1;
	}
	((void**)dynarray_get(queue->arrays, 0))[index] = data;
	queue->front = index;
	queue->firstempty = 0;
	if (queue->arrays->count == 1) {
		queue->lastempty = 0;
	}
	queue->count++;
	if (queue->count == 1) {
		queue->back = queue->front;
	}
}

void deque_push_back(deque * queue, void * data)
{
	unsigned int index;
	if (queue->count == 0) {
		/* Adding the first element */
		index = queue->arraysize / 2;
	}
	else if (queue->lastempty) {
		/* There is an empty array at the end */
		index = 0;
	}
	else if (queue->back == queue->arraysize - 1) {
		/* End array is full - add another */
		dynarray_add_tail(queue->arrays, malloc(queue->arraysize * sizeof(void*)));
		index = 0;
	}
	else {
		index = queue->back + 1;
	}
	((void**)dynarray_get(queue->arrays, queue->arrays->count - 1))[index] = data;
	queue->back = index;
	queue->lastempty = 0;
	if (queue->arrays->count == 1) {
		queue->firstempty = 0;
	}
	queue->count++;
	if (queue->count == 1) {
		queue->front = queue->back;
	}
}

void * deque_pop_front(deque * queue)
{
	void *data = NULL;
	if (queue->count) {
		if (queue->firstempty) {
			/* There is an empty array at the beginning */
			free(dynarray_remove_head(queue->arrays));
			queue->firstempty = 0;
		}
		data = ((void**)dynarray_get(queue->arrays, 0))[queue->front];
		queue->front++;
		if (queue->front == queue->arraysize) {
			/* First array is now empty */
			queue->firstempty = 1;
			queue->front = 0;
		}
		queue->count--;
		if (queue->count == 1) {
			queue->back = queue->front;
		}
		else if (queue->count == 0 && queue->arrays->count == 2) {
			/* Both arrays are empty - remove either one */
			free(dynarray_remove_head(queue->arrays));
		}
	}
	return data;
}

void * deque_pop_back(deque * queue)
{
	void *data = NULL;
	if (queue->count) {
		if (queue->lastempty) {
			/* There is an empty array at the end */
			free(dynarray_remove_tail(queue->arrays));
			queue->lastempty = 0;
		}
		data = ((void**)dynarray_get(queue->arrays, queue->arrays->count - 1))[queue->back];
		if (queue->back == 0) {
			/* Last array is now empty */
			queue->lastempty = 1;
			queue->back = queue->arraysize - 1;
		}
		else {
			queue->back--;
		}
		queue->count--;
		if (queue->count == 1) {
			queue->front = queue->back;
		}
		else if (queue->count == 0 && queue->arrays->count == 2) {
			/* Both arrays are empty - remove either one */
			free(dynarray_remove_tail(queue->arrays));
		}
	}
	return data;
}

void * deque_get_at(const deque *queue, unsigned int index)
{
	void * data = NULL;
	if (index < queue->count) {
		const unsigned int pos = index + queue->front;
		data = ((void**)dynarray_get(queue->arrays, 
			pos / queue->arraysize + queue->firstempty))[pos % queue->arraysize];
	}
	return data;
}

void * deque_set_at(deque *queue, unsigned int index, void * data)
{
	void * result = NULL;
	if (index == queue->count) {
		deque_push_back(queue, data);
	}
	else if (index < queue->count) {
		const unsigned int pos = index + queue->front;
		result = deque_get_at(queue, index);
		((void**)dynarray_get(queue->arrays, 
			pos / queue->arraysize + queue->firstempty))[pos % queue->arraysize] = data;
	}
	return result;
}

void * deque_peek_front(const deque * queue)
{
	void *data = NULL;
	if (queue->count > 0) {
		data = ((void**)dynarray_get(queue->arrays, queue->firstempty))[queue->front];
	}
	return data;
}

void * deque_peek_back(const deque * queue)
{
	void *data = NULL;
	if (queue->count > 0) {
		data = ((void**)dynarray_get(queue->arrays, 
					dynarray_get_count(queue->arrays) - 1 - queue->lastempty))[queue->back];
	}
	return data;
}

void deque_for_each(const deque * queue, deque_forfn fun)
{
	unsigned int i;
	for (i = 0; i < queue->count; i++) {
		fun(deque_get_at(queue, i));
	}
}

Sorting a linked list by turning it into a binary search tree

Introduction

A doubly-linked list node has two pointers, previous and next, and a binary tree node also has two pointers, left and right

This means that one way of sorting a linked list is to turn it into a binary tree and then back into a list again.

Turning the list into a binary tree

Turning the list into a tree is just a question of iterating over the list and performing the normal binary tree insertion algorithm. We need to remember to save the current node’s next pointer before we insert it, as it will not be available afterwards.

typedef int(*cmpfn)(const void*, const void*);

listnode * linkedlist_to_tree(linkedlist * list, cmpfn compare)
{
    listnode * root = list->head;
    if (root) {
        listnode * node = root->next;
        root->previous = NULL;
        root->next = NULL;
        while (node != NULL) {
            listnode * next = node->next;
            listnode * current = root, * previous = NULL;
            int result;
            while (current != NULL) {
                previous = current;
                result = compare(current->data, node->data);
                if (result > 0) {
                    current = current->previous;
                }
                else {
                    current = current->next;
                }
            }
            if (result > 0) {
                previous->previous = node;
            }
            else {
                previous->next = node;
            }
            node->previous = NULL;
            node->next = NULL;
            node = next;
        }
    }
    return root;
}

Turning the binary tree back into a list

This involves an inorder traversal of the tree, which is most easily implemented using recursion. We need to look out for the first and last elements; they need to be treated specially as they are the head and tail of the list.

The first element in a binary tree is the one that we encounter the first time we can go left no further. We find the last element by keeping track of the number of elements encountered so far, and comparing it to the number in the list.

void linkedlist_from_tree(linkedlist * list, listnode * root,
        listnode ** previous, unsigned int * count)
{
    if (root) {
        listnode * left = root->previous;
        listnode * right = root->next;
        linkedlist_from_tree(list, left, previous, count);
        if (root->previous == NULL && list->head == NULL) {
            /* We're at the first element */
            list->head = root;
            list->head->previous = NULL;
        }
        else {
            (*previous)->next = root;
            root->previous = *previous;
        }
        if (*count == linkedlist_get_count(list) - 1) {
            /* We're at the last element */
            list->tail = root;
            list->tail->next = NULL;
        }
        *previous = root;
        (*count)++;
        linkedlist_from_tree(list, right, previous, count);
    }
}

The sort function

Our linked list sort function now just needs to combine the two operations:

void linkedlist_sort(linkedlist * list, cmpfn compare)
{
    unsigned int count = 0;
    listnode * previous;
    listnode * tree = linkedlist_to_tree(list, compare);
    list->head = NULL;
    list->tail = NULL;
    linkedlist_from_tree(list, tree, &previous, &count);
}

Example program

int main(void)
{
    char * elements[] = {"D", "B", "D", "F", "A", "C", "E"};
    const unsigned int n = sizeof(elements) / sizeof(const char *);
    linkedlist * list;
    unsigned int i;

    list = linkedlist_create();
    for (i = 0; i < n; i++) {
        linkedlist_add_tail(list, elements[i]);
    }
    linkedlist_sort(list, (cmpfn)strcmp);
    linkedlist_for_each(list, (forfn)puts);
    linkedlist_delete(list);

    return 0;
}