# Sorting Linked Lists (code not concept)

• 05-10-2004
Newbie Magic
Sorting Linked Lists (code not concept)
I am a little new at this (notice the name :D )

I created a linked list and want to sort it (notice thread name :p )

Code:

```struct NODE {         int data;         NODE *next;                                 }; class LINKED_LIST {         public:                 LINKED_LIST();                 ~LINKED_LIST();                 void insertAfterHead(int);                        int getHead() { return head->data; }                 int getTail() { return tail->data; }                 int printList();                 bool searchList(int);                 void clear();                        void removeNode(int);                 NODE *head;                 NODE *tail; };```

Here is my sorting method:

Code:

```LINKED_LIST sortList(LINKED_LIST List) {         LINKED_LIST Temp;         NODE *walker = new NODE, *temp_node = new NODE;         int a = 0,b = 0;         walker = List.head;         temp_node->data = 1;         while(walker != NULL)         {                 if(walker->data > temp_node->data)                         temp_node = walker;                 walker = walker->next;                 if(walker->next == NULL)                 {                         Temp.insertAfterHead(temp_node->data);                         delete temp_node;                         walker = List.head;                         NODE *temp_node = new NODE;                         temp_node->data = 1;                 }         }         return List; }```
And I have double checked it and didn't see anything wrong with it, but I make many mistakes in debugging and no idea what is wrong, perhaps some help can be offered :rolleyes:
• 05-10-2004
codec
If you could post the exact behaviour of your sorting algorithm that would be helpful so we know exactly what's going wrong.
• 05-11-2004
Kip Neuhart
The function has quite a few problems. Most notable are the fact that releasing the memory for temp_node destroys the structure of List and will cause future searches to fail with an access violation, an off by one error due to advancing walker before testing walker->next against null, returning the destroyed List instead of the sorted Temp, and memory leaks due to allocating memory for the first test using temp_node, but no release before reassigning the pointer to a node within the list.

The following fixes all but the memory leak.
Code:

```LINKED_LIST sortList(LINKED_LIST List) {   LINKED_LIST Temp;   NODE *walker, *temp_node = new NODE;   walker = List.head;   temp_node->data = 0;   while(walker != NULL)   {     if(walker->data > temp_node->data)       temp_node = walker;     if(walker->next == NULL)     {       Temp.insertAfterHead(temp_node->data);       List.removeNode(temp_node->data);       walker = List.head;       temp_node = new NODE;       temp_node->data = 0;     }     walker = walker->next;   }   return Temp; }```