Blog Code: Implementing a Generic Linked List in C

list.c

#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
#include "list.h"
 
void list_new(list *list, int elementSize, freeFunction freeFn)
{
  assert(elementSize > 0);
  list->logicalLength = 0;
  list->elementSize = elementSize;
  list->head = list->tail = NULL;
  list->freeFn = freeFn;
}
 
void list_destroy(list *list)
{
  listNode *current;
  while(list->head != NULL) {
    current = list->head;
    list->head = current->next;

    if(list->freeFn) {
      list->freeFn(current->data);
    }

    free(current->data);
    free(current);
  }
}
 
void list_prepend(list *list, void *element)
{
  listNode *node = malloc(sizeof(listNode));
  node->data = malloc(list->elementSize);
  memcpy(node->data, element, list->elementSize);

  node->next = list->head;
  list->head = node;

  // first node?
  if(!list->tail) {
    list->tail = list->head;
  }

  list->logicalLength++;
}
 
void list_append(list *list, void *element)
{
  listNode *node = malloc(sizeof(listNode));
  node->data = malloc(list->elementSize);
  node->next = NULL;

  memcpy(node->data, element, list->elementSize);

  if(list->logicalLength == 0) {
    list->head = list->tail = node;
  } else {
    list->tail->next = node;
    list->tail = node;
  }

  list->logicalLength++;
}
 
void list_for_each(list *list, listIterator iterator)
{
  assert(iterator != NULL);
 
  listNode *node = list->head;
  bool result = TRUE;
  while(node != NULL && result) {
    result = iterator(node->data);
    node = node->next;
  }
}
 
void list_head(list *list, void *element, bool removeFromList)
{
  assert(list->head != NULL);
 
  listNode *node = list->head;
  memcpy(element, node->data, list->elementSize);
 
  if(removeFromList) {
    list->head = node->next;
    list->logicalLength--;
 
    free(node->data);
    free(node);
  }
}
 
void list_tail(list *list, void *element)
{
  assert(list->tail != NULL);
  listNode *node = list->tail;
  memcpy(element, node->data, list->elementSize);
}
 
int list_size(list *list)
{
  return list->logicalLength;
}

list.h

#ifndef __LIST_H
#define __LIST_H
 
// a common function used to free malloc'd objects
typedef void (*freeFunction)(void *);
 
typedef enum { FALSE, TRUE } bool;
 
typedef bool (*listIterator)(void *);
 
typedef struct _listNode {
  void *data;
  struct _listNode *next;
} listNode;
 
typedef struct {
  int logicalLength;
  int elementSize;
  listNode *head;
  listNode *tail;
  freeFunction freeFn;
} list;
 
void list_new(list *list, int elementSize, freeFunction freeFn);
void list_destroy(list *list);
 
void list_prepend(list *list, void *element);
void list_append(list *list, void *element);
int list_size(list *list);
 
void list_for_each(list *list, listIterator iterator);
void list_head(list *list, void *element, bool removeFromList);
void list_tail(list *list, void *element);
 
#endif

sample_app.c

#include <stdio.h>
#include <string.h>
 
#include "list.h"
 
void list_with_ints();
void list_with_strings();
 
bool iterate_int(void *data);
bool iterate_string(void *data);
void free_string(void *data);
 
int main(int argc, char *argv[])
{
  printf("Loading int demo...\n");
  list_with_ints();
  list_with_strings();
}
 
void list_with_ints()
{
  int numbers = 10;
  printf("Generating list with the first %d positive numbers...\n", numbers);
 
  int i;
  list list;
  list_new(&list, sizeof(int), NULL);
 
  for(i = 1; i <= numbers; i++) {
    list_append(&list, &i);
  }
 
  list_for_each(&list, iterate_int);
 
  list_destroy(&list);
  printf("Successfully freed %d numbers...\n", numbers);
}
 
void list_with_strings()
{
  int numNames = 5;
  const char *names[] = { "David", "Kevin", "Michael", "Craig", "Jimi" };
 
  int i;
  list list;
  list_new(&list, sizeof(char *), free_string);
 
  char *name;
  for(i = 0; i < numNames; i++) {
    name = strdup(names[i]);
    list_append(&list, &name);
  }
 
  list_for_each(&list, iterate_string);
 
  list_destroy(&list);
  printf("Successfully freed %d strings...\n", numNames);
}
 
bool iterate_int(void *data) 
{
  printf("Found value: %d\n", *(int *)data);
  return TRUE;
}
 
bool iterate_string(void *data)
{
  printf("Found string value: %s\n", *(char **)data);
  return TRUE;
}
 
void free_string(void *data)
{
  free(*(char **)data);
}