writting swap function

This is a discussion on writting swap function within the C Programming forums, part of the General Programming Boards category; i want to write a swap function for a singly linked list. the function should take 2node pointers as input ...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    26

    writting swap function

    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 :
    Code:
    
    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!!!

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    [code]
    Before
    Code:
    A -> B -> ... L -> P -> R -> ... -> M -> Q -> S -> ...
    After
    Code:
             
                     ------------------------------
                     | ------------------         |
                     | |                |         |
                     | 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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    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.
    Last edited by whiteflags; 04-06-2010 at 12:58 PM. Reason: whoops

  4. #4
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    Quote Originally Posted by whiteflags View Post
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Pulock2009 View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    Quote Originally Posted by vart View Post
    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?

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Oct 2009
    Posts
    26

    thanks a lot!!!

    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. In over my head
    By Shelnutt2 in forum C Programming
    Replies: 1
    Last Post: 07-08-2008, 07:54 PM
  2. Brand new to C need favor
    By dontknowc in forum C Programming
    Replies: 5
    Last Post: 09-21-2007, 11:08 AM
  3. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 09:10 AM
  4. C++ compilation issues
    By Rupan in forum C++ Programming
    Replies: 1
    Last Post: 08-22-2005, 06:45 AM
  5. I need help with passing pointers in function calls
    By vien_mti in forum C Programming
    Replies: 3
    Last Post: 04-24-2002, 11:00 AM

Tags for this Thread


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