Hey all,
It occurred to me recently that in year of coding I have never learned to use linked lists, so I decided to remedy that. I put together an implementation of a singly linked list.
Now, I ran this through valgrind, and it says that there are several blocks "possibly lost" but I can't find where I would get a memory leak here. Can someone point it out?
And, any general criticisms or suggestions are welcome as well, since I did this from scratch off the top of my head and I am sure there are ways to improve on it.
Code:#include <stdio.h> #include <stdlib.h> typedef struct node { int index; int data; struct node *next; }node; //data type for linked list nodes typedef struct list_info { int length; int size_of_elements; node *head; node *latest; }list_info; //data type to keep track of the current state of the list; /******************************************** *Free the entire list */ int free_list(list_info *list_props) { node *current; node *iter; int i; int freecount=0; current=list_props->head; while (current!=NULL) { iter=current->next; free(current); current=iter; freecount++; list_props->length--; } return freecount; } /******************************************** *After adding a new node in the middle of the list, we need to fix the indices of other nodes */ void re_Index_List(list_info *list_props) { int count=0; node *iter; for (iter=list_props->head; iter!=NULL; iter=iter->next) { iter->index=count; count++; } } /******************************************** *print the index of the nodes along with the data they store */ void print_list(list_info *list_props) { node *iter; for (iter=list_props->head; iter!=NULL;iter=iter->next) { printf("%d\t%d\n",iter->index,iter->data); } } /******************************************** *Multipurpose node adder: *add a node at the end of the list if position desired exceeds the end *add a node in the position specificed otherwise */ int add_node(list_info *list_props, int position) { node *iter; node *newnode; if ((newnode=malloc(sizeof(node)))==NULL) { printf("Cannot allocate new node in position %d\n",position); abort(); } for (iter=list_props->head;iter->next!=NULL && iter->next->index<position; iter=iter->next); if (position==0) { printf("Cannot replace head\n"); return -1; } if (iter->next==NULL) //if we get to the end of the list before we are at the relevent position { iter->next=newnode; newnode->next=NULL; newnode->index=list_props->length; newnode->data=0; list_props->latest=newnode; list_props->length++; return 1; } else //we are adding a node in the middle of the list { node *temp; temp=iter->next; iter->next=newnode; newnode->next=temp; newnode->data=0; re_Index_List(list_props); list_props->latest=newnode; list_props->length++; return 2; } } int main(void) { list_info *list_props; if ((list_props=malloc(sizeof(list_info)))==NULL) { printf("cannot allocate memory for list_info\n"); abort(); } if ((list_props->head=malloc(sizeof(node)))==NULL) { printf("cannot allocate memory for head\n"); abort(); } int check; list_props->length=1; list_props->size_of_elements=sizeof(node); list_props->head->next=NULL; check = add_node(list_props, 1); list_props->latest->data=12; printf("check 1 = %d\n",check); add_node(list_props, 2); list_props->latest->data=15; printf("check 2 = %d\n",check); add_node(list_props, 3); list_props->latest->data=2; printf("check 3 = %d\n",check); add_node(list_props, 4); list_props->latest->data=5; printf("check 4 = %d\n",check); check = add_node(list_props, 3); list_props->latest->data=17; printf("check 5 = %d\n",check); check = add_node(list_props, 1); list_props->latest->data=4; printf("check 6 = %d\n",check); print_list(list_props); check = free_list(list_props); printf("%d free'd\n",check); return 0; }