Basic C linked list example

5 March 2021

A simple if slightly contrived example of linked lists in C below.

Why use a linked list? A linked list allows data structures (i.e. structs in C) to be linked together as they are used, which is useful if you don’t know how much input is coming in and you need flexibility. Memory is allocated from the heap with malloc rather than from the stack (as a local or global variable created as the programme is executed).

First let’s have a look at what’s in a hypothetical example folder with tree:

.
├── linked-list-a
├── linked-list-a.c
├── linked-list-b
├── linked-list-b.c
└── makefile

A simple makefile is always useful to make compilation more straightforward but is not strictly necessary. This simple makefile just sets up compiler flags for sensible warnings, inclusion of debugging info in the binary, and tells the compiler we want to use C11. cat makefile:

CC=clang
CFLAGS=-glldb -O0 -std=c11 -Wall -Werror -Wextra -Wno-sign-compare -Wno-unused-parameter -Wno-unused-variable -Wshadow

default: linked-list-a linked-list-b

linked-list-a: linked-list-a.c
	$(CC) $(CFLAGS) linked-list-a.c -o linked-list-a

linked-list-b: linked-list-b.c
	$(CC) $(CFLAGS) linked-list-b.c -o linked-list-b

.PHONY: clean

clean:
	rm -fr *.dSYM

Let’s see the source for the first example, which creates a linked list of 3 random digits in the range 0-9.

cat linked-list-a.c:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct ll_digit {
  char digit;
  struct ll_digit *next;
} ll_digit;

char rrrand()
{
  struct timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);

  // Returns a random number [0,9]
  srandom(ts.tv_nsec); // seed
  int random_int = (random() / ((double) RAND_MAX + 1)) * 10;
  // printf("%d randomly generated\n", random_int);
  return '0' + random_int;
}

ll_digit* make_ll()
{
  // for (int i = 0; i < n_items; i++)

  // head
  ll_digit *list = malloc(sizeof(ll_digit));

  if (list == NULL)
    exit(1);

  list = NULL;

  // first node

  ll_digit *n = malloc(sizeof(ll_digit));
  if (n == NULL)
    exit(1);

  n->digit = rrrand();
  n->next = NULL; // for now; unless changed denotes end of list

  list = n;

  // second node

  n = malloc(sizeof(ll_digit));
  if (n == NULL)
    exit(1);

  n->digit = rrrand();
  n->next = NULL; // for now; unless changed denotes end of list

  list->next = n;

  // third node

  n = malloc(sizeof(ll_digit));
  if (n == NULL)
    exit(1);

  n->digit = rrrand();
  n->next = NULL; // for now; unless changed denotes end of list

  list->next->next = n;

  return list;
}

void print_ll(ll_digit *list)
{
  ll_digit* n = list;

  while (n != NULL)
  {
    printf("%c", n->digit);
    n = n->next;
  }
}

void free_ll(ll_digit *list)
{
  free(list->next->next);
  free(list->next);
  free(list);
}

int main (int argc, char** argv)
{
  ll_digit *list = NULL;

  list = make_ll();
  print_ll(list);
  free_ll(list);

  return 0;
}

When run, we get e.g. the following:

This seems a bit crude, so how about being able to accommodate a linked-list of random digits in the range 0-9 of an arbitrary length?

cat linked-list-b.c:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct ll_digit {
  char digit;
  struct ll_digit *next;
} ll_digit;

char rrrand()
{
  struct timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);

  // Returns a random number [0,9]
  srandom(ts.tv_nsec); // seed
  int random_int = (random() / ((double) RAND_MAX + 1)) * 10;
  return '0' + random_int;
}

void add_ll(ll_digit* list)
{
  ll_digit *n = malloc(sizeof(ll_digit));

  // check memory has been assigned and exit if not
  if (n == NULL) exit(1);

  // assign to node
  n->digit = rrrand();
  n->next = NULL; // for now; unless changed denotes end of list

  // walk through list until we find a node where n->next == NULL
  ll_digit* tmp = list;
  while (tmp->next != NULL)
  {
    tmp = tmp->next;
  }

  // point to the new node
  tmp->next = n;
}

void print_ll(ll_digit *list)
{
  ll_digit* n = list;

  while (n != NULL)
  {
    printf("%c", n->digit);
    n = n->next;
  }
  printf("\n");
}

void free_ll(ll_digit *list)
{
  while (list != NULL)
  {
    // assign pointer to next node so we don't lose track of it
    ll_digit *tmp = list->next;
    // free
    free(list);
    // update to point to next node (to free next time)
    list = tmp;
  }
}

int main (int argc, char** argv)
{
  if (argc != 2)
  {
    printf("Usage:\n\t%s n\nWhere n is the number of random digits in linked list\n", argv[0]);
    return 1;
  }

  int n_items = atoi(argv[1]);
  if (n_items == 0) return 0;

  // set up the first node in the linked list
  ll_digit *list = malloc(sizeof(ll_digit));
  // check memory has been assigned and exit if not
  if (list == NULL) exit(1);
  list->next = NULL;
  list->digit = rrrand();

  if (n_items > 1)
    for (int i = 0; i < n_items-1; i++)
      add_ll(list);

  print_ll(list);
  free_ll(list);

  return 0;
}

When run with an argument specifying how many digits we want, that is what we get e.g. running ./linked-list-b 6: