Algorithm Runtime as a Function of Structure Size

Function Best Case Worst Case
create O(1) O(1)
destroy O(n) O(n)
append O(1) O(1)
insert O(1) O(n)
remove O(1) O(n)
get O(1) O(n)
length O(1) O(1)
toarray O(n) O(n)

Source Code

linked_list.c

#include <stdlib.h>
#include "linked_list.h"

struct linked_list_node {
	struct linked_list_node *next;
	void *data;
};

struct linked_list_handle {
	struct linked_list_node *head;
	struct linked_list_node *tail;
	int length;
};

linked_list* linked_list_create(void) {
	struct linked_list_handle *new = malloc(sizeof(struct linked_list_handle));
	if(new != NULL) {
		new->length = 0;
		new->head = new->tail = NULL;
	}
	return new;
}

void linked_list_destroy(linked_list *handle) {
	struct linked_list_node *current = handle->head;
	struct linked_list_node *next;
	while(current != NULL) {
		next = current->next;
		free(current);
		current = next;
	}

	free(handle);
	return;		
}

int linked_list_append(linked_list *handle, void *data) {	
	struct linked_list_node *new = malloc(sizeof(struct linked_list_node));
	if(new == NULL) return LINKED_LIST_MALLOC_ERROR;

	new->data = data;
	new->next = NULL;

	if(handle->tail == NULL) { 
		handle->head = handle->tail = new;
	} else {
		handle->tail->next = new;
		handle->tail = new;
	}

	handle->length++;
	return LINKED_LIST_OK;
}

int linked_list_insert(linked_list *handle, int index, void* data) {
	struct linked_list_node *new;
	struct linked_list_node *curr;	

	if(index ==	0) {
		new = malloc(sizeof(struct linked_list_node));
		new->data = data;
		new->next = handle->head;
		handle->head = new;
	} else {
		curr = handle->head;
		while(index-- > 1) {
			if(curr == NULL) return LINKED_LIST_OUT_OF_BOUNDS;
			curr = curr->next;
		}

		if(curr == NULL) return LINKED_LIST_OUT_OF_BOUNDS;
		new = malloc(sizeof(struct linked_list_node));
		new->data = data;
		new->next = curr->next;
		curr->next = new;			
	}

	if(new->next == NULL)
		handle->tail = new;

	handle->length++;
	return 0;
}

void* linked_list_remove(linked_list *handle, int index) {
	struct linked_list_node *old;
	struct linked_list_node *prev;
	void *old_data;

	if(handle->head == NULL) return NULL;

	if(index == 0) {
		old = handle->head;
		handle->head = old->next;	
		old_data = old->data;
		free(old);
	} else {
		old = handle->head;
		while(index-- > 0) {
			if(old == NULL) return NULL;
			prev = old;
			old = old->next;
		}
		if(old == NULL) return NULL;

		if(old->next == NULL) {
			handle->tail = prev;
			prev->next = NULL;
		} else {
			prev->next = old->next;
		}
		
		old_data = old->data;
		free(old);
	}

	handle->length--;
	return old_data;
}

void* linked_list_get(linked_list *handle, int index) {
	if(handle->head == NULL || handle->tail == NULL) return NULL;

	struct linked_list_node *curr;

	if(index == -1) {
		return handle->tail->data;
	} else {
		curr = handle->head;
		while(index-- > 0) {
			if(curr == NULL) return NULL;
			curr = curr->next;
		}
		if(curr == NULL) return NULL;
		return curr->data;
	}
}
 
int linked_list_length(linked_list *handle) { return handle->length; };

int linked_list_toarray(linked_list *handle, void *output[], int outlen) {
	int i = 0;
	struct linked_list_node *current = handle->head;
	while(i<outlen && current != NULL) {
		output[i++] = current->data;
		current = current->next;
	}
	return i;
}

linked_list.h

#pragma once

#define LINKED_LIST_OK 0
#define LINKED_LIST_OUT_OF_BOUNDS -1
#define LINKED_LIST_MALLOC_ERROR -2

typedef struct linked_list_handle linked_list;

linked_list* linked_list_create(void);
void  linked_list_destroy(linked_list *handle);
int   linked_list_length( linked_list *handle);
int   linked_list_insert( linked_list *handle, int index, void* data);
int   linked_list_append( linked_list *handle, void *data);
void* linked_list_remove( linked_list *handle, int index);
void* linked_list_get(    linked_list *handle, int index) ;
int   linked_list_toarray(linked_list *handle, void *output[], int outlen);