inserting into a linked list

I have taken a data structures class which focused primarily on implementing in java but I am trying to apply my knowledge by implementing a few structures in a different language.

currently I am trying to implement a linked list. I have managed to get it working fine so far, but am having trouble with the insert function. I can only insert at the top of the list, after the header. To insert after any given node I must set my current node to current->next after the insertion is completed. How can I accomplish this within the function itself? Thanks for your help. I've posted my code below.

Code:

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

void printList(struct node* list);
int isEmpty(struct node* list);
void makeEmpty(struct node* list);
struct node* find(struct node* list, int item);
void insert(struct node* p, int item);
void removeNode(struct node *list, int item);

struct node
{
	int data;
	struct node* next;
};


int main()
{
	struct node *root;
	struct node *current;
	struct node **ptr_to_head = &root;
	int k;

	root = (struct node*)malloc(sizeof(struct node));
	root->next = NULL;
	root->data = NULL;
	current = root;

	for(k = 1; k < 10; k++)
	{
		insert(current, k * 5);
		current = current->next;
	}

	printList(root);

	return 0;
}

int isEmpty(struct node* list)
{
	if(list->next == NULL)
		return 1;
	return 0;
}

void makeEmpty(struct node* list)
{
	list->next = NULL;
}

void printList(struct node *list)
{
	struct node* current;

	if(isEmpty(list))
		printf("List is empty.\n");
	else
	{
		current = list->next;
		while(current->next != NULL)
		{
			printf("%d\n", current->data);
			current = current->next;
		}
		printf("%d\n", current->data);
	}

}

/*returns a node containing the item in the list. If item is
 *not found then a null value is returned
 */

struct node* find(struct node *list, int item)
{
	struct node *p = list->next;
	if(p != NULL)
	{
		while(p->next != NULL)
		{
			if(p->data == item)
				return p;
			p = p->next;
		}
	}

	return NULL;
}

//inserts item at the front of the list

void insert(struct node *list, int item)
{
	if(list != NULL)
	{
		struct node* p = (struct node*)malloc(sizeof(struct node));
		p->data = item;
		p->next = list->next;
		list->next = p;
	}
}

void removeNode(struct node *list, int item)
{
	struct node *current = list->next;
	struct node *previous = list;

	if(isEmpty(list))
		printf("List is empty.");
	else
	{
		while(current->next != NULL && current->data != item)
		{
			previous = current;
			current = current->next;
		}
		if(current->data == item)
		{
			previous->next = current->next;
			free(current);
		}
		else
			printf("Value not in list.\n");
	}
}

Compile with warnings turned all the way up. In GCC, use the -Wall flag. If you have another compiler, you will have to check it's documentation.

Code:

$ make list
gcc -Wall -g -std=c99  -lssl -lm -lpthread -lcurses -lefence  list.c   -o list
list.c:4: warning: ‘struct node’ declared inside parameter list
list.c:4: warning: its scope is only this definition or declaration, which is probably not what you want
list.c:5: warning: ‘struct node’ declared inside parameter list
list.c:6: warning: ‘struct node’ declared inside parameter list
list.c: In function ‘main’:
list.c:27: warning: assignment makes integer from pointer without a cast
list.c:36: warning: passing argument 1 of ‘printList’ from incompatible pointer type
list.c:4: note: expected ‘struct node *’ but argument is of type ‘struct node *’
list.c:22: warning: unused variable ‘ptr_to_head’
list.c: At top level:
list.c:41: error: conflicting types for ‘isEmpty’
list.c:5: note: previous declaration of ‘isEmpty’ was here
list.c:48: error: conflicting types for ‘makeEmpty’
list.c:6: note: previous declaration of ‘makeEmpty’ was here
list.c:53: error: conflicting types for ‘printList’
list.c:4: note: previous declaration of ‘printList’ was here
make: *** 
[list] Error 1

Most of those can be fixed by simply moving the struct definition above your function prototypes. After doing that, all that is left is:

Code:

$ make list
gcc -Wall -g -std=c99  -lssl -lm -lpthread -lcurses -lefence  list.c   -o list
list.c: In function ‘main’:
list.c:27: warning: assignment makes integer from pointer without a cast
list.c:22: warning: unused variable ‘ptr_to_head’

Line 27, you do root->data = NULL. NULL is a pointer type, data is an int. Set it equal to 0.

To do what you want, you need to pass in a pointer to current, i.e. a struct node **, to insert. Something like this (which is untested):

Code:

void insert(struct node **list, int item)  // note the double * there
{
    // exact same code as your existing insert function, but using *list everywhere instead of list
    // list now points to current, so to actually access current, you must use *list

    // at the end of the function, update *list, or current in your main function
    *list = (*list)->next;
}

// when you call insert, pass in a pointer to current (i.e. the address of current)
insert(&current, k * 5);

EDIT: I should tell you, you have a somewhat unconventional way of implementing a linked list in C. Having a current node outside your insert function, basically just to track the end of the list is not ideal. Using a "dead" node at the beginning to signify an empty list is also not ideal. I would either just set the root pointer to NULL, or create a special node that perhaps contains other useful stuff. A typical list header node would contain a pointer to the start of the list, perhaps a pointer to the end, and a count of elements in it.

ok. I will try and make some improvements. Do you know of a good reference, be it book or website, for implementing linked lists and binary trees in C? My implementation is pretty much based off of my C text book. It is "Engineering Problem Solving with C" by Delores M. Etter. Thanks for your help.

A quick Google search brought up several tutorials of varying quality. This one seemed to be pretty good: http://en.literateprograms.org/Categoryata_structures.