# linked list swap function

Printable View

Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last
• 10-25-2005
Axel
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
• 10-25-2005
quzah
You're overwriting 'first' without storing it any place first. Did you mean to?

Quzah.
• 10-25-2005
Axel
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
• 10-25-2005
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.
• 10-25-2005
Axel
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
• 10-25-2005
quzah
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.
• 10-25-2005
Axel
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.
• 10-25-2005
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.
• 10-25-2005
Axel
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 :p 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-25-2005
Axel
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?
• 10-25-2005
Axel
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.
• 10-25-2005
Axel
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.
• 10-25-2005
Axel
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; }```
• 10-25-2005
Axel
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
• 10-25-2005
cbastard
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.
Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last