Skip to content

Instantly share code, notes, and snippets.

@pseudomuto
Created August 25, 2013 16:30
Show Gist options
  • Save pseudomuto/6334796 to your computer and use it in GitHub Desktop.
Save pseudomuto/6334796 to your computer and use it in GitHub Desktop.
Blog Code: Implementing a Generic Linked List in 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;
}
#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
#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);
}
@Philhil
Copy link

Philhil commented Oct 7, 2016

I think you have to add
if(list->freeFn){ list->freeFn(node->data); }
in list.c row 89

But i like it !

@Moo2017
Copy link

Moo2017 commented May 30, 2018

Hi, anyone has an idea how use this for structure which has some void pointer member?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment