Linked list, is this correct?

This is a discussion on Linked list, is this correct? within the C Programming forums, part of the General Programming Boards category; My main area of concern is when I'm freeing the allocated memory (in bold). I don't know if I'm going ...

  1. #1
    Registered User
    Join Date
    Jul 2003
    Posts
    85

    Question Linked list, is this correct?

    My main area of concern is when I'm freeing the allocated memory (in bold). I don't know if I'm going about this properly. If you see any other corrections, I'd appreciate those as well. Thank you very much

    Code:
    /*   File:  linked-lists.c
     *   Date:  November 12, 2003
     *   Info:  Example of linked lists. There's no better way of
     *          learning pointers than learning linked lists.
     * Author:  Sean
     *
     * References:
     *    http://cslibrary.stanford.edu/103/LinkedListBasics.pdf
     */
    
    #include <stdio.h>
    #include <stdlib.h> 
    
    struct node* initialize_list(void);
    int add_node(struct node** headptr, int value);
    int del_node(struct node** headptr);
    int del_list(struct node* head);
    int count_list(struct node* head);
    int display_list(struct node* head);
    
    struct node {
        int             data;
        struct node*    next;
    };
    
    int main(void)
    {
        struct node* head;
        int count;
        
        head = initialize_list();
    
        add_node(&head,8);
        add_node(&head,2);
        add_node(&head,5);    
        add_node(&head,7);
        
        count = count_list(head);
        printf("Number of nodes in list: %d\n",count);
        puts("The list currently contains: ");
        display_list(head);
        
        del_node(&head);
        puts("After deleting a node\n");
        count = count_list(head);
        printf("Number of nodes in list: %d\n",count);
        puts("The list currently contains: ");
        display_list(head);
    
        del_list(head); /* free the allocated memory (delete list) */
        
        return 0;
    }
    
    
    /* initializes our list. */
    struct node* initialize_list(void)
    {
        struct node* head = NULL;
        return head;
    }
    
    /* adds value to a node. if head node is empty, */
    /* the value is added there, if not, it's added */
    /* to a new node before the head pointer and    */
    /* that node becomes the new head pointer.      */
    int add_node(struct node** headptr, int value)
    {
        struct node* tmp = NULL;
       
        tmp = malloc(sizeof(struct node));
        if( tmp == NULL )
            return -1; /* memory allocation failed */
        else {
            tmp->data = value;
            if( *headptr == NULL ) { /* if the head pointer is empty */
                *headptr = tmp;
                return 0;
            }
            tmp->next = *headptr;
            *headptr = tmp;
        }
        return 0;        
    }
    
    
    /* deletes the head node. we pass a pointer to   */
    /* our head pointer in this case because we need */
    /* to alter our head pointer.                    */
    int del_node(struct node** headptr)
    {
        struct node* tmp;
      
        if( *headptr == NULL )
            return -1; /* nothing to delete */
        else {
            tmp = *headptr;
            *headptr = (*headptr)->next;
            free(tmp);
        } 
        return 0;
    }
    
    /* deletes the entire list. frees up all the     */
    /* allocated memory. uses the del_node function. */
    int del_list(struct node* head)
    {
        struct node* cur = head;
    
        while( cur != NULL ) {
            del_node(&cur);
        }
        return 0;
    } 
    
    /* counts the number of nodes in list and returns it */
    int count_list(struct node* head)
    {
        struct node* cur = head;
        int count;
        
        /* goes through list */
        for( count = 0; cur != NULL; cur = cur->next)
            count++;
            
        return count;
    }
    
    /* displays the contents of the list */
    int display_list(struct node* head)
    {
        struct node* cur = head;
       
        if( cur == NULL ) {
            printf("The list is empty!");
            return 0;
        }
        
        while( cur != NULL ) {
            printf("%d\n",cur->data);
            cur = cur->next;
        }
        return 0;
    }
    
    /* EOF */

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,646
    del_node() and del_list() are fine.
    The problem is in add_node() when *headptr == NULL. You assign tmp to *headptr but tmp->next is uninitialized.

    gg

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,655
    >> tmp->next = *headptr;

    Here, you are inserting the new node *in front* the head (meaning you'll never see it again). You need to traverse to the end of the list, and point the last node's next ptr to the new node. The new node must have it's next ptr set to NULL.

    Then the very next line goes:

    >> *headptr = tmp;

    That's a memory leak. headptr now points to temp, and the memory headptr *was* pointing to is lost forever (so to speak).

    Everything else is OK.

  4. #4
    Registered User
    Join Date
    Jul 2003
    Posts
    85
    Originally posted by Codeplug
    del_node() and del_list() are fine.
    The problem is in add_node() when *headptr == NULL. You assign tmp to *headptr but tmp->next is uninitialized.

    gg
    in that case, can i just set tmp->next to NULL? when the headptr is NULL, i'm assuming that the list is empty, so tmp->next wouldn't have to be initialized? thanks

    Originally posted by Sebastiani
    >> tmp->next = *headptr;

    Here, you are inserting the new node *in front* the head (meaning you'll never see it again). You need to traverse to the end of the list, and point the last node's next ptr to the new node. The new node must have it's next ptr set to NULL.

    Then the very next line goes:

    >> *headptr = tmp;

    That's a memory leak. headptr now points to temp, and the memory headptr *was* pointing to is lost forever (so to speak).

    Everything else is OK.
    when i'm inserting the new node *in front* of the head pointer, i thought i was just moving the old headptr to the the new headptr's next. first i assign the current headptr to the tmp->next, then i assign the tmp to headptr as the new head pointer. so i don't see how it'll be lost or why i would have to traverse to the end..

    Code:
    tmp->data = value;
            if( *headptr == NULL ) { /* if the head pointer is empty */
                *headptr = tmp;
                return 0;
    in that bit, headptr doesn't actually have any memory allocated to it, correct? so assigning tmp (which points to allocated memory) to headptr just gives headptr allocated memory to point to, right?

    thanks for all of your guys' help

    scrappy

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You really don't even need to check for NULL, It's pointless to do so.
    Code:
    int add_node(struct node** headptr, int value)
    {
        struct node* tmp = NULL;
       
        tmp = malloc(sizeof(struct node));
        if( tmp == NULL )
            return -1; /* memory allocation failed */
        else {
            tmp->data = value;
            tmp->next = *headptr;
            *headptr = tmp;
        }
        return 0;        
    }
    There is no need to test for NULL, because you're just going to make the new node the first node anyway. If it is NULL, it simply makes "head->next" equal NULL, and head be the new node. That's what you want anyway, so there is no point in even testing to see if it is null.

    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,655
    >> i thought i was just moving the old headptr to the the new headptr's next.

    My mistake. I see what you were doing now.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  3. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 06:29 PM

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