linked list node removal using 'free'

This is a discussion on linked list node removal using 'free' within the C Programming forums, part of the General Programming Boards category; I created a circular linked list in which I successfully manage to skip a specific node at a time(denoted 'candidate' ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    2

    linked list node removal using 'free'

    I created a circular linked list in which I successfully manage to skip a specific node at a time(denoted 'candidate' in the code) , however I couldn't remove the requested node's allocated memory using 'free' procedure.Please see the below code(I also attached the C file for your convenience).
    Your help is much appreciated!
    Thanks!! Ron.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    typedef struct singleNode *nodePtr ;
    struct singleNode
    {
    short int val ;
    nodePtr next ; 
    };
    short int listLength(nodePtr);
    void printCList(nodePtr); 
    void main(){
     nodePtr member, Head, tmp=NULL, candidate=NULL;
     short int len=0,i,ind,j, LIST_SIZE=0,survivors;
        printf("Please define the list size,integer>=1\n");
     scanf("%d",&LIST_SIZE);
     for (i=1;i<=LIST_SIZE;i++){  // Building a regular linked list
      member = (nodePtr) malloc(sizeof(struct singleNode)) ;
      member->val = i ;                                           
      member->next = NULL ;
      if ( i == 1 ){ 
       tmp = member ;
       Head = member ;
      }
      else{ 
       tmp->next = member;
       tmp = tmp->next ;  
      }
     } 
     member->next = Head; // Turning the list into cirular one
     tmp = Head;
     printf("\n\nThe linked list: ");
     printCList(tmp);
     printf("Please enter the 'Every which location' and the number of survivors:m k\n");
     scanf("%d %d", &ind, &survivors);
     printf("(m=%d,k=%d)",ind, survivors);
     for (j=1;listLength(tmp)>=survivors;tmp=tmp->next,j++){  
      if (! (j%(ind-1)) ){
       candidate=tmp; 
       candidate->next=candidate->next->next; // skipping every m'th location
       //free(candidate); // ---> doesn't work 
      }
      if (listLength(tmp)==survivors){
        printf("\n\n The %3d survivors are located at places:\n", survivors);
        printCList(tmp);
        break;
      }
     }
    }//main
    void printCList(nodePtr temp){ // printing a circular linked list
        nodePtr head=temp;
     printf("%2d ",head->val);
        temp=temp->next;
     while(temp!=head){  
       printf("%2d ",temp->val);
       temp = temp->next;
     }
        printf("\n\n");
    }
    short int listLength(nodePtr pivot){
     short int k;
     nodePtr ptr;
     for (ptr=pivot,k=1;ptr->next!=pivot;ptr=ptr->next,++k); 
     return k;
    }
    Attached Files Attached Files

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    When you free candidate, you're freeing the same thing that tmp points to, as they both point to the same thing. You then try to do tmp = tmp->next; which tries to access deleted memory.
    You need to move ahead to tmp->next before you delete tmp. This means you need to rethink how that loop is structured. If you can't get it sorted from that description someone will help you out again after you post back.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,495
    It looks like your algorithm sets candidate to the node just before the one you want to remove. That's why you do candidate->next = candidate->next->next. You're basically making the list "skip over" whatever node candidate->next points to. You should fix the pointers using temp, and make candidate the node to delete:
    Code:
            if (! (j%(ind-1)) ){
                candidate=tmp->next;  // candidate is the node to skip/delete
                tmp->next = tmp->next->next; // skipping every m'th location
                free(candidate); // now it should work
            }
    Also, it's int main(void) and return an int when you're done, usually 0 for success. Read this link and this link.

  4. #4
    Registered User
    Join Date
    Nov 2011
    Posts
    2
    It makes sense and works very well. Btw I do agree with anduril462 regarding the convention about using int main(void).
    Thanks!!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 11-04-2010, 01:18 PM
  2. Replies: 0
    Last Post: 09-16-2008, 05:04 AM
  3. traversing a linked list with a node and list class
    By brianptodd in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 11:57 AM
  4. Removal on Linked List
    By s0ul2squeeze in forum C++ Programming
    Replies: 4
    Last Post: 03-28-2002, 03:38 PM
  5. Replies: 5
    Last Post: 10-04-2001, 03:42 PM

Tags for this Thread


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