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);
I just released Vidrio, a free app for macOS and Windows to make your screen-sharing awesomely holographic. Vidrio shows your webcam video on your screen, just like a mirror. Then you just share or record your screen with Zoom, QuickTime, or any other app. Vidrio makes your presentations effortlessly engaging, showing your gestures, gazes, and expressions. #1 on Product Hunt. Available for macOS and Windows.

With Vidrio

With generic competitor

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.