Linked List help

This is a discussion on Linked List help within the C Programming forums, part of the General Programming Boards category; I'm just learning Linked Lists in C and made a quick program that I'm having problems getting to work. Here's ...

  1. #1
    Registered User
    Join Date
    Jan 2003
    Posts
    5

    Linked List help

    I'm just learning Linked Lists in C and made a quick program that I'm having problems getting to work. Here's the code:

    Code:
    #include <stdio.h>
    #define NAME_LENGTH 100
    #define NODES_AT_ONCE 1000
    
    struct node 
    { 
    	char name[NAME_LENGTH]; 
    	struct node *next; 
    };
    
    typedef struct node Node;
    
    Node *freeList = NULL;
    
    void freeNode( Node *p )
    {
    	p -> next = freeList; 
    	freeList = p;
    }
    
    Node* newNode( char *s, Node *next )
    {
    	Node *r = freeList;
    	int i;
    	
    	// if no space left in list, get space for Nodes
    	if( freeList == NULL )
    	{
    	   freeList = ( Node* )calloc( NODES_AT_ONCE, sizeof( Node ) );
    	   for( i = NODES_AT_ONCE - 1; i >= 0; i-- )
    	   {
    		freeList[i].next = r;
    		r = &freeList[i];
    	   }
    	}
    
    	freeList = r -> next;
    	strncpy( r -> name, s, NAME_LENGTH );
    	r -> next = next;
    }
    
    void output( Node *head )
    {
    	Node *p;
    	for( p = head; p != NULL; p = p -> next )
    	   printf( "%s", p -> name );
    	printf( "\n" );
    }
    
    Node* reverseList( Node *head )
    {
    	Node *p, *rev = NULL;
    	for( p = head; p != NULL; p = p -> next )
    	   rev = newNode( p -> name, rev );
    	return rev;
    }
    
    int main()
    {
    	Node *ghead, *bhead, *p, *temp, *rev;
    	
    	ghead = newNode( "Amy", NULL );
    	output( ghead );
    	bhead = newNode( "Kirk", NULL );
    	output ( bhead );
    
    	ghead -> next = newNode("Tiff", ghead -> next );
                    output( ghead );
    	bhead -> next = newNode("Merl", bhead -> next );
    	output ( bhead );
    		
    	rev = reverseList( bhead );
    	output( rev );
    
    	return 0;
    }
    I planned on allowing users to pass files or to manually type in the names, but until I get it working, I hardcoded my inputs.
    Currently, it prints the following output:

    Amy
    Kirk
    Segmentation Fault

    I'm pretty sure the error comes in this piece of code and have tried altering it a few times, but can't get it to work. Any suggestions?
    Code:
    ghead -> next = newNode("Tiff", ghead -> next );
    output( ghead );
    bhead -> next = newNode("Merl", bhead -> next );
    output ( bhead );

  2. #2
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    A problem is in the newNode() function. It does not return a pointer to Node. So bhead and ghead in function main() stay uninitialised.

    I really wonder what that freelist is doing in your code. It seems unnecessary to me.

    Code:
    Node* newNode( char *s)
    {
        Node *temp;
        
        // First try to allocate memory for a new node
        temp = malloc (sizeof (Node));
        if (NULL == temp)
        {
            printf ("newNode() could not allocate memory\n");
            return NULL;
        }
    
        // It succeeded, so initialise the new node
        strncpy (temp->name, s, NAME_LENGTH);
        temp->next = NULL;
    
        // Return pointer to new node
        return temp;
    }
    And then in your calling function you can have a call like this:

    Code:
    // A pointer pointing to the last node in the list
    Node *list_tail_ptr;
    
    // Try to add a new node to the list
    list_tail_ptr->next = newNode (name);
    
    if (NULL == list_tail_ptr->next)
    {
        // It failed
        printf ("Could not add new node to linked list\n");
    }
    else
    {
        // It succeeded, now replace the pointer to the last node in list
        list_tail_ptr = list_tail_ptr->next;
    }
    Hope this helps you a bit.

  3. #3
    Registered User
    Join Date
    Jan 2003
    Posts
    5
    Thanks for the help, completely missed the return r. Feel stupid for that one. As for freeList, I was told to make the list so it grow if need be. If it uses up the memory allocated for it, then that should increase the size so the list can store more. At least thats what I was told.

  4. #4
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    >If it uses up the memory allocated for it, then that should
    >increase the size so the list can store more. At least thats what
    >I was told.

    That is not a linked list, but an array of variable size. A linked list is in the beginning just a pointer to a node. During the life-time of the program, you add and remove nodes from the list. For each node you allocate memory.

    An array of variable size has a size in the beginning. When the memory is all used, you resize the memory so you can put new elements in it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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