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/Category:Data_structures.