linked list swap function

This is a discussion on linked list swap function within the C Programming forums, part of the General Programming Boards category; I'm not sure why the following swap function is not working. When i access the swap function in main i ...

  1. #1
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335

    linked list swap function

    I'm not sure why the following swap function is not working. When i access the swap function in main i pass it start and start->next

    so if i have

    A (start)
    B (start->next)

    i'm certain that's correct but i think it's my swap function that's the problem:

    in main :



    Code:
    
    charNode* swap(charNode *first, charNode *next)
    {
    
      charNode *newList = NULL; /* a reference to the new list that will be used to store the new order */
        first = next;  /* place next (i.e. B in first and (A) in next) */
        next = newList; /* update the list the order that next is in  */
        newList = first; /* update the list the order that first is in  */
        return newList; /* return a reference to the new list, which will be used by the print function */
    
    /* a while loop is not necessary in this case because it can be done in one go */

    here's how i'm calling it:

    Code:
       charNode *start = NULL;
       start = swap(start, start->next);
       printList(start, start);
    result:

    B
    C
    D


    seems as though 'A's' reference is not updated
    Last edited by Axel; 10-25-2005 at 04:45 AM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You're overwriting 'first' without storing it any place first. Did you mean to?


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

  3. #3
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    nope.

    But i've modified it now:

    Code:
        charNode *newList = NULL;
        newList = first ;
        first = next;
        next = newList;
        newList = first ;
        return newList;
    and get the same result
    B,C,D

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    So what exactly are you trying to do? Reverse A and B in the list? So it ends up B A C D E F...?
    Code:
    struct node *foo( struct node *a, struct node *b )
    {
        struct node *temp = b->next;
        b->next = a;
        a->next = temp;
    
       return b;
    }
    I will never understand how linked lists can possibly give you this much trouble. :P


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

  5. #5
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    works great, i have no idea why

    start = swap(start->next, start->next->next);

    the opposite won't work

    actually it does work but

    it skips A
    forming CBD
    Last edited by Axel; 10-25-2005 at 05:40 AM.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    It fails because you have no way of resetting the pointer which points to it. Linked lists are really really easy if you take a few seconds to actually think about what you're doing.
    Code:
    [start] = swap( [start->next], [start->next->next] )
    Do you see what you're doing? You're reasigning 'start' to point to whatever is returned by this function, but you're passing it [start->next] and [start->next->next]. So what happened to the origional [start]? Of course it skips [start], you just told it to.

    You really need to think about what you want your function to do. As it stands, you pass it two consecutive nodes to swap. This doesn't really work, because you're not using double linked lists. If you were, this would work in every single case, with minimal code.

    As it stands, you have to write a function much more complicated. You need to:

    a) Pass it the start of the list.
    b) Pass it the first node of the two to swap.
    c) Pass it the second node of the two to swap.
    d) Walk through and find the node that points to the first node, if any.
    e) Walk thorugh and find the node that points to the second node, if any.
    f) Make your adjustments.

    Now a double linked list:

    a) Pass it the start of the list.
    b) Pass it the first node of the two to swap.
    c) Pass it the second node of the two to swap.
    d) Make your adjustments.

    The nice thing about double linked lists is that they point to the node before them. This makes stuff like what you're trying to do very very easy.

    As it is, this will be a good exercise for you. Just take your time visualizing your nodes. If it helps, use physical objects to represent the nodes, line them up, and visualise your severing of the links between them as you adjust pointers. Then you'll see what you're really doing, where your pointers are going.


    Quzah.
    Last edited by quzah; 10-25-2005 at 06:02 AM.
    Hope is the first step on the road to disappointment.

  7. #7
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by quzah
    a) Pass it the start of the list.
    .
    do i pass start to both the parameters?

    Doubly linked lists sounds much easier. I just want to get the hang of this first.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You pass whatever you want to pass. It's your function. However, in a single linked list, if you don't pass for at one of the arguments, the very start of the list, you have no way to get back to it to run through the whole list. You only have the ->next pointer, so all you can do is go foreward. Like going past the exit you've missed on the interstate. You've got no way to go back.

    Thus, you need to really think what your function is supposed to do, and what each argument you provide's purpose is.


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

  9. #9
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by quzah
    . Like going past the exit you've missed on the interstate. You've got no way to go back.

    Thus, you need to really think what your function is supposed to do, and what each argument you provide's purpose is.

    Yes you can you can always re-verse or make a U turn Although i wouldn't suggest this because it's dangerous espically in an interstate.

    But i do understand the point you're trying to make. I guess i'll have to make it accept one parameter and then go to the other steps

  10. #10
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by quzah


    e) Walk thorugh and find the node that points to the second node, if any.
    i'm stuck at this bit. I've drawn up a small diagram to make things easier. I know why we need the first node but why the second?

  11. #11
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    and just to clarify something:

    here's what i'm aiming to do with this function:

    A | B | C | D | E | F | G

    A | C | B | D | E | F | G

    A | C | D | B | E | F | G

    A | C | D | E | B | F | G

    etc...

    it should be easy once i figure out how to swap the current elements next element, next element around.

  12. #12
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by quzah
    f) Make your adjustments.
    I'm stuck on this bit, could please give me some more info? I just can't seem to resync back A to the rest of the list once a swap has been made.

  13. #13
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    now C is missing

    A, , B, D
    Code:
       start = foo(start, start->next, start->next->next);
    charNode *foo(charNode *start, charNode *a, charNode *b )
    {
     charNode *temp = b->next;
        charNode *temp2 = a->next->next;
        b = temp2;
        a->next = temp;
        b = start;
    
    
    
    
       return b;
    }
    Last edited by Axel; 10-25-2005 at 08:39 AM.

  14. #14
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    i'm still having trouble figuring it out. I know how the original swap function works. I'm just not sure how to update it so it includes A at the start without skipping a i.e. A, , B, D

    correct me if i'm wrong with the original swap function here's what happens:
    Code:
    
       charNode *temp = b->next; /* get whatever is AFTER b, in this case C. store it somewhere */
       b->next = a; /* swap a and b around to form B, A */
       a->next = temp; /* get the stored value from temp (c) and store it AFTER a(A)->next(C). to form BAC */
    and i've tried implementing the same approach, visuallised it with a deck of cards named a,b,c,d.

    here's what i came up with:

    Code:
      charNode *temp = a; /* store a */
       charNode *temp2 = b; /* store b */
       charNode *temp3 = b->next; /* store whatever is after b (c) */
       a->next = temp3; (store C to a->next(B)) to form A,CB)
       a->next->next->next = temp2; (update the list to form A,C,B,D)
       a = temp; (place A at the start of the list)

    it still gives me A, C, D.

    and i tried removing some nodes to form A,B,C

    Code:
    charNode *temp = a;
       charNode *temp2 = a->next;
       charNode *temp3 = b->next;
       a->next = b->next; /* form A, C works until here */
       temp2 = temp3; (place B at the end to  form A,C,B) */
    prints A,C

    B is skipped
    Last edited by Axel; 10-25-2005 at 12:26 PM.

  15. #15
    Registered User cbastard's Avatar
    Join Date
    Jul 2005
    Location
    India
    Posts
    167
    Code:
    charNode *temp = a; /* store a */
    charNode *temp2 = b; /* store b */
    charNode *temp3 = b->next; /* store whatever is after b (c) */
    a->next = temp3;
    (store C to a->next(B)) now you have lost the pointer to b which was a->next now the list is you can say {A C} or {B C}.

    Code:
    a->next->next->next = temp2
    a->next->next is c->next.c->next is NULL in your implementation.
    a->next->next->next is c->next->next.so you are refering
    NULL->next


    Code:
    charNode *temp = a;
       charNode *temp2 = a->next;       temp2 is b
       charNode *temp3 = b->next;        temp3 is c 
       a->next = b->next; /* form A, C works until here */
    temp2 = temp3; you are overwriting temp2(b) to temp3(c).now you again lost b.
    Long time no C. I need to learn the language again.
    Help a man when he is in trouble and he will remember you when he is in trouble again.
    You learn in life when you lose.
    Complex problems have simple, easy to understand wrong answers.
    "A ship in the harbour is safe, but that's not what ships are built
    for"

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 03:39 PM
  3. <Gulp>
    By kryptkat in forum Windows Programming
    Replies: 7
    Last Post: 01-14-2006, 01:03 PM
  4. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 07:39 AM
  5. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 06:06 PM

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