Thread: another list question....

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

    another list question....

    i have the following code:

    Code:
    testNode *temp = current;
    testNode *loc;   
       
            loc = current->next;
            current->next = current->next->next;
            loc->next = current;
            current = loc;
    which swaps 2 nodes around (the first node be at the start of the list)

    now i'm having trouble understanding how it works.

    if we have the following:

    BA and we want AB

    Code:
    
    loc = start->next; // we save A to loc
    current->next = current->next->next; <--- i don't understand this bit! Since nothing 
    // exists after current, next, next. Does it just make the two nodes point together?
    loc->next = current; // we put B after A
     current = loc; // put A before B
    any ideas?
    i just want to understand how it works.
    Last edited by Axel; 10-27-2006 at 10:31 PM.

  2. #2
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    Assuming u have 3 elements in ur list , say
    1 -> 2 -> 3 -> NULL

    and when u call ur function, curr is at the head of the list as u said,

    so we have,
    curr->val = 1
    loc->val=2
    ((curr->next)->next)->val=3

    now,
    1) the node with value 3 is made the next node for the head node.
    2) the next node for the value with value 2 is made curr ( which is ur head ) i.e, the node with value 2 is now ur head.


    so, U have loc at the head of the list,


    the new list wud be :
    2 -> 1 -> 3 ->null


    In ur case, we have at the start :
    curr- >val = B
    loc -> val = A
    loc -> next =NULL;

    " curr->next = (curr->next)->next "
    curr->next now points to NULL,

    next U do : " loc->next = curr "
    so, loc is at the head of the list..
    loc -> val = A
    loc -> next = curr

    curr->val = B
    curr->next = NULL
    Last edited by kris.c; 10-27-2006 at 10:56 PM.
    In the middle of difficulty, lies opportunity

  3. #3
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    what if there are only 2 nodes?

  4. #4
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    hmm.. and what does the last line

    current = loc; do ?

  5. #5
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    it just makes "curr" point to ur "loc" which is the head of the list. Probably ur function returns curr back to the main program.
    In the middle of difficulty, lies opportunity

  6. #6
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    yes it does. ummm

    Code:
    loc = current->next; // makes loc point to A
    current->next = current->next->next; // sets B->next to null so we have B NULL A
    loc->next = current; // we then get A NULL B
    current = loc; // make "A" the head..
    based on my drawings etc inbetween AB there always appears to be NULL since the second step sets it to NULL and it doesnt change from there ??

    i did another drawing this time it ends up being BAB

    but at the last line when you make "current" point to "loc" it ends up being AB... is this correct? so actually a B is left behind
    Last edited by Axel; 10-27-2006 at 11:24 PM.

  7. #7
    Registered User
    Join Date
    Jun 2004
    Posts
    277
    Do you need something like that?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
     int value;
     struct Node *next;
    }Node;
    
    
    int main()
    {
    Node head;
    Node *current;
    Node *temp;
    
     current = &head;
     current->value = 0;
     current->next = malloc(sizeof(Node));
     temp = current;
     current= current->next;
     current->value = 1 ;
     current->next = temp;
     current->next->next = NULL;
     printf("%d %d",current->value, current->next->value);
    
     return 0;
    }
    Notice I don't free my memory this is crappy quality code.
    Last edited by Maragato; 10-27-2006 at 11:27 PM.

  8. #8
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    nope, thanks anyway i have it working already. i was just trying to understand the code.

  9. #9
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    No,
    > current->next = current->next->next; // sets B->next to null so we have B NULL A
    that cannot be correct.
    U r effectively splicing out A with this, U now have :

    curr -> val = B, curr -> next =NULL
    loc -> val =A , loc ->next =NULL

    but ,U havent lost the node A as u still have a pointer to it.
    u now make loc->next =NULL and re-insert it into the list at the head

    so,
    loc->val = A , loc ->next =curr
    curr -> val = B , curr -> next = NULL

    next u make curr point to loc ( head of the list) and return curr..
    In the middle of difficulty, lies opportunity

  10. #10
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    hmm ok what about:

    i did another drawing this time it ends up being BAB
    at the last line when you make "current" point to "loc" it ends up being AB... is this correct? so actually a B is left behind

  11. #11
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    > so actually a B is left behind
    do u mean u r losing the last B in ur list ? that is not possible either.. try reading what I had written for three nodes again. Its actually easy, just work it out on a piece of paper..
    In the middle of difficulty, lies opportunity

  12. #12
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    here's what i mean diagrammatically.. it might help explain easier:

    http://img98.imageshack.us/img98/540/testzj4.jpg

  13. #13
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    I dont get that part where he says :

    B -- NULL -- B
    It deosnt make any sense. .
    U have a doubt with two or three nodes now?
    In the middle of difficulty, lies opportunity

  14. #14
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    i have doubts about 2 nodes only.


    well, loc->next = current;

    whatevers in current (i.e. B) put it after loc->next.

    since loc is at the position current->next

    it makes B NULL B

  15. #15
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    Again ... A is "SPLICED OUT" of the list.
    the next of current now points to NULL and not A.

    read on :

    for two nodes, at the start u have :

    B -- > A --> NULL

    B is ur curr and A is ur loc. right ?

    now , after curr->next = (curr->next)->next

    A is spliced out.but ,U still have "loc" pointing to A

    so, U now have :

    B -- > NULL in ur list
    and A -- > NULL still exists , but not as a part of ur list..


    even now,
    B is ur curr , loc is ur A .. fine ??

    after loc->next = curr U get :

    A -- > B --> NULL
    In the middle of difficulty, lies opportunity

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM