linked list in C

[haglerchristopher]

I am trying to write a linkedlist in c, but for some reason I have run into a problem where the list head is always NULL. Maybe I am overlooking something, but I have not been able to figure this out. Any help will be appreciated. I am trying to test out the contains function, but it always return NO because the compare function is never being called. I believe it is because the list head is always NULL so it never tries to call the compare function. Therefore, I assume the error is within my list_insert function.

#ifndef linkedlist_H
#define linkedlist_H

typedef struct list linkedlist;

/*
 * Create an initial empty linkedlist.
 * 
 * @list:	The list to initialize
 */
void list_init(linkedlist **list);

/*
 * Destroy The linkedlist and the data that is contained therein.
 *
 * @list: 	The list to destroy.
 * @free_data: 	The function responsible for destroying the data held within the list nodes
 */
void list_destroy(linkedlist *list, void (*free_data)(void *));

/*
 * Insert a new element into the head of the list
 *
 * @list: 	The list to insert the element into.
 * @data: 	The data that is inserted into the list
 */
void list_insert(linkedlist *list, const void *data);

/*
 * Remove the data from the list. If data is NULL then the data at list head is
 * removed.
 *
 * @list: 	The list to search
 * @data:	The data element to remove from the list. 
 * @element: 	element will point to the list element that was removed
 * @compare: 	The compare function that knows how to compare the data
 *  	     	contained in the list
 */
void list_remove(linkedlist *list, const void *data, void **element, 
				int (*compare)(void *key1, void *key2));

/*
 * Search the list for the element specified by data
 *
 * @list:	The list to search.
 * @data: 	The data to search for.
 * @compare: 	The function that knows how to compare the data.
 * 
 * return: 0 if the list contains the data and -1 otherwise.
 */
int list_contains(linkedlist *list, const void *data, 
		int (*compare)(const void *key1, const void *key2));

/*
 * Return the size of the list
 *
 * @list: 	The list whose size (the number of elements) that will be returned.
 */
int list_size(linkedlist *list);

void list_print(linkedlist *list, void (*print)(void *data));

#endif /* linkedlist.h */ 

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

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

struct list {
	struct list_node *head;
	struct list_node *tail;
};

void list_init(linkedlist **list)
{
	*list = (linkedlist *)malloc(sizeof(struct list));

	(*list)->head = NULL;
	(*list)->tail = NULL;
}

void list_destroy(linkedlist *list, void (free_data)(void *))
{
	if (list->head == NULL)
		return;
	else {
		struct list *tmp = list;
		tmp->head = tmp->head->next;

		list_destroy(tmp, free_data);
		free_data(tmp->head->data);
		tmp->head->next = NULL;
	}
}

void list_insert(linkedlist *list, const void *data)
{
	struct list_node *node = (struct list_node *) malloc(sizeof(struct list_node));
	node->data = data;
	node->next = NULL;

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

void list_remove(linkedlist *list, const void *data, void **element, 
					int (*compare)(void *key1, void *key2))
{
	
}

int list_contains(linkedlist *list, const void *data, 
			int (*compare)(const void *key1, const void *key2))
{
	if (list->head == NULL)
		return -1;
	
	struct list_node *tmp = list->head;

	int result = -1;
	while (tmp->next) {
		if ((result = compare(tmp->data, data)) == 0);
                         return result;
	}
	return result;
}

int list_size(linkedlist *list)
{
	if (list->head == NULL)
		return 0;
	else {
		struct list *tmp_list = list;
		tmp_list->head = tmp_list->head->next;

		return 1 + list_size(tmp_list);
	}
}

void list_print(linkedlist *list, void (*print)(void *data)) {
	printf("list head: %p", list->head);
	if(list->head) {
		struct list_node *tmp = list->head;
		while(tmp->next) {
			print(tmp->data);
		}
	}
}

#include <stdio.h>
#include "linkedlist.h"

struct fraction {
	int num;
	int denom;
};

void print(void *data)
{
	printf("Node Data: %i\n", ((struct fraction *)data)->num);
}

int compare(const void *key1, const void *key2)
{
	printf("weeeeee");
	return ((struct fraction *)key1)->num - ((struct fraction *)key2)->num;
}

int main(int argc, char **argv)
{
	linkedlist *list;
	list_init(&list);

	struct fraction f1 = {1, 2};
	struct fraction f2 = {3, 4};

	list_insert(list, &f1);
	list_insert(list, &f2);

	printf("list size: %i\n", list_size(list));
	printf("linkedlist contains f1: %s\n", list_contains(list, &f1, &compare) == 0 ? "YES" : "NO");
	list_print(list, &print);
}

Thanks in advance for the help

[tanezavm]

int list_size(linkedlist *list)
{
	if (list->head == NULL)
		return 0;
	else {
		struct list *tmp_list = list;
		tmp_list->head = tmp_list->head->next;

		return 1 + list_size(tmp_list);
	}
}

That is because of this function list_size();
The main culprit is the line 7 where list->head will be set to NULL at some point of the recursion step. You get the correct list size but after the call to this, your link-list is gone. You should not modify the head. Change your logic and as much as possible don't use this recursive way of getting the list size if you don't exactly know how it works. You can do it using a while loop anyway.

[haglerchristopher]

Thanks for the help. I see exactly what you are talking about.