Whats wrong with my node swap?

[DrolArumil]

I have a function in my node class of my linked list program, when I call the swapWithNext function from my node class it is suppose to swap the current node (this) with the ->next node by switching the pointers. It works..kind of. it loses nodes, Am I missing a connection between nodes or something? also sometimes I get an "Access violoation" when running the Sort function (pasted below) it looks like I am encountering a NULL node and thus it is unreadable, but when I use the same exact function and simply swap the data, everyting works perfect..

Any help would be appreciated, Thank you

heres the function

void Node::SwapWithNext( void )
{
	// 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;
		}
	
	}

}

and here is where I call it

void List::sortList()
{
	if (isEmpty())
		return;

	Node *current = _head;
	bool swapped = true;

	while (swapped)
	{
		current = _head;
		swapped = false;
		for (int i = 1; i < sizeOfList(); i++)
		{
			if (current->_next->_data < current->_data)
			{
				current->SwapWithNext();// this gives me error
				swapped = true;//..
                                 //this (swap data) works perfect
                                //swap(current->_data, current->next->_data)

			}	
			current = current->_next;
		}
		
	}

}

[cire]

Two things:

* Your code doesn't attempt to keep head pointing to the first element in the list (and you can't from inside the Node class unless the Node retains a reference to the list it belongs in - which may suggest this functionality doesn't belong in the Node class.)

* Your code doesn't handle the case where the previous pointer is null correctly.

[DrolArumil]

Thank you for your observations I will try a different approach.
My professor made the Swap function and said we could use it and that it was better than working on the nodes from the list class, which is the reason why I tried to implement it and was shocked that it did not work.

I am thinking of just making a buble sort or something like that in the list class to handle the full sort without having to call on the node class to do anything, I will report back :P

Thanks again

[cire]

You can use the swap function, but you have to keep track of what you're doing in sortList and update the head pointer appropriately (which is going to be true no matter what method of sorting you use.)

I would be more likely to implement it something like:

Node* Node::extract()
{
    _next->_previous = _previous ;
    _previous->_next = _next ;

    _next = _previous = nullptr ;
    return this ;
}

void Node::insertBefore( Node* n )
{
    if ( n->_previous )
        n->_previous->_next = this ;

    _previous = n->_previous ;
    n->_previous = this ;
    _next = n ;
}

void List::sortList()
{
    if (isEmpty() || _head->_next == nullptr )
		return;

    bool swapped = true ;
    while ( swapped )
    {
        swapped = false ;
        if ( _head->_next->_data < _head->_data )       // handle head as a special case.
        {
            Node * n = _head->_next->extract() ;
            n->insertBefore(_head) ;
            _head = n ;
            swapped = true ;
        }

        Node * current = _head->_next ;

        while ( current->_next )
        {
            if ( current->_next->_data < current->_data )
            {
                Node * n = current->_next->extract() ;
                n->insertBefore(current) ;
                swapped = true ;
            }
            else
                current = current->_next ;
        }
    }
}