Related Books
Books / Introduction to C Programming Language / Chapter 26
Deques and doubly-linked lists
Suppose we want a data structure that represents a line of elements where we can push or pop elements at either end. Such a data structure is known as a deque (pronounced like “deck”), and can be implemented with all operations taking O(1) time by a doubly-linked list, where each element has a pointer to both its successor and its predecessor.
An ordinary singly-linked list is not good enough. The reason is that even if we keep a pointer to both ends as in a queue, when it comes time to pop an element off the tail, we have no pointer to its predecessor ready to hand; the best we can do is scan from the head until we get to an element whose successor is the tail, which takes O(n) time.
So instead we need a doubly-linked list, where each node points to both its successor and predecessor. The most straightforward way to build this is to make it circular, and use an extra node whose value isn’t used to represent the head of the list. The resulting data structure might look something like this:
Below is an implementation of this structure. We have separated the interface in deque.h from the implementation in deque.c. This will allow us to change the implementation if we decide we don’t like it, without affecting any other code in the system.
A nice feature of this data structure is that we don’t need to use null pointers to mark the ends of the deque. Instead, each end is marked by a pointer to the extra head element. For an empty deque, this just means that the head points to itself. The cost of this is that to detect an empty deque we have to test for equality with the head (which might be slightly more expensive that just testing for null) and the head may contain some wasted space for its missing value if we allocate it like any other element.
To keep things symmetric, we implement the pointers as an array, indexed by the directions DEQUE_FRONT and DEQUE_BACK (defined in deque.h). This means we can use the same code to push or pop on either end of the deque.
typedef struct deque Deque;
#define DEQUE_FRONT (0)
#define DEQUE_BACK (1)
#define DEQUE_EMPTY (-1) /* returned by dequePop if deque is empty */
/* return a new empty deque */
Deque *dequeCreate(void);
/* push new value onto direction side of deque d */
void dequePush(Deque *d, int direction, int value);
/* pop and return first value on direction side of deque d */
/* returns DEQUE_EMPTY if deque is empty */
int dequePop(Deque *d, int direction);
/* return 1 if deque contains no elements, 0 otherwise */
int dequeIsEmpty(const Deque *d);
/* free space used by a deque */
void dequeDestroy(Deque *d);
examples/linkedLists/deque/deque.h
#include <stdlib.h>
#include <assert.h>
#include <stddef.h> /* for offsetof */
#include "deque.h"
#define NUM_DIRECTIONS (2)
struct deque {
struct deque *next[NUM_DIRECTIONS];
int value;
};
Deque *
dequeCreate(void)
{
Deque *d;
/*
* We don't allocate the full space for this object
* because we don't use the value field in the dummy head.
*
* Saving these 4 bytes doesn't make a lot of sense here,
* but it might be more significant if the value field was larger.
*/
d = malloc(offsetof(struct deque, value));
/* test is to deal with malloc failure */
if(d) {
d->next[DEQUE_FRONT] = d->next[DEQUE_BACK] = d;
}
return d;
}
void
dequePush(Deque *d, int direction, int value)
{
struct deque *e; /* new element */
assert(direction == DEQUE_FRONT || direction == DEQUE_BACK);
e = malloc(sizeof(struct deque));
assert(e);
e->next[direction] = d->next[direction];
e->next[!direction] = d;
e->value = value;
d->next[direction] = e;
e->next[direction]->next[!direction] = e; /* preserves invariant */
}
int
dequePop(Deque *d, int direction)
{
struct deque *e;
int retval;
assert(direction == DEQUE_FRONT || direction == DEQUE_BACK);
e = d->next[direction];
if(e == d) {
return DEQUE_EMPTY;
}
/* else remove it */
d->next[direction] = e->next[direction];
e->next[direction]->next[!direction] = d;
retval = e->value;
free(e);
return retval;
}
int
dequeIsEmpty(const Deque *d)
{
return d->next[DEQUE_FRONT] == d;
}
void
dequeDestroy(Deque *d)
{
while(!dequeIsEmpty(d)) {
dequePop(d, DEQUE_FRONT);
}
free(d);
}
examples/linkedLists/deque/deque.c
And here is some test code:
Alternate implementation using a ring buffer
The deque.h file carefully avoids revealing any details of the implementation of a deque. This allows us to replace the implementation with a different implementation that is more efficient in its use of both time and space, at the cost of additional code complexity. Below is a replacement for deque.c that uses a ring buffer in place of the circular linked list.
The idea of a ring buffer is to store the deque elements in an array, with a pointer to the first element and a length field that says how many elements are in the deque. The information needed to manage the array (which is allocated using malloc) is stored in a struct.
The sequence of elements wraps around the endpoints of the array, leaving a gap somewhere in the middle. Deque pushes extend the sequence into this gap from one side or another, while pops increase the size of the gap. If the user wants to do a push and the array is full, we build a new, larger deque, move all the elements there, and then transplant all the bits of the new struct deque into the old one. This transplant trick avoids changing the address of the struct deque that the user needs to access it.
#include <stdlib.h>
#include <assert.h>
#include "deque.h"
/*
* Alternative implementation of a deque using a ring buffer.
*
* Conceptually, this is an array whose indices wrap around at
* the endpoints.
*
* The region in use is specified by a base index pointing
* to the first element, and a length count giving the number
* of elements. A size field specifies the number of slots
* in the block.
*
* Picture:
*
* ---------------------------------------------------
* |7|8|9| | | | | | | | | | | | | | | | |1|2|3|4|5|6|
* ---------------------------------------------------
* ^ ^
* | |
* base + length - 1 base
*
*/
struct deque {
size_t base; /* location of front element */
size_t length; /* length of region in use */
size_t size; /* total number of positions in contents */
int *contents;
};
#define INITIAL_SIZE (8)
/* create a new deque of the given size */
static Deque *
dequeCreateInternal(size_t size)
{
struct deque *d;
d = malloc(sizeof(struct deque));
assert(d);
d->base = 0;
d->length = 0;
d->size = size;
d->contents = malloc(sizeof(int) * d->size);
assert(d->contents);
return d;
}
/* return a new empty deque */
Deque *
dequeCreate(void)
{
return dequeCreateInternal(INITIAL_SIZE);
}
void
dequePush(Deque *d, int direction, int value)
{
struct deque *d2; /* replacement deque if we grow */
int *oldContents; /* old contents of d */
/*
* First make sure we have space.
*/
if(d->length == d->size) {
/* nope */
d2 = dequeCreateInternal(d->size * 2);
/* evacuate d */
while(!dequeIsEmpty(d)) {
dequePush(d2, DEQUE_BACK, dequePop(d, DEQUE_FRONT));
}
/* do a transplant from d2 to d */
/* but save old contents so we can free them */
oldContents = d->contents;
*d = *d2; /* this is equivalent to copying the components one by one */
/* these are the pieces we don't need any more */
free(oldContents);
free(d2);
}
/*
* This requires completely different code
* depending on the direction, which is
* annoying.
*/
if(direction == DEQUE_FRONT) {
/* d->base is unsigned, so we have to check for zero first */
if(d->base == 0) {
d->base = d->size - 1;
} else {
d->base--;
}
d->length++;
d->contents[d->base] = value;
} else {
d->contents[(d->base + d->length++) % d->size] = value;
}
}
/* pop and return first value on direction side of deque d */
/* returns DEQUE_EMPTY if deque is empty */
int
dequePop(Deque *d, int direction)
{
int retval;
if(dequeIsEmpty(d)) {
return DEQUE_EMPTY;
}
/* else */
if(direction == DEQUE_FRONT) {
/* base goes up by one, length goes down by one */
retval = d->contents[d->base];
d->base = (d->base+1) % d->size;
d->length--;
return retval;
} else {
/* length goes down by one */
return d->contents[(d->base + --d->length) % d->size];
}
}
int
dequeIsEmpty(const Deque *d)
{
return d->length == 0;
}
void
dequeDestroy(Deque *d)
{
free(d->contents);
free(d);
}
examples/linkedLists/deque/ringBuffer.c
Here is a Makefile that compiles testDeque.c against both the linked list and the ring buffer implementations. You can do make time to race them against each other.
CC=gcc
CFLAGS=-Wall -O3 -g3
# how many iterations for test
ITERATIONS=10000000
VALGRIND_ITERATIONS=100
all: testDeque testRingBuffer
test: all
./testDeque $(ITERATIONS)
valgrind -q --leak-check=yes ./testDeque $(VALGRIND_ITERATIONS)
./testRingBuffer $(ITERATIONS)
valgrind -q --leak-check=yes ./testRingBuffer $(VALGRIND_ITERATIONS)
time: all
time ./testDeque $(ITERATIONS)
time ./testRingBuffer $(ITERATIONS)
testDeque: testDeque.o deque.o
$(CC) $(CFLAGS) -o $@ $^
testRingBuffer: testDeque.o ringBuffer.o
$(CC) $(CFLAGS) -o $@ $^
clean:
$(RM) testDeque testRingBuffer *.o
examples/linkedLists/deque/Makefile
#/media/File:Tallrik_-_Ystad-2018.jpg){kind=link}