Thread: Delete and destroy in double linked lists

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    31

    Delete and destroy in double linked lists

    I have a problem using the functions delete (the header cell remains) and destroy in single and double linked lists. This is the code that I used for DLL:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "DLList.h"
    
    ListDT *deleteDList(ListDT *L)
    // deletes all the cells of the list L except the header cell; returns a pointer to header cell
    
    {
    
        NodeDT *p;
    
        while (L->first!= NULL)
          {
            p = L->first;
            L->first = L->first -> next;
            free( p );
          }
    
        L->last = NULL;
        return L;
    }
    
    void destroyDList(ListDT *L)
    // deletes all the cells of the list L including the header cell.
    
    
    {
        NodeDT *p;
        p = L->first;
        while (p != NULL)
          {
            p = L->first;
            L->first=L->first->next;
            free( p );
           }
       free (L);
    }
    What I did wrong?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Why do you believe you did something wrong? What is (is not) happening that shouldn't (should)?

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    31
    It's not working properly.
    For example, if in my list I have the numbers 4 2 10 if I use delete or destroy, but not both, the list will contain 10. If a used both the list will pe empty. But is not working for all the examples. free (p) doesn't work as I thought it will. If I add another number to the list, for example 3, and the list will be 4 2 10 3, the program runs for infinity and prints 4 2 10 10 10 10...
    But if I print the list before delete it prints correctly: 4 2 10 3

  4. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    31
    This the print function that I used:

    Code:
    void*printItem (void *pItem)
    
    {
    
    printf("%d ", pItem);
    
    }
    
    void printDList(ListDT *L)
    // prints the contents of all the cells on list L;
    // invokes the external printSItem to get a representation of the data stored at each node
    
    {
    
     if (L->first == NULL)
       error_message(2);
     else {
          NodeDT *p;
          p=L->first;
          while (p != NULL)
         	{
    	    	printItem(p->Item);
    	    	p = p->next;
    	    }
          }
    }

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Delia View Post
    It's not working properly.
    For example, if in my list I have the numbers 4 2 10 if I use delete or destroy, but not both, the list will contain 10. If a used both the list will pe empty. But is not working for all the examples. free (p) doesn't work as I thought it will. If I add another number to the list, for example 3, and the list will be 4 2 10 3, the program runs for infinity and prints 4 2 10 10 10 10...
    But if I print the list before delete it prints correctly: 4 2 10 3
    So wait: you deleted the list, then added a number, and the numbers came back? That means you're not using the return value of your delete function.

  6. #6
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Seems to be because of not setting next pointers to NULL after freeing the memory.
    Just because you free() it doesn't mean the values gets deleted, but accessing it after it's freed is a bad thing to do.

    edit:
    Just to clarify, this post is directed towards Delia, not tabstop. Managed to hit reply instead of quote

  7. #7
    Registered User
    Join Date
    Mar 2010
    Posts
    31
    Quote Originally Posted by tabstop View Post
    So wait: you deleted the list, then added a number, and the numbers came back? That means you're not using the return value of your delete function.

    No if I add a number before using delete.
    Nevermind. I modified it a little and it runs ok. Except free (L). This is why my program runs at infinity. If I put in comment //free (L) and I use only destroy it is running like delete. How can I delete a header cell otherwise?

  8. #8
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by Delia View Post
    I have a problem using the functions delete (the header cell remains) and destroy in single and double linked lists. This is the code that I used for DLL:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "DLList.h"
    
    ListDT *deleteDList(ListDT *L)
    // deletes all the cells of the list L except the header cell; returns a pointer to header cell
    
    {
    
        NodeDT *p;
    
        while (L->first!= NULL)
          {
            p = L->first;
            L->first = L->first -> next;
            free( p );
          }
    
        L->last = NULL;
        return L;
    }
    
    void destroyDList(ListDT *L)
    // deletes all the cells of the list L including the header cell.
    
    
    {
        NodeDT *p;
        p = L->first;
        while (p != NULL)
          {
            p = L->first;
            L->first=L->first->next;
            free( p );
           }
       free (L);
    }
    What I did wrong?
    When you say:

    L->first = L->first->next;

    How do you know L->first->next is not NULL?

  9. #9
    Registered User
    Join Date
    Mar 2010
    Posts
    31
    Quote Originally Posted by claudiu View Post
    When you say:

    L->first = L->first->next;

    How do you know L->first->next is not NULL?
    I modified and put
    Code:
     while (L->first != NULL)
    instead

  10. #10
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by Delia View Post
    I modified and put
    Code:
     while (L->first != NULL)
    instead
    Well L->first may not be NULL but the NEXT element could. Try going through your code using an example of a list containing only the head node.

    You do:

    L->first = L->first->next (WHICH IS NULL)

    and then,

    free(p) which is free(l->first) which is free(L->first->next) which is free(NULL); BOOOM

  11. #11
    Registered User
    Join Date
    Mar 2010
    Posts
    31
    Quote Originally Posted by claudiu View Post
    Well L->first may not be NULL but the NEXT element could. Try going through your code using an example of a list containing only the head node.

    You do:

    L->first = L->first->next (WHICH IS NULL)

    and then,

    free(p) which is free(l->first) which is free(L->first->next) which is free(NULL); BOOOM
    But my problem isn't there I think. free (p) is in fact free (L->first) in the step 1. Only in the step 2 it will be (L->first->next) which is NULL. But step 2 doesn't take place because in step one L->first is NULL and the while stops. I'm thinking it all wrong?

    The program works properly except free (L);

  12. #12
    Registered User
    Join Date
    Jan 2010
    Posts
    34
    L point to first head right ? u must freed already freed memory , could you post struct.h ?

  13. #13
    Registered User
    Join Date
    Mar 2010
    Posts
    31
    Quote Originally Posted by kira_coder View Post
    L point to first head right ? u must freed already freed memory , could you post struct.h ?
    Code:
    typedef struct nodeD
    {
    void *Item; // pointer to satellite data
    struct nodeD *next; // pointer to next cell
    struct nodeD *prev; // pointer to previous cell
    } NodeDT; // type of cells on the doubly linked list
    
    typedef struct
    {
    int size; // number of cells currently on list
    NodeDT *first; // pointer to first cell on list
    NodeDT *last; // pointer to first cell on list
    } ListDT; // type of header cell of the doubly linked list

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by claudiu View Post
    Well L->first may not be NULL but the NEXT element could. Try going through your code using an example of a list containing only the head node.

    You do:

    L->first = L->first->next (WHICH IS NULL)

    and then,

    free(p) which is free(l->first) which is free(L->first->next) which is free(NULL); BOOOM
    free(NULL) is perfectly ordinary and not at all a problem. The only possible problem here is if L->first is NULL, in which case you are trying to access a null pointer when you do L->first->next.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I'm not sure, at this point in time, what errors you are seeing or when. If you free(L), make sure that the pointer you are dealing with came from malloc. Looking at your struct, if you did something like
    Code:
    ListDT myList;
    .
    .
    .
    destroy(&myList);
    well, that's a large quantity of pain. If you are using pointers from malloc, then after you return from your destroy, you should set your pointer to NULL to keep you from trying to use that memory again, and be sure the next time you try to use the list that you malloc again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked lists and new/delete?
    By Neo1 in forum C++ Programming
    Replies: 12
    Last Post: 08-11-2007, 10:17 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Problem need help
    By Srpurdy in forum C++ Programming
    Replies: 1
    Last Post: 07-24-2002, 12:45 PM
  5. eof in fstream & singly linked lists
    By mazo in forum C++ Programming
    Replies: 3
    Last Post: 06-03-2002, 09:50 AM