writting swap function

[Pulock2009]

i want to write a swap function for a singly linked list. the function should take 2node pointers as input parameters and exchange their place in the linked list. this is what i tried out :

void swap(node *p,node *q)
{
/*assigning the previous and current nodes*/
node *pprev,*qprev;
node *pcurr,*qcurr;
node *temp;
pprev=p;
qprev=q;
pcurr=p->link;
qcurr=q->link;
/*swapping for q in the place of p*/
temp=qcurr;
pprev->link=temp;
temp->link=pcurr->link;
/*swapping for p in the place of q*/
temp=pcurr;
qprev->link=temp;
temp->link=qcurr->link;
}

please point out where i went wrong. thanks in advance!!!

[vart]

[code]
Before

A -> B -> ... L -> P -> R -> ... -> M -> Q -> S -> ...

After

         
                 ------------------------------
                 | ------------------         |
                 | |                |         |
                 | V                |         V
A -> B -> ... L  |-P    R -> ... -> M  - Q    S -> ...
              |         ^              | ^
              |         ---------------| |
              |                          |
               ---------------------------

So you need to change 4 pointers
L->link
P->link
M->link
Q->link

How do you plan to get L->link and M->link?

Easier will be to swap contents of the P node and Q node living links intact...
Or - you need to pass M and L nodes the the swap function which will swap P and Q nodes (using 4 links method)

And special case will be when one of nodes is Head

[whiteflags]

A -> D -> ... C -> B -> E

Like vart says, to swap D and B, you have to find and change A->link and D->link, and C->link and B->link. If you have the head node, you can find A->link and C->link easily, just by following links until you arrive at the nodes A and C: save these locations. You should be able to do a temp swap with D->link and B->link, then point A->link at B and C->link at D. The list should be whole. Avoid the special case with head nodes, by attaching the head of a list to dummy->link.

[vart]

If you have the head node, you can find A->link and C->link easily, just by following links until you arrive

if you need to walk whole list for each simple operation on it - you are working with the wrong container type or your logic is broken

[iMalc]

please point out where i went wrong. thanks in advance!!!

You went wrong in your second sentence:

the function should take 2node pointers as input parameters and exchange their place in the linked list

It needs three parameters, or four if the items are not consecutive.

[whiteflags]

if you need to walk whole list for each simple operation on it - you are working with the wrong container type or your logic is broken

Well we don't have the benefit of prev links in a singly linked list, so if you aren't going to pass in all the necessities, then you will have to walk the list to get prev nodes. It's not still broken now is it?

[quzah]

You can only need the two pointers if the list is circular. That's the only way you can get away with just passing the two nodes to swap. Otherwise, you at a bare minimum need a pointer to the root of the node. Not the node itself, a pointer to it -- in case it happens to be one of the ones you're trying to swap.


Quzah.

[Pulock2009]

thanks a lot for all of your valuable advice. it was particularly enlightening for me to know that one needs to pass 4 parameters in case of a singly linked list and that my idea would be applicable for only circular linked lists. also i was thinking of swapping the node-data instead of the links which is what i will be doing now.