-
February 28th, 2013, 01:26 AM
#1
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;
}
}
}
-
February 28th, 2013, 01:36 AM
#2
Re: Swap adjacent nodes in doubly linked list?
Originally Posted by Sinlak
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.
-
February 28th, 2013, 01:47 AM
#3
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
-
February 28th, 2013, 02:07 AM
#4
Re: Swap adjacent nodes in doubly linked list?
Originally Posted by Sinlak
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
-
February 28th, 2013, 10:51 AM
#5
Re: Swap adjacent nodes in doubly linked list?
Originally Posted by Sinlak
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.
-
February 28th, 2013, 01:55 AM
#6
Re: Swap adjacent nodes in doubly linked list?
Originally Posted by Sinlak
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
-
February 28th, 2013, 02:24 AM
#7
Re: Swap adjacent nodes in doubly linked list?
Originally Posted by Paul McKenzie
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!
-
February 28th, 2013, 07:11 AM
#8
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.
-
February 28th, 2013, 08:10 AM
#9
Re: Swap adjacent nodes in doubly linked list?
Originally Posted by 2kaud
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.
-
February 28th, 2013, 11:42 AM
#10
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!
-
February 28th, 2013, 03:10 PM
#11
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::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;
}
}
}
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|