Thread: linked list - basic concept.

  1. #1
    Registered User Vber's Avatar
    Join Date
    Nov 2002
    Posts
    807

    linked list - basic concept.

    Hello, I started this week to deal a little bit with linked lists, I did a simple example, I'm not sure the way I did it is correct, maybe I'm missing something, here's the code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node {
    	int data;
    	struct node *next; //wohhaaa... a linked list :)
    };
    
    void add( struct node **head, int data ) {
    	struct node *tmp = malloc( sizeof ( struct node ) );
    	
    	tmp->data = data;
    	tmp->next = *head;
    
    	*head = tmp;
    }
    
    void print( struct node *head ) {
    	struct node *current = head;
    	
    	while( current ) {
    		printf( "data: %d\n", current->data );
    		current = current->next;
    	}
    }
    
    void collect( struct node *head ) {
    	struct node *current = head;
    	
    	while(current ) {
    		free( current );
    		current = current->next;
    	}
    }
    
    int main( void ) {
    	struct node *head = NULL;
    
    	add( &head, 4 );
    	add( &head, 3 );
    	add( &head, 2 );
    
    	print( head );
    	collect( head );
    	return 0;
    }
    My big question is, my collect() function really works? it's correct, or I'm forgetting to free something?

  2. #2
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    my collect() function really works?
    Nope, it's buggy and very dangerous. Why?
    Code:
    free( current );
    current = current->next;
    What makes you think that you can access a pointer that's already been freed? Just because it was freed the line before doesn't mean the memory hasn't been reused. A better way is to save the next pointer, then free the current pointer, then set the current pointer to the saved next pointer
    Code:
    void collect( struct node *head ) {
        struct node *current = head;
        struct node *forward;
    
        while(current ) {
            forward = current->next;
            free( current );
            current = forward;
        }
    }
    p.s. What the alphabet would look like without q and r.

  3. #3
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    no its not correct. look
    Code:
    void collect( struct node *head ) {
    	struct node *current = head;
    	
    	while(current ) {
    		free( current ); // current is dead after this call
    		current = current->next;// but you access it here.
    	}
    }
    oops beaten
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  4. #4
    Registered User Vber's Avatar
    Join Date
    Nov 2002
    Posts
    807
    Ok, thanks for helping
    Any other comments about my code? I'm still missing something?

  5. #5
    Registered User
    Join Date
    Jan 2003
    Posts
    4
    I have altered your collect function, you should find the nodes are deleted correctly now

    Code:
    void collect( struct node *head ) {
    	struct node *current = head;
    	struct node *p;
    
    
    	while(current){
    		p = current->next;
    		free( current );
    		current = p;
    
    		//check if node really is freed
    		printf("\n\n Deleting node\n");
    		print(current);
    
    	}
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  5. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM