Freeing Linked Lists

This is a discussion on Freeing Linked Lists within the C Programming forums, part of the General Programming Boards category; Greetings all, Im getting confused about linked lists and wonder if someone can clear it up for me. Say i ...

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

    Freeing Linked Lists

    Greetings all,

    Im getting confused about linked lists and wonder if someone can clear it up for me.

    Say i have a simple linked list structured like this :
    Code:
    typedef struct sockets SOCKETS;
    
    struct sockets {
     int state;
     int sock_id;
     struct socks* next;
     struct socks* prev;
    };
    Now a small function to populate this linked list with some inital data like :
    Code:
    struct sockets* populate()
    {
     struct sockets* head = NULL; 
     struct sockets* first = NULL;
     head = malloc(sizeof(struct sockets));
     first = malloc(sizeof(struct sockets));
    
     head->state=1;
     head->sock_id=5;
     head->next=first;
     head->prev=NULL;
    
     first->state=1;
     first->sock_id=6;
     first->next=NULL;
     first->prev=head;
    
     return head;
    }
    so in my main to create this list in memory it looks like :

    Code:
    int main(void)
    {
     SOCKETS *socks;
     socks = populate();
    }
    Ok so now I have my first node held in socks. Sorry for the simplicity of this btw as I could probably just cut to the chase but i need to make sure im doing everything as I should and make it clear what my question is in relation to how i have my lists.

    Ok now if i want to delete a node from that list ive always just looped through the list until i found the key like this :
    Code:
    void del_node(struct sockets* first_node, int sock_id)
    {
     struct sockets* current = first_node;
     struct sockets *tmp_next = NULL;
     struct sockets *tmp_previous = NULL;
     while(current != NULL) {
      if(current->sock_id == sock_id) {
       if(current->next == NULL) {
        tmp_previous = current->previous;
        tmp_previous->next = NULL;
       } else {
        tmp_previous = current->previous;
        tmp_next = current->next;
        tmp_next->previous=tmp_previous;
        tmp_previous->next=tmp_next;
       }
       free(current);
       break;
      }
      current = current->next;
     }
    }
    Ok i know that is a messy for deleting but its all I could come up with while testing. Anyway heres my question (at last!) as you can see in my delete node function im just free'ing the pointer yes ? and not actually freeing the data within the struct ? as after researching this on the web I found some code by someone like this :

    Code:
    free(head->data);     /* free mem within the list! */   
    free(head);
    So do i have to free up all the sections in the struct aswell ?
    Also ive read somewhere that after ive free a pointer its still there but has no memory allocated to it. So do i need to NULL it after I use it aswell ?

    If anyone can explainwith a little example id really appreciate it.

    Thanks.

    mrpickle

    ps. sorry for the long drawn out post !

  2. #2
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    So do i have to free up all the sections in the struct aswell ?
    Also ive read somewhere that after ive free a pointer its still there but has no memory allocated to it. So do i need to NULL it after I use it aswell ?
    You only free the data if you had to allocate the data via malloc or similar function. You are just using ints so its not necessary.

    After you free the pointer if you accidently dereference it there are a number of things that could happen and unfortunately your program won't always crash like you'd expect. So it's common practice to set the pointer to NULL after you free the memory so if you do dereference it by mistake you will surely get a crash.
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

  3. #3
    Registered User
    Join Date
    Jan 2003
    Posts
    21
    Thanks for reply.

    OK so technically the only thing im doing wrong is not setting the pointers to NULL after ive free'd them?

    Reason I ask is because I keep getting random segfaults with chunk_alloc errors reported by GDB in a MUD ive been writing.

    And even though I cant ever recreate the segfaults while running the code through Valgrind as it doesnt ever complain about any bad memory operations. So i thought it may have something to do with my pointers this also may be related to what you said about trying to access a dereferenced pointer.

    Ok well ill go through my code and make sure I NULL all the pointers I am finished with and pray for no more random seg faults

    Thanks

    mrpickle.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You really shouldn't be doing what you're doing. At least not the way you're doing it. What's the purpose of your dummy node? You don't need one. It's confusing code.

    Rather, it's not clear on its intent. Deleting nodes from a double linked list is very very easy.
    Code:
    int freesocket( int socketid, struct socket **list )
    {
        struct socket *node = NULL;
    
        for( node = *list; node; node = node->next )
            if( node->socketid == socketid )
            {
                if( node == *list )
                {
                    *list = node->next;
                }
                if( node->prev )
                    node->prev->next = node->next;
                if( node->next )
                    node->next->prev = node->prev;
    
                /*free anything dynamicly allocated inside 'node'*/
                /* now free 'node' itself */
                free( node );
    
                return 0;
            }
        return -1;
    }
    That's all there is to it. Very simple. Call the function like so:
    Code:
    struct socket * list;
    ...
    
    if( freesocket( socketid_to_delete, &list ) != 0 )
    {
        printf("error: socketid not found %d\n", socketid_to_delete );
    }
    Something like that. I am not sure I see the point of you creating two nodes in 'populate'. Personally, I'd create one function to return a newly allocated node with the socket value I need.

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

  5. #5
    Registered User
    Join Date
    Jan 2003
    Posts
    21
    quzah,

    yep i see my way is going all the way around the houses to do what your code makes very simple. I think when I tried to do it like you have, i had trouble getting my head around the use of this piece of code :

    node->prev->next

    so my way was just a poor workaround due to lack of knowledge. I "think" i know what it does but im still a little confused about it but ill try and figure it out.

    thanks

    mrpickle.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  2. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 10:32 PM
  3. freeing linked lists
    By lambs4 in forum C Programming
    Replies: 1
    Last Post: 03-27-2003, 05:14 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

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