Deallocating memory for a linked list

This is a discussion on Deallocating memory for a linked list within the C Programming forums, part of the General Programming Boards category; Hi everyone, i am trying to deallocate the memory for i linked list i allocated using malloc. but i cannot ...

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    12

    Wink Deallocating memory for a linked list

    Hi everyone,
    i am trying to deallocate the memory for i linked list i allocated using malloc. but i cannot seem to clear the nodes.

    here is the relevant parts of my program:

    Code:
    struct node
    {
    	char depart[25];
    	char arrive[25];
    	int depart_time;
    	int arrive_time;
    	
    	int id;	
    
    	struct node *next;
    };
    This is where my structure 'node' is created.

    Code:
    struct node* mknode(char depstat[25], char arrstat[25], int dtime, int atime, int check)
    {
    	struct node* np;
    	
    	np=(struct node*)malloc(sizeof(struct node));
    	
    	if(np)
    	{
    		strcpy(np->depart,depstat);
    		strcpy(np->arrive,arrstat);
    		np->depart_time=dtime;
    		np->arrive_time=atime;
    		
    		np->id=check;
    		
    		np->next=NULL;
    	}
    	
    	return np;
    }
    This part is assigning values to each variable in the structure.

    Code:
    	struct node *n2;
    	int number;
    
    	for(number=1; number<=check; number++)
    	{
    		if(number==n->id)
    		{
    			n2=n;
    			n=n->next;
    			free(n2);
    			return 1;
    		}
    	}
    }
    I have tried to deallocate using this code(this is the part where i am sure it is going wrong)

    Code:
    deallocate(&n_start, check);
    and i call the function using this line

    the first node in the linked list is 'n_start'
    check is the number of nodes in the list

    i know that the nodes are all being created properly so that part is ok.

    and how can i check that the mmory is deallocated?can i use a simple printf of what should be deallocated?(btw: i am using OSX Tiger and Xcode if that makes a difference)

    thank you all very much

  2. #2
    Registered User wintellect's Avatar
    Join Date
    Mar 2006
    Posts
    24
    How many of the nodes are you trying to remove?

    All of them?

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    12
    yes, i intend to run the function just before the program closes so i can avoid memory leaks.

    so i dont need to bother about relinking the nodes on either side, i just need to remove everything

  4. #4
    Registered User vinit's Avatar
    Join Date
    Apr 2006
    Location
    India
    Posts
    39
    Code:
     deallocate(&n_start, check);
    is n_start poinrt???
    I mean struct node *n_start;
    You are passing n_start as "&n_start" inturn passing address where n_start is stored in memory, so that can be a problem,so you are probably accessing memory which is not urs,so that can be a problem.
    It would be better if u post ur entire code or atleast entire function.
    Thanks & Regards
    Vinit

  5. #5
    Registered User
    Join Date
    Nov 2005
    Posts
    95

    I hope this will answer

    I am not sure I understod you.
    But the a look at the deallocate function.

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <math.h>
    #include <limits.h>
    #include <string.h>
    #include <time.h>
    
    
    /* You don't need to worry about memory leaks. becasue as the 
       program closes, All the memory for this program is relased */
    
    struct node
    {
    	char depart[25];
    	char arrive[25];
    	int depart_time;
    	int arrive_time;
    	
    	int id;	
    
    	struct node *next;
    };
    
    
    struct node* mknode(char depstat[25], char arrstat[25], int dtime, int atime, int check)
    {
    	struct node* np;
    	
    	np=(struct node*)malloc(sizeof(struct node));
    	
    	if(np)
    	{
    		strcpy(np->depart,depstat);
    		strcpy(np->arrive,arrstat);
    		np->depart_time=dtime;
    		np->arrive_time=atime;
    		
    		np->id=check;
    		
    		np->next=NULL;
    	}
    	
    	return np;
    }
    
    
    
    void deallocate(struct node *phead)
    {
    struct node *pdel;
    
    
    while ( pdel = phead )
       {
       phead = phead->next;
    /* check that the mmory is deallocated */
       printf("Deallocate : %s %s %d %d %d\n", 
                pdel->depart, pdel->arrive, pdel->depart_time, pdel->arrive_time, pdel->id);
       free(pdel);
       }	
    
    }
    
    
    int main(void)
    {
    struct node *phead;
    struct node *pnew ;
    char Idepart[25];
    char Iarrive[25];
    int Idepart_time;
    int Iarrive_time;
    int Iid;	
    
    
    phead = NULL;
    for ( ;  ; )
       {
       printf("Enter depart arrive depart_time arrvie_time id\n");
       scanf("%s %s %d %d %d", Idepart, Iarrive, &Idepart_time,&Iarrive_time, &Iid);
       if ( Idepart[0] == 'q' )
           break; 
       if ( ! ( pnew = mknode(Idepart, Iarrive, Idepart_time,Iarrive_time, Iid)) )
          {
          printf("memory error\n");
          break;
          }
       pnew->next = phead;
       phead = pnew;
       }
    
    deallocate(phead);
    getchar();
    getchar();
    return(0);           
    }

  6. #6
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    You dellocate memory using free(). I haven't plugged this into the code, but I would maybe do something like the following to delete the nodes. This is only one way of approching the problem.

    Code:
    void deallocate(struct node *phead)
    {
     while(phead ! = NULL)
       struct node *temp = phead;
       phead = phead->next;
       free(temp);
     }
    }
    Last edited by cdalten; 04-10-2006 at 09:08 AM.

  7. #7
    Registered User
    Join Date
    Apr 2006
    Posts
    12
    thanks for the posts...i dont quite understand the function tho

    here is my whole code so far:
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    struct node
    {
    	char depart[25];
    	char arrive[25];
    	int depart_time;
    	int arrive_time;
    	
    	int id;	
    
    	struct node *next;
    };
    
    struct node* mknode(char depstat[25], char arrstat[25], int dtime, int atime, int check)
    {
    	struct node* np;
    	
    	np=(struct node*)malloc(sizeof(struct node));
    	
    	if(np)
    	{
    		strcpy(np->depart,depstat);
    		strcpy(np->arrive,arrstat);
    		np->depart_time=dtime;
    		np->arrive_time=atime;
    		
    		np->id=check;
    		
    		np->next=NULL;
    	}
    	
    	return np;
    }
    
    int direct(char depart[25], char arrive[25], int arrival, struct node *n, int check)
    {	
    	int direct_value=0,time=0;
    	
    	printf("\nDIRECT ROUTE: ");
    	
    	while((n->id)<=(check))
    	{	
    		if((strcmp(depart,n->depart)==0)&&(strcmp(arrive,n->arrive)==0)&&(n->arrive_time<=arrival)&&((arrival-200)<(n->arrive_time)))
    		{
    			time=duration(n->depart_time, n->arrive_time);
    			printf("\nDepart: %s at %.2d:%.2d\n",depart,n->depart_time/100,n->depart_time%100);
    			printf("Arrive: %s at %.2d:%.2d\nChange at: None\n",arrive,n->arrive_time/100,n->arrive_time%100);
    			printf("Duration: %.2d:%.2d\n",time/60,time%60);
    			direct_value=1;
    		}
    		
    		if((n->next) != NULL)
    			n=n->next;
    		else
    			break;
    	}
    	
    	if(direct_value==0)
    		printf("None\n");
    		
    	return 0;
    }
    
    int indirect(char depart[25], char arrive[25], int arrival, struct node *n,int check)
    {
    	struct node *second_node=NULL, *head=NULL;
    	char change_station[25];
    	int loops=1,change=0,indirect_value=0;
    	int wait_time,time;
    	
    	head=n;
    	second_node=n;
    	
    	printf("\nINDIRECT ROUTE: ");
    	
    	while((second_node->id) <= check)
    	{		
    		if(strcmp(depart,second_node->depart)==0)
    			{
    				strcpy(change_station,second_node->arrive);
    				change=1;
    			}
    		
    		if(change==1)
    		{	
    			while((n->id) <= check)
    			{					
    				if((strcmp(n->arrive,arrive)==0)&&(strcmp(change_station,n->depart)==0)&&(n->arrive_time<=arrival)&&((arrival-200)<(n->arrive_time)))
    				{
    					wait_time=duration(second_node->arrive_time,n->depart_time);
    					if((5<=wait_time)&&(wait_time<=60))
    					{
    						time=duration(second_node->depart_time, n->arrive_time);
    						printf("\nDepart: %s at %.2d:%.2d\n",depart,second_node->depart_time/100,second_node->depart_time%100);
    						printf("Arrive: %s at %.2d:%.2d\n",arrive,n->arrive_time/100,n->arrive_time%100);
    						printf("Change at: %s\n",change_station);
    						printf("Duration: %.2d:%.2d\nWait time at %s: %.2d minutes\n",time/60,time%60, change_station,wait_time);
    						indirect_value=1;
    					}
    				}
    				
    				if((n->next) != NULL)
    					n=n->next;
    				else
    					break;
    			}
    		}
    		n=head;
    		loops++;
    		
    		if((second_node->next) != NULL)
    			second_node=second_node->next;
    		else
    			break;
    			
    		change=0;
    	}
    	
    	if(indirect_value==0)
    		printf("None\n");
    	
    	return 0;
    }
    
    int check_station(char station[25], struct node *n, int check)
    {
    	int real_station=0;
    	
    	while((n->id)<=(check))
    	{	
    		if((strcmp(station,n->depart) == 0) || (strcmp(station,n->arrive) == 0))
    			real_station=1;
    											
    		if((n->next) != NULL)
    			n=n->next;
    		else
    			break;
    	}
    	
    	if(real_station==0)
    			printf("THE STATION ENTERED '%s' IS NOT A VALID STATION\n",station);
    	
    	return real_station;
    }
    
    int duration(int timeA, int timeB)
    {
    	int hoursA,hoursB,minsA,minsB,timeA_mins,timeB_mins,diff_mins;
    
    	hoursA=timeA/100;
    	minsA=timeA-(hoursA*100);
    	timeA_mins=(hoursA*60)+(minsA);
    		
    	hoursB=timeB/100;
    	minsB=timeB-(hoursB*100);
    	timeB_mins=(hoursB*60)+(minsB);
    	
    	diff_mins=timeB_mins-timeA_mins;
    		
    	return diff_mins;
    }
    
    int deallocate(struct node *n, int check)
    {
    	struct node *n2;
    	int number;
    
    	for(number=1; number<=check; number++)
    	{
    		if(number==n->id)
    		{
    			n2=n;
    			n=n->next;
    			free(n2);
    			return 1;
    		}
    	}
    }
    
    int main(void)
    {
    	int arrival,c=0,d=0,start=0,check=0,real_station=0;
    	char arrive[20],depart[20],a[25],b[25];
    	FILE *ttimes;
    	struct node *n=NULL,*n_start=NULL,*n2=NULL, *n3=NULL;
    			
    	ttimes=fopen("times.txt","r");
    	if(ttimes == NULL)
    	{
    		printf("There was an error opening the train timetable\nNow exiting...\n");
    		return 1;
    	}
    			
    	while(fscanf(ttimes,"%s %s %d %d",a,b,&c,&d) != EOF)
    	{
    		check++;
    		
    		if(start == 1)
    		{	
    			n2=mknode(a,b,c,d, check);
    			n->next=n2;
    			n=n2;
    		}
    		
    		if(start == 0)
    		{	
    			n=mknode(a,b,c,d, check);
    			start=1;
    			n_start=n;
    		}	
    	}
    	
    	fclose(ttimes);
    	
    	while(real_station == 0)
    	{
    			printf("Enter the name of the station you will be departing from:\n");
    			scanf("%s",depart);
    			real_station=check_station(depart, n_start, check);
    	}
    	
    	real_station=0;
    	
    	while(real_station == 0)
    	{
    			printf("Enter the name of the station you will be arriving at:\n");
    			scanf("%s",arrive);
    			real_station=check_station(arrive, n_start, check);
    	}
    		
    	printf("Please enter the time (HHMM) at which you would like to arrive at %s:\n", arrive);
    	scanf("%d", &arrival);
    		
    	printf("\nUser wants to travel from %s to %s, to arrive at %d\n",depart,arrive,arrival);
    	
    	direct(depart, arrive, arrival, n_start, check);
    	indirect(depart, arrive, arrival, n_start, check);
    	deallocate(&n_start, check);
    			
    	printf("\n");			
    
    	return 0;
    }
    i have left in my original deallocate function. there is an input file, but i know that this part of the code is correct, so hopefully some sense can still be made of this

    its very long i know...but if anyone has any hints still, id be very grateful

    thank you all so much

  8. #8
    Registered User
    Join Date
    Jan 2006
    Location
    Berkeley, Ca
    Posts
    195
    Okay, I need to drag my butt into work, but the method I used uses temp nodes.
    Temp points to phead. phead points to next. I then free the temp node. The reason for this is because if the temp node wasn't there and phead->next was NULL, free() would do a segmentation fault because it was passed NULL. If phead->next was after free(), this would be undefined behavior.

    Maybe someone else can explain this better than me.

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    12
    ok, i understand that function...i think.
    i have tried it, and it compiles and runs through the function but i dont think it is deallocating the memory.
    i have used the code from cdalten like this:
    Code:
    void deallocate(struct node *phead)
    {
    	struct node *temp;
    	
    	while(phead != NULL)
    	{
    		
    		temp = phead;
    		phead = phead->next;
    		printf("+-+%d+-+\n",temp->arrive_time);
    		free(temp);
    		printf("*-*%d*-*\n",temp->arrive_time);
    	}
    }
    if the dellocation process id working, should the second printf be a blank space rather than a time?when i run the program, the times are printed, but both are the same
    eg:
    +-+0932+-+
    *-*0932*-*
    +-+1009+-+
    *-*1009*-*
    etc etc

    thank you for your time

  10. #10
    Registered User wintellect's Avatar
    Join Date
    Mar 2006
    Posts
    24
    free(3) returns memory space allocated by malloc(3) and the like back to the OS, this does NOT mean it blanks out the memory.

    What you're reading is the contents of the memory location pointed to by temp which is nolonger allocated to your program. It just so happens to hold the same data in it from its last use - given enough time this data will eventually be overwritten or used by something else.

  11. #11
    Registered User
    Join Date
    Apr 2006
    Posts
    12
    oh ok .. so as the function is now, if ive understood you correctly, the memory allocated to the node is cleared?
    so, is there any other way to check the memory is deallocated or is it down to faith in the program?

    many thanks

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,752
    > so, is there any other way to check the memory is deallocated
    If you called free(), then it's gone.

    As wintellect pointed out, the bytes are still there, probably containing what you last stored there, but you certainly can't rely on the memory containing anything in particular. As with a lot of these things, "seems to work" is only half the battle.

    For example, some debug versions of memory manangement
    - fill the memory you just deallocated with a magic pattern to indicate the memory has been freed.
    - make the memory inaccessible to the program (causes a segfault)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    Registered User
    Join Date
    Apr 2006
    Posts
    12

    Wink

    Thank you all for your help

  14. #14
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71

    Lightbulb

    Another idéa is to use a memory pool!
    Allocate memory pool(s) with an arbitary size with malloc( ), etc. Then you get memory objects from a pool with your own allocate( ) function. When it's curtains for the app you just free( ) your pool(s) of memory. Google on!
    Bobby Fischer Live Radio Interviews http://home.att.ne.jp/moon/fischer/

  15. #15
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    free() would do a segmentation fault because it was passed NULL
    free() will simply do nothing when passed a NULL, it won't crash anything.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  2. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM
  3. Resource ICONs
    By gbaker in forum Windows Programming
    Replies: 4
    Last Post: 12-15-2003, 07:18 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21