Thread: Linked list possible memory leak?

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;
  
  
}

Well you don't free list_props

Ha... so I don't.

Nice...

EDIT: yea, that was the whole problem. Now valgrind complains that I am using unititalized values in the print fucntion - is that just complaining about my comparison of iter to NULL?

The hurt isn't when you're doing it right, it's when you're doing it wrong.

NOT casting and NOT including stdlib.h gets you an error message you really need to pay attention to.

See the FAQ

Creating a dummy node at the head of the list is a waste.

This code

Code:

  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;
  }

I would swap the two statements. No sense running the list before checking to see if input is valid or not. Also, why can't the head be replaced? Arbitrary decision?

Code added:

Code:

void get_pointer(list_info *list_props, node *ptr, int i)
{
  if (i > list_props->length)
  {
    printf("Cannot get pointer for index %d: invalid index\n",i);
    ptr=NULL;
  }
  else if (i==-1) //get last node
  {
    for (ptr=list_props->head; ptr->next!=NULL; ptr=ptr->next);
  }
  else
  {
    for (ptr=list_props->head; ptr!=NULL && ptr->index<i; ptr=ptr->next);
  }
}

I want to get a pointer to to the node with index i with that. For some reason, if I call it in main as follows:

Code:

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);
  
  
  node *ptr;
  get_pointer(list_props, ptr, 1);
  printf("%d --> %d\n",ptr->index,ptr->data);
  
  
  
  
  
  
  
  
  print_list(list_props);
  check = free_end_of_list(list_props, 3);
  printf("%d free'd\n",check);
  print_list(list_props);
  check = free_list(list_props);
  printf("%d free'd\n",check);
  free(list_props);
  return 0;
  
  
}

The contents of pointer are garbage, but the contents of the element with index 1 are not. Now, I'm sure it's something simple I am missing... Can someone point it out?

> Who said the head was a dummy node?
Well you treat it as a special case when you add it, and then you also have a specific case if you try and delete it.

Neither of these should be true.