Thread: 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

You're overwriting 'first' without storing it any place first. Did you mean to?


Quzah.

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.

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

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.

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.

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;
}

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

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.