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;
  free(top);
  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);
  free(stack);
}

// ----------------------------------------------------
// --------------------- 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);
  destroy_stack(stack);
}

This page copyright James Fisher 2020. Content is not associated with my employer. Found an error? Edit this page.

Jim Fisher

CV

Speaking

Blogroll

RSS

TigYog

Kickabout