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 */

---

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

>> 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.

Quote:

---

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

Quote:

---

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

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.

>> 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.