• February 28th, 2013, 12:26 AM
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?

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, 12:36 AM
nuzzle
Quote:

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, 12:47 AM
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
• February 28th, 2013, 12:55 AM
Paul McKenzie
Quote:

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, 01:07 AM
Paul McKenzie
Quote:

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, 01:24 AM
Sinlak
Quote:

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, 06:11 AM
2kaud
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, 07:10 AM
GCDEF
Quote:

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, 09:51 AM
nuzzle
Quote:

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, 10:42 AM
2kaud
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, 02:10 PM
Sinlak
``` 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(); }  ```
``` 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;             }         }     }  ```