Linked List "Changed by itself"

This is a discussion on Linked List "Changed by itself" within the C Programming forums, part of the General Programming Boards category; A background to the source code: We build a linked list 1-2-3 We build a linked list 1-2-3-4-5 We use ...

  1. #1
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181

    Linked List "Changed by itself"

    A background to the source code:

    We build a linked list 1-2-3
    We build a linked list 1-2-3-4-5

    We use a function called ShuffleMerge that takes each node from both lists and alternates them. So mixing the above two lists gives:

    1-1-2-2-3-3-4-5

    See the code below:
    Code:
    # include <stdio.h>
    # include <assert.h>
    # include <stdlib.h>
    
    struct node {
        int data;
        struct node* next;
    };
    
    void PrintLinkedList (struct node* head) {
        if (head == NULL) {
            printf("Null List");
            return;
            }
        while (head -> next != NULL) {
            printf("%d ", head -> data);
            head = head -> next;
            }
        printf("%d", head -> data);
        return;
    }
    
    struct node* BuildOneTwoThree() {
        struct node* head = NULL;
        struct node* second = NULL;
        struct node* third = NULL;
        head = malloc (sizeof(struct node));
        second = malloc (sizeof(struct node));
        third = malloc (sizeof(struct node));
        head -> data = 1;
        head -> next = second;
        second -> data = 2;
        second -> next = third;
        third -> data = 3;
        third -> next = NULL;
        return (head);
    }
    
    struct node* BuildOneTwoThreeFourFive() {
        struct node* head = NULL;
        struct node* second = NULL;
        struct node* third = NULL;
        struct node* fourth = NULL;
        struct node* fifth = NULL;
        head = malloc (sizeof(struct node));
        second = malloc (sizeof(struct node));
        third = malloc (sizeof(struct node));
        fourth = malloc (sizeof(struct node));
        fifth = malloc (sizeof(struct node));
        head -> data = 1;
        head -> next = second;
        second -> data = 2;
        second -> next = third;
        third -> data = 3;
        third -> next = fourth;
        fourth -> data = 4;
        fourth -> next = fifth;
        fifth -> data = 5;
        fifth -> next = NULL;
        return (head);
    }
    
    void MoveNode (struct node** destRef, struct node** sourceRef) {
        if (*sourceRef == NULL)
            return;
        struct node* temp = *destRef;
        *destRef = *sourceRef;
        *sourceRef = (*sourceRef) -> next;
        (*destRef) -> next = temp;
    }
    
    struct node* ShuffleMerge(struct node* a, struct node* b) {
        struct node dummy;
        struct node* tail = &dummy;
        dummy.next = NULL;
        while (!(a == NULL && b == NULL)) {
            if (a != NULL) {
                MoveNode (&(tail -> next), &a);
                tail = tail -> next;
            }
            if (b != NULL) {
                MoveNode (&(tail -> next), &b);
                tail = tail -> next;
            }
        }
        //PrintLinkedList (a);      Just before its returned, a points to a NULL List, confirmed by printing it at this line
        return (dummy.next);
    }
    
    int main() {
        struct node* a = BuildOneTwoThree();
        struct node* b = BuildOneTwoThreeFourFive();
        PrintLinkedList (ShuffleMerge(a, b)); // Here the returned head pointer from the shuffle merge function is printed
        printf("\n");
        PrintLinkedList (a); // Heres the problem, when "a" exited the ShuffleMerge function, it was NULL as it should be. But when its printed here, it points to the shuffled linked list!
        getchar();
    }
    I got the programme to work no problem. But just as a matter of interest theres one anomoly which I cant explain and its the second last statement:
    "a" points to the returned shuffled list and not to NULL as it should!

  2. #2
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181
    I think itll take too long a time to get the actual code. The point I dont get focuses on TWO statements:
    Line 86 where we print a and it prints NULL
    Line 95 where the code imediately jumps to after line 86 and it all of a sudden prints 1-1-2-2-3-3-4-5 !
    And thats anomolous because just as it exited the shuffle merge function it was NULL and no operation whatsoever was performed on it. It obviously has something to do with the fact that a COPY of the pointer was passed to sufflemerge and not a pointer to the pointer, but I still cant make out what exactly. Answer is staring me in the face!

  3. #3
    Registered User
    Join Date
    Jun 2011
    Posts
    76
    a in ShuffleMerge and a in main are two different variables.
    a in Shuffelmerge is NULL a in main should have the value returned by BuildOneTwoThree.

  4. #4
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181
    Quote Originally Posted by sparkomemphis View Post
    a in ShuffleMerge and a in main are two different variables.
    a in Shuffelmerge is NULL a in main should have the value returned by BuildOneTwoThree.
    Thats exactly what its doing but why? Shouldnt it stay NULL?

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,806
    No, "a" is local to the function ShuffleMerge, changes to "a" within the scope of the function only affect that local copy of "a" and not the one you passed into the function from main. If you want the "a" you pass into ShuffleMerge from main to be altered by the call, you'll need to pass in its address (a pointer-to-a-pointer to the struct like what you do with the MoveNode function) and alter how you access "a" within ShuffleMerge.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181
    Quote Originally Posted by hk_mp5kpdw View Post
    No, "a" is local to the function ShuffleMerge, changes to "a" within the scope of the function only affect that local copy of "a" and not the one you passed into the function from main. If you want the "a" you pass into ShuffleMerge from main to be altered by the call, you'll need to pass in its address (a pointer-to-a-pointer to the struct like what you do with the MoveNode function) and alter how you access "a" within ShuffleMerge.
    You are right about this, Mr Heckler & Koch!; I knew it had something to do with it all along. Problem is it seems so counter intuitive. Because although we are making a copy of the pointer, its still changing the same linked list. And thats why I thought even the copy's should be the same because its the same linked list. But I finally drew a memory diagram showing why one returns NULL and other points to the changed list:
    Name:  Mem Diag.JPG
Views: 193
Size:  51.8 KB

    The a in the callee points to NULL because it kept iterating down the linked list until it hit NULL. All the while the callers "a" was always pointing to the actual node "1" that got moved and conglomerated/shuffled with other nodes. Hence when it returned it was the final shuffled list.

    What frustrates me is that I knew playing with copies was tricky and yet still felt confused with this one. I guess its because its so counter intuitive especially to beginer's.
    Last edited by Vespasian; 05-15-2012 at 04:32 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list "lastin - first out"?
    By Shackdaddy836 in forum C Programming
    Replies: 7
    Last Post: 03-29-2011, 12:16 AM
  2. help with linked list for displaying "stack is full"
    By sujesh in forum C++ Programming
    Replies: 2
    Last Post: 11-23-2010, 11:18 AM
  3. Must be "linked list" lesson week
    By Dino in forum General Discussions
    Replies: 3
    Last Post: 02-19-2010, 05:20 PM
  4. please help i'm screwed "linked list"
    By jspri in forum C Programming
    Replies: 7
    Last Post: 10-17-2004, 09:18 PM
  5. recursivly "adding" a linked list
    By axon in forum C++ Programming
    Replies: 1
    Last Post: 10-19-2003, 08:01 PM

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