Stack and Queue Linked List Implementations

Question

I'm relatively new to C as a language, but I wouldn't call myself a beginner. That being said, I don't believe my C "coding style," so to speak, is particularly developed. Also, I'm new to error handling in C as well.

stack.c

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
 int val;
 struct node* next;
} node_t;
typedef struct stack {
 struct node* head;
} stack_t;
stack_t* create_list(void)
{
 stack_t* stack = malloc(sizeof *stack);
 if (stack != NULL) {
 stack->head = NULL;
 }
 return stack;
}
void push(stack_t* list, int val)
{
 node_t* newnode = malloc(sizeof *newnode);
 if (newnode != NULL) {
 newnode->val = val;
 newnode->next = list->head;
 }
 list->head = newnode;
}
int pop(stack_t* list)
{
 int val = list->head->val;
 node_t* next = list->head->next;
 free(list->head);
 list->head = next;
 return val;
}
void destroy_list(stack_t* list)
{
 do {
 node_t* head = list->head;
 node_t* next = head->next;
 free(head);
 list->head = next;
 } while (list->head);
 free(list);
}
void foreach(stack_t* list, int (*func)(const int))
{
 node_t* curr = list->head;
 do {
 curr->val = func(curr->val);
 curr = curr->next;
 } while(curr);
}
int print_val(const int val)
{
 printf("value: %d\n", val);
 return val;
}
int main(int argc, char* argv[])
{
 printf("creating list\n");
 stack_t* list = create_list();
 printf("pushing value 2\n");
 push(list, 2);
 printf("top value: %d\n", list->head->val);
 printf("pushing value 5\n");
 push(list, 5);
 printf("top value: %d\n", list->head->val);
 printf("iterating top-down\n");
 foreach(list, print_val);
 printf("popping top value\n");
 int popped = pop(list);
 printf("popped: %d\n", popped);
 printf("top value: %d\n", list->head->val);
 destroy_list(list);
 return 0;
}

queue.c

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
 int val;
 struct node* next;
} node_t;
typedef struct {
 node_t *head, *tail;
} queue_t;
queue_t* create_list(void)
{
 queue_t* queue = malloc(sizeof *queue);
 if (queue != NULL) {
 queue->head = queue->tail = NULL;
 }
 return queue;
}
void enqueue(queue_t* queue, int val)
{
 node_t* newnode = malloc(sizeof *newnode);
 if (newnode != NULL) {
 newnode->val = val;
 newnode->next = NULL;
 }
 if (queue->tail) {
 queue->tail->next = newnode;
 } else {
 queue->head = newnode;
 }
 queue->tail = newnode;
}
int dequeue(queue_t* queue)
{
 int val = queue->head->val;
 node_t* next = queue->head->next;
 free(queue->head);
 queue->head = next;
 return val;
}
void destroy_list(queue_t* queue)
{
 do {
 node_t* head = queue->head;
 node_t* next = head->next;
 free(head);
 queue->head = next;
 } while (queue->head);
 queue->head = queue->tail = NULL;
 free(queue);
}
void foreach(queue_t* list, int (*func)(const int))
{
 node_t* curr = list->head;
 do {
 curr->val = func(curr->val);
 curr = curr->next;
 } while(curr);
}
int print_val(const int val)
{
 printf("value: %d\n", val);
 return val;
}
int main(int argc, char* argv[])
{
 printf("creating list\n");
 queue_t* list = create_list();
 printf("enqueuing value 2\n");
 enqueue(list, 2);
 printf("top value: %d\n", list->head->val);
 printf("enqueueing value 5\n");
 enqueue(list, 5);
 printf("top value: %d\n", list->head->val);
 printf("iterating top-down\n");
 foreach(list, print_val);
 printf("dequeueing top value\n");
 int dequeued = dequeue(list);
 printf("dequeued: %d\n", dequeued);
 printf("top value: %d\n", list->head->val);
 destroy_list(list);
 return 0;
}

Answer 1

• Naming

  stack_t * create_list(); and queue_t create_list() are misnomers. To begin with, you cannot use both of them in the same applications. Besides, it discloses unnecessary details of the implementation, and really confuses the reviewer.

• DRY

  The common (list related) code shall be factored out into a list.c with the interfaces in list.h; stack.c and queue.c should use the exported interfaces, for example,

  void destroy_stack(stack_t * stack)
  {
   destroy_list(stack->head);
  }
  

• Empty object is valid

  destroy_list and foreach suffer the common problem: they presume that the list is not empty. An attempt to apply them to an empty object results in a null-pointer dereference. Use while() {} instead.

• enqueue is implemented correctly, kudos.

• robbie: Thanks for the review! I'm not sure why I went with do...while, it just seemed to make sense at the time. One question: what else would the common list code be besides destroying a chain of nodes?
• vnp: Creation of the list (which backs up creation of stack and queue); adding the node; removal of the node; in fact, anything which knows what the node_t is. For example, stack_pop shall be expressed in terms of list_remove_head.

Answer 2

There are some improvements you can make to your error handling (as you hinted there might be). Look at this method, for example:

void push(stack_t* list, int val)
{
 node_t* newnode = malloc(sizeof *newnode);
 if (newnode != NULL) {
 newnode->val = val;
 newnode->next = list->head;
 }
 list->head = newnode;
}

Let's walk through this, and see what happens when malloc() fails. We obviously don't dereference newnode (good), but we still assign newnode (i.e. NULL) to list->head. Now, we've not only cleared the entire list, but we no longer have a pointer to the old head of the list - that's a memory leak. And to cap it all, the calling code has no idea that the action it asked for hasn't been performed.

Consider instead this:

int push(stack_t *list, int val)
{
 node_t *newnode = malloc(sizeof *newnode);
 if (!newnode)
 return 0;
 newnode->val = val;
 newnode->next = list->head;
 list->head = newnode;
 return 1;
}

Because we return false immediately, the caller can see that push() failed. Also, we don't modify the list at all in the error case; this allows the caller greater ability to recover from the error (crucially, all the assigned nodes can still be released).

Note that the author of that code has to remember to check the return value. This is a common problem in C APIs (and some compilers allow you to annotate the function to indicate that the return value must be used). However, even if the return value is not checked, the new code at least leaves the structures in a valid state (i.e. it doesn't leak).

You might want to include <stdbool.h> and use the provided boolean type instead of int for the return type, to make that clearer. Also, see that I use the pointer directly as a boolean - that's possibly more idiomatic than testing equality to NULL (but some people prefer the explicit style, so be consistent with what you find).