# Implementing a queue using a linked list

A “queue” is an abstract data type that provides `enqueue` and `dequeue` operations which behave like a queue of people. There are many ways to implement a queue, but a natural way is with a “linked list”.

A linked list is a concrete data type consisting of “nodes” in a chain. To implement a queue, we need to keep references to both ends of the linked list: the “head” and the “tail”. But which should be the “front” of the list, the “head” or the “tail”?

The answer is: the head should be the front of the list. This allows us to update the front when dequeueing, because it holds a pointer to the new front of the list.

Here’s an implementation in C:

``````#include <stdlib.h>
#include <assert.h>

typedef struct Node {
int val;
struct Node * next;
} Node;

Node* new_node(int val, Node* next) {
Node* node = malloc(sizeof(Node));
node->val = val;
node->next = next;
return node;
}

// ----------------------------------------------------
// ------------------- QUEUE API ----------------------

typedef struct Queue {
Node* front;
Node* back;
} Queue;

int dequeue(Queue* queue) {
Node* front = queue->front;
if (front == NULL) return -1;
int x = front->val;
queue->front = front->next;
if (queue->front == NULL) queue->back = NULL;
free(front);
return x;
}

void enqueue(Queue* queue, int x) {
Node* node = new_node(x, NULL);
if (queue->back == NULL) {
queue->front = node;
} else {
queue->back->next = node;
}
queue->back = node;
}

Queue* new_queue() {
return calloc(1, sizeof(Queue));
}

void delete_queue(Queue* queue) {
while(dequeue(queue) != -1);
free(queue);
}

// ----------------------------------------------------
// --------------------- TESTS ------------------------

int main(int argc, char** argv) {
Queue* queue = new_queue();
assert(dequeue(queue) == -1);
enqueue(queue, 1);
assert(dequeue(queue) == 1);
assert(dequeue(queue) == -1);
enqueue(queue, 1);
enqueue(queue, 2);
enqueue(queue, 3);
assert(dequeue(queue) == 1);
assert(dequeue(queue) == 2);
assert(dequeue(queue) == 3);
assert(dequeue(queue) == -1);
assert(dequeue(queue) == -1);
delete_queue(queue);
}
``````

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only \$19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s \$29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

### More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer.