Learn more about Russian war crimes in Ukraine.

Implementing a stack using a linked list

A “stack” is an abstract data type that provides push and pop operations which behave like “a stack of plates”. There are many ways to implement a stack, but a very natural way is with a “linked list”. A linked list is a concrete data type consisting of “nodes” in a chain. The head of the list represents the top of the stack. 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;

// ----------------------------------------------------
// ------------------- STACK API ----------------------

typedef Node** Stack;

int pop(Stack stack) {
  Node* top = *stack;
  if (top == NULL) return -1;
  *stack = top->next;
  int x = top->val;
  return x;

void push(Stack stack, int x) {
  *stack = new_node(x, *stack);

Stack new_stack() {
  return calloc(1, sizeof(Node*));

void destroy_stack(Stack stack) {
  while(pop(stack) != -1);

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

int main(int argc, char** argv) {
  Stack stack = new_stack();
  assert(pop(stack) == -1);
  push(stack, 1);
  assert(pop(stack) == 1);
  assert(pop(stack) == -1);
  push(stack, 1);
  push(stack, 2);
  push(stack, 3);
  assert(pop(stack) == 3);
  assert(pop(stack) == 2);
  assert(pop(stack) == 1);
  assert(pop(stack) == -1);
  assert(pop(stack) == -1);

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. Found an error? Edit this page.