Swap adjacent nodes in doubly linked list?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: Swap adjacent nodes in doubly linked list?

  1. #1
    Join Date
    Feb 2013
    Posts
    4

    Swap adjacent nodes in doubly linked list?

    I have been trying to swap two adjacent nodes for my linked list sort. Its not meant to be optimal, just meant to work. My problem is I either lose nodes or get Access Violation errors, Can anyone help?

    PHP Code:
    void List::sortList()
    {
        
    Node *current _head;

        
    Node *rightNode NULL;        

        if (
    _head->_data _head->_next->_data)
        {            
            
    current _head;
            
    rightNode _head->_next;
            
    current->_previous rightNode;
            
    current->_next rightNode->_next;
            
    rightNode->_previous NULL;
            
    rightNode->_next current;
            
    _head rightNode;
        }
        

        
    bool swapped true;

        while (
    swapped)
        {
            
    current _head;
            
    swapped false;
            while (
    current->_next != NULL)
            {
                if (
    current->_next->_data current->_data)
                {
                    
    Node *left, *right;
                    
    left current;
                    
    right current->_next;

                    
    left->_next right->_next;
                    
    left->_previous->_next right;
                    
    right->_next->_previous left;
                    
    right->_previous left->_previous;
                    
    right->_next left;
                    
    left->_previous right;
                    
    swapped true;
                }    
                
    current current->_next;
            }

        }



  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Swap adjacent nodes in doubly linked list?

    Quote Originally Posted by Sinlak View Post
    I have been trying to swap two adjacent nodes for my linked list sort.
    When sorting a linked list the nodes aren't swapped structurally. It's the values the nodes hold that are swapped.

  3. #3
    Join Date
    Feb 2013
    Posts
    4

    Re: Swap adjacent nodes in doubly linked list?

    The problem is that the payload may be HUGE so it would be better to swap the pointers around, thats why I have to solve it this way

  4. #4
    Join Date
    Apr 1999
    Posts
    27,444

    Re: Swap adjacent nodes in doubly linked list?

    Quote Originally Posted by Sinlak View Post
    I have been trying to swap two adjacent nodes for my linked list sort. Its not meant to be optimal, just meant to work. My problem is I either lose nodes or get Access Violation errors, Can anyone help?
    Before doing anything, did you draw on paper with boxes and arrows showing how the sort will work? You always do that first before writing any code. If you did that, then the code should follow the plan you drew up and work correctly on the first, second, or third try. If not, then you debug the code see where it diverges from your plan, or you then determine that your original plan was flawed.

    If you're just writing code thinking how it should work without any plan on paper, then that is the wrong approach.

    Regards,

    Paul McKenzie

  5. #5
    Join Date
    Apr 1999
    Posts
    27,444

    Re: Swap adjacent nodes in doubly linked list?

    Quote Originally Posted by Sinlak View Post
    The problem is that the payload may be HUGE so it would be better to swap the pointers around, thats why I have to solve it this way
    Unless a teacher forced you to solve this way, there is no reason to "have to solve it this way".

    Why don't you have a linked list that contains pointers to dynamically created objects? Then the only copying is that of a pointer, not of an entire object.

    Regards,

    Paul McKenzie

  6. #6
    Join Date
    Feb 2013
    Posts
    4

    Re: Swap adjacent nodes in doubly linked list?

    Quote Originally Posted by Paul McKenzie View Post
    Before doing anything, did you draw on paper with boxes and arrows showing how the sort will work? You always do that first before writing any code. If you did that, then the code should follow the plan you drew up and work correctly on the first, second, or third try. If not, then you debug the code see where it diverges from your plan, or you then determine that your original plan was flawed.

    If you're just writing code thinking how it should work without any plan on paper, then that is the wrong approach.

    Regards,

    Paul McKenzie
    Ive been drawing all day, still Im at a loss. Everytime I recode it I feel like "This time it will work for sure!' then I hit F5 and my dreams are crushed!

  7. #7
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,701

    Re: Swap adjacent nodes in doubly linked list?

    Can you provide the definition of Node. What exactly is List::sortlist trying to do? as you do a data comparision first then enter a while loop which does more comparisons? You say that the payload (data) may be huge - yet you are doing comparisons on the data - so this data must be of a type for which the > and < operators have been defined.

    Is this a homework assignment? If it's not then why bother with writing linked lists? Why not use one of the STL containers? If you do need to write your own list code, why not create the list sorted in the first place? As Paul mentioned in post #5, why store a huge payload of data in the linked list instead of just storing a pointer in the node to a dynamically created object?

    Have you tried drawing a list of a few nodes on paper and then using the paper list walk through your code moving pointers etc on the paper exactly as the code says? I found in the past that helped me with pointer issues.

  8. #8
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,196

    Re: Swap adjacent nodes in doubly linked list?

    Quote Originally Posted by 2kaud View Post

    Have you tried drawing a list of a few nodes on paper and then using the paper list walk through your code moving pointers etc on the paper exactly as the code says? I found in the past that helped me with pointer issues.
    This is really what you need to do. Once you understand and can visualize the steps, coding it should be relatively easy. You need to figure out which nodes are involved and which pointers need to be swapped.

  9. #9
    Join Date
    May 2009
    Posts
    2,413

    Re: Swap adjacent nodes in doubly linked list?

    Quote Originally Posted by Sinlak View Post
    The problem is that the payload may be HUGE so it would be better to swap the pointers around, thats why I have to solve it this way
    Then, as has been suggested, one option is to store object pointers in the list nodes rather than the objects directly. An alternative if you don't want to use pointers is to store the objects in a random access array and then keep their index positions in the list.

    Yet another alternative is to break up the linked list and store the node pointers in an array, Then you sort the array and afterwards you rebuild the list from the sorted nodes in the array. Sorting an array is more efficient than sorting a linked list and you get rid of the complicated node swaps. Java does this when sorting a LinkedList. It really sorts an ArrayList.

  10. #10
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,701

    Re: Swap adjacent nodes in doubly linked list?

    Just a further thought. Before using List::sortList are you sure that the links are correct? Have you verified them? Have you printed the list from head to tail and from tail to head? If the links are not correct before you call List::sortList then you will definately get problems!

  11. #11
    Join Date
    Feb 2013
    Posts
    4

    Re: Swap adjacent nodes in doubly linked list?

    I solved it, the problem was the head was getting adjusted incorrectly during the swap, if anyones intrested here is some working code on swapping nodes in a doubly linked list

    The isSorted just cheks if the list is sorted or not, rather than using a flagged while loop (will alter it later)


    PHP Code:
    void List::sortList()
    {
        
    Node *current _head;        
        
        while (
    current->_next != NULL)    {
            
            if (
    current->_next->_data current->_data)
            {
                if (
    current == _head)
                    
                {
                    
    Node *rightNode _head->_next;
                    
    current _head;
                    
    rightNode _head->_next;
                    
    current->_previous rightNode;
                    
    current->_next rightNode->_next;
                    
    rightNode->_previous NULL;
                    
    rightNode->_next current;
                    
    _head rightNode
                }

                
    current->SwapWithNext();

            }    
            if (
    current->_next != NULL)
            
    current current->_next;
            

        }
        if (!
    isSorted())
            
    sortList();


    and from the node class

    PHP Code:
    void Node::SwapWithNextvoid )
        {
            
    // swap list positions with the other node - if there is one
            // i.e. it's next becomes my next, my prev becomes its prev

            
    Node *other this->_next;
            if ( 
    other )
            {
                
    Node *pLeftNode _previous;            // node before me
                
    Node *pRightNode other->_next;    // node after other

                
    other->_previous _previous;
                
    _next other->_next;

                
    other->_next this;
                
    _previous other;

                
    // not quite done because node to my left still thinks I'm next,
                // and node after other still thinks other is previous
                
    if ( pLeftNode )
                {
                    
    pLeftNode->_next other;
                }

                if ( 
    pRightNode )
                {
                    
    pRightNode->_previous this;
                }

            }

        } 

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center