Thread: Duplicating value of pointer to linked list

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    19

    Duplicating value of pointer to linked list

    I am trying to extract the head from a linked list (and also the tail, but that part works) with the following function:
    Code:
    void Remove (myllist *list){ //remove the head and return the removed node and the rest of the list
         myllist * head, * tail;
         int i;
         
         //get the head
         head = list;
         head->link = NULL;
         //check list
         printf("\nPrinting list\n");
         printList(list);
         
         //print the results
         printf("\nRemoved Node:\n");
         printList(head);
         
         //get the tail
         tail = list->link;
         //check list
         printf("\nPrinting list\n");
         printList(list);
         
         //print the results
         printf("\nTail of list:\n");
         printList(tail);
         
         printf("\nReturning to main.");
         return;
         }
    myllist is:

    Code:
    typedef struct myllist
    {
            int info;
            struct myllist * link;
    } myllist;
    The problem is that when I remove the tail from the list to get the head I am accidentally modifying the original list. I think this line is just creating a new pointer to the same information instead of copying the information into a new list:
    Code:
    head = list;
    How can I change it so that I can modify head without changing list?

    Thanks!

    The entire program is below if you need it.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct myllist
    {
            int info;
            struct myllist * link;
    } myllist;
    
    void GetNewNode (int newInfo, myllist * pNode);
    void disposeOfNode(myllist *change, myllist *remove);
    void Remove (myllist *list);
    void printList (myllist *list);
    
    main(){
           //setup nodes
           myllist * pNode;
           pNode = (myllist *) malloc(sizeof(*pNode));
           GetNewNode(4, pNode);
           
           myllist * pNode2;
           pNode2 = (myllist *) malloc(sizeof(*pNode));
           GetNewNode(5, pNode2);
           
           myllist * pNode3;
           pNode3 = (myllist *) malloc(sizeof(*pNode));
           GetNewNode(6, pNode3);
           
           //link nodes together
           pNode->link = pNode2;
           pNode2->link = pNode3;
           
           //print list
           printf("Old List:\n");
           myllist * tmp;
           tmp = pNode;
           while(tmp->link != NULL){
                           printf("%d", tmp->info);
                           tmp = tmp->link;
                           }
           printf("%d", tmp->info);
           
           //do stuff to list
           
           Remove(pNode);
           
           //print new list
           printf("\nNew List:\n");
           printList(pNode);
           
           //end
           getchar();
    }
    
    void disposeOfNode(myllist *change, myllist *remove){
         change->link = remove->link;
         free(remove);
         return;
         }
    
    void GetNewNode (int newInfo, myllist * pNode){
          /*myllist * pNode;
          pNode = (myllist *) malloc(sizeof(*pNode));*/
          if(pNode == NULL){
                   printf("error: malloc failed");
                   }else{
                         pNode->info = newInfo;
                         pNode->link = NULL;
                         }
          return;
    }
    
    void printList (myllist *list){
         myllist * tmp;
           tmp = list;
           while(tmp != NULL){
                           printf("%d", tmp->info);
                           tmp = tmp->link;
                           }
           }
           
    void Remove (myllist *list){ //remove the head and return the removed node and the rest of the list
         myllist * head, * tail;
         int i;
         
         //get the head
         head = list;
         head->link = NULL;
         //check list
         printf("\nPrinting list\n");
         printList(list);
         
         //print the results
         printf("\nRemoved Node:\n");
         printList(head);
         
         //get the tail
         tail = list->link;
         //check list
         printf("\nPrinting list\n");
         printList(list);
         
         //print the results
         printf("\nTail of list:\n");
         printList(tail);
         
         printf("\nReturning to main.");
         return;
         }

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    1
    Are you sure you are extracting the tail? tail = list->link would not work since list->link = NULL. In this case list and head references the same memory address, so you are effectively assigning NULL to head->link. As far as not modifying the original list - I would allocate space for a new list and do a "deep" copy.

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    19
    Sorry, could you give me sme more specifics, I am new to this. Thanks!

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    First, your comments are confusing. Do you want Remove() to be a modifying function or non-modifying function for your list? You say you want it to remove the head and return the list to main, but you are not returning anything.

    Then, look at the red line of code:

    Code:
    void Remove (myllist *list){ //remove the head and return the removed node and the rest of the list
         myllist * head, * tail;
         int i;
         
         //get the head
         head = list;
         head->link = NULL;
         //check list
         printf("\nPrinting list\n");
         printList(list);
         
         //print the results
         printf("\nRemoved Node:\n");
         printList(head);
         
         //get the tail
         tail = list->link;
         //check list
         printf("\nPrinting list\n");
         printList(list);
         
         //print the results
         printf("\nTail of list:\n");
         printList(tail);
         
         printf("\nReturning to main.");
         return;
         }
    What it is doing is removing the forward pointer from the head, and thus truncating the whole list to leave just the first node. That's why 4 is the only node reported in your printList.

    One you fix that, you'll have more to fix.

    Todd

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I think you've got all the right steps in there, somewhere, you just need to do them in the right order.

    You need to set tail to point to the tail of the list before you chop head off the list with the line in red above. And then, if you want the list to be headless afterwards, you need to set list=tail.

  6. #6
    Registered User
    Join Date
    Jan 2008
    Posts
    19
    I don't want Return to modify the original list. I guess instead of saying "return" I should have said "print".

    tabstop - The problem with doing it that way is that it modifies the origional list. Sorry if I was not clear about that.

    EDIT - I think my question comes down to this:

    How do I take a pointer (list) and give another pointer (head) the data from the the original pointer (list) such that modifying head does nothing to list?

    I know its a beginner question, but I am new to this so please explain it so I can understand. Thanks!
    Last edited by zephyrcat; 01-21-2008 at 08:58 AM. Reason: clarification

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    You don't have a function called Return. You have a function called Remove and you don't want it to modify (or remove something) from the original list?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    My astonishment matches anon's. Are you trying to modify someone else's remove function to do what you want, or what?

    Anyway, to print the head of the list only, what's wrong with
    Code:
    printf("%d", head->info); /* ? */
    If you had written a PrintNode helper function for your PrintList function like you should have , we wouldn't have gotten into this jam in the first place.

  9. #9
    Registered User
    Join Date
    Jan 2008
    Posts
    19
    My astonishment matches anon's. Are you trying to modify someone else's remove function to do what you want, or what?

    No, I am new to C.

    Sorry I guess I needed to be a lot clearer. I do want to have the head and the tail is their own lists so I could easily modify the program to return those lists, but for now in order to test the program, I am just printing the lists. That is why I don't want to just use a printf statement.

    Thanks!

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So, this is what we've got so far: (1) the original list must not be messed with; (2) we need a new list for the head; (3) we need a new list for the tail.

    Then, for instance, to do (1)+(2) we need to do something like this:
    1. Create a copy of the first node in list (this involves malloc'ing a new node, and copying the info from list to the new node)
    2. Set head to point at this copy.
    3. Since there's no rest-of-the-list here, set head->link to NULL.

    Doing (1)+(3) should be similar.

  11. #11
    Registered User
    Join Date
    Jan 2008
    Posts
    19
    Thank you! My program works now!

    Just out of curiosity and in case I have to do something similar again, how could you do the same thing except by creating a copy of the origional list and than setting link to NULL?

    Thanks so much for all the help!

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by zephyrcat View Post
    Thank you! My program works now!

    Just out of curiosity and in case I have to do something similar again, how could you do the same thing except by creating a copy of the origional list and than setting link to NULL?

    Thanks so much for all the help!
    I don't know what you're asking. Are you asking whether "creating a copy of the original list and then setting link to NULL" would also do what you want? If so, then not really -- the rest of the list will become a memory leak. If you mean "make a copy of the pointer to the list and then setting link to NULL", the answer is no, since if the pointers point to the same place, there's only one list.

  13. #13
    Registered User
    Join Date
    Jan 2008
    Posts
    19
    I would like to know how to copy a list so I end up with two separate lists that have the same information in them so that I can modify one without modifying the other.

    Thanks!

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    To copy a list, you need to make copies of all the nodes, transfer the data, and set the links.

    Normally people have a function that adds a node to a list (either at the end or in sorted order or at the beginning or ... wherever). You could use that, if you had one, to (1) walk through one list and (2) add those values to the new list.

  15. #15
    Registered User
    Join Date
    Jan 2008
    Posts
    19
    Alright, thanks!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need urgent help in linked list
    By Cassandra in forum C++ Programming
    Replies: 4
    Last Post: 03-12-2009, 07:47 PM
  2. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  3. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  4. Linked list probs
    By mouse163 in forum C++ Programming
    Replies: 5
    Last Post: 02-19-2005, 05:41 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM