I was asked to create a program that enters numbers and displays the before sorting order, and the sorted order displaying the previous node address and the next node address. I was told not to swap the data inside the nodes, but move the nodes themselves. I have a problem with the sorting part because I certainly have no idea how to swap pointers. Here is my code so far:

#include <iostream>
#include <iomanip>
using namespace std;

typedef struct node
{
    int DATA;
    node *NEXT;
};

node *HEAD = NULL;
void Create(int data);
void Display();
void Sort();

int main()
{
    int num, numOfEl;
    cout << "Enter number of elements: ";
    cin >> numOfEl;
    cout << "Enter " << numOfEl << " numbers: ";
    for(int i = 0 ; i < numOfEl ; i++)
    {
        cin >> num;
        Create(num);
    }
    cout << "\nDisplay before sorting.\n";
    Display();
    Sort();
    cout << "\nDisplay after sorting.\n";
    Display();
}

void Sort()
{
    node *current = HEAD, *current2 = current->NEXT, *temp;
    while(current->NEXT->NEXT != NULL)
    {
        if(current->DATA > current->NEXT->DATA)
        {
            temp = current;
            current = current2;
            current2 = temp;
        }
        current = current->NEXT;
    }
}

void Display()
{
    node *current;
    current = HEAD;
    cout << setw(20) << "LAST" << setw(20) << "NUMBER" << setw(20) << "NEXT" << endl;
    while(current != NULL)
    {
        cout << setw(20) << current << setw(20) << current->DATA << setw(20) << current->NEXT << endl;
        current = current->NEXT;
    }
    system("pause>0");
}

void Create(int data)
{
    node *front, *tail;
    tail = new node;
    tail->DATA = data;
    tail->NEXT = NULL;
    if(HEAD == NULL)
        HEAD = tail;
    else
    {
        front = HEAD;
        while(front->NEXT!=NULL)
            front = front->NEXT;
        front->NEXT = tail;
    }
}

If I do get any help from here, thank you very much.

  1. If the node to be swapped is found on the head
    a. create a temporary pointer and make it point to the node after head
    b. make the next pointer of the head node point to the next node of the node after head
    c. make the next pointer of the node pointed by the temp pointer point to the head node
    d. make the head pointer point to the temp pointer

  2. If the node to be swapped is found in the middle
    a. same procedure with when swapping the head node but instead you'll use the temporary pointer when traversing the linked list in swapping the nodes

To swap two nodes of a single linked-list you will have to keep track of three pointers, let's call them "previous", "candidate1" and "candidate2". These three should always appear in that order in the list, that is, "previous" is the node before the first candidate for swapping and "candidate1" and "candidate2" are the two nodes that need to be swapped. So, we have:

Before the swap:

  • previous->NEXT == candidate1
  • candidate1->NEXT == candidate2
  • candidate2->NEXT == next_candidate

Then, after the swap, you just need to have the following:

  • previous->NEXT == candidate2
  • candidate1->NEXT == next_candidate
  • candidate2->NEXT == candidate1

From the above, it's pretty clear that all you have to do to perform the swap is to do this:

previous->NEXT = candidate2;
candidate1->NEXT = candidate2->NEXT;
candidate2->NEXT = candidate1;

It's that simple, except that you also have to consider the case of previous == NULL which would occur if candidate1 == HEAD, if that's the case, then you simply skip the first step.

BTW, your sorting loop is not complete, you need a nested loop. Doing one pass will only result in the largest value appearing at the end of the list (that's the "bubble" in bubble-sort), you need to do multiple passes until all is sorted.

The easiest way to do the swap is to swap the data, not the node itself. If you do that then there is no problem with pointers because they won't be changed. When a node has a lot of data items it is easier to put them into a structure so that the structure can easily be swapped. But in the OP's program there is only one int data item in the node so structure isn't necessary. Like I said, all you have to do is swap the int data item exactly like you would do if you were sorting a simple int array. Swapping nodes and adjusting all those pointers is just simply too much unnecessary work and headaches.

Edited 4 Years Ago by Ancient Dragon: spelling

@AD
He specified:

I was told not to swap the data inside the nodes, but move the nodes themselves.

The idea of this exercise is to not swap the data. I agree that if the data is small, it is better to swap the data, if this was for a real problem, not an exercise.

I have a problem though. How do I initialize the 'previous' variable since it's before the candidate1? My compiler says that the variable 'previous' is being used without being initialized.

as I understand mike_2000_17 suggestion

'previous' is not a variable but a pointer to a node
and it would point to the variable before the nodes to be swapped
so when traversing the linkedlist when the next node would be part of the node to be swapped after that, you assign the current node to 'previous'

now that I think about it, it's exactly the one I had in my mind which is no surprise since it's the common solution :)

Edited 4 Years Ago by zeroliken: added info

Hmmm, okay. So I've only manage to get the swapping in the head right now. I'm sorry if I don't really get the hang of it at this time, it's only my first year so please spare me. So when you say that previous, where would I point it?

better to swap the data, if this was for a real problem, not an exercise

Yes and if you swap data, you must still be quite sure that there is not any other pointers existing to the nodes or you have nightmare to debug. I would think so, no real world experience though...

you must still be quite sure that there is not any other pointers existing to the nodes

That should never happen, there shoul never be two nodes that have next pointers to the same node.

Here is a simple traversal algorithm that probably would make sense for one pass of the sorting:

node* previous = NULL;
node* candidate1 = HEAD;
node* candidate2 = candidate1->NEXT;
while( candidate2 != NULL ) {
  // do stuff.. (like swapping if necessary)

  previous = candidate1;
  candidate1 = candidate2;
  candidate2 = candidate2->NEXT;
};

This is how to handle the three pointers. So, again, previous always points to the node before the first candidate, or NULL if none exist (if the first candidate is HEAD). The above loop also has the feature that it will not execute if there is only one node, which makes sense since there is no need to sort anything if there is just one node.

skenario I thought about was that we would have functions min and max returning pointers to smallest and biggest node. Then we would sort the linked list. If we swap nodes the min and max would stay valid, if we exchange values, we get suden change of these values (so in this case we must store values, not node pointers)

skenario I thought about was that we would have functions min and max returning pointers to smallest and biggest node. Then we would sort the linked list. If we swap nodes the min and max would stay valid, if we exchange values, we get suden change of these values (so in this case we must store values, not node pointers)

This is what interface specifications are for. If your sorting algorithm swaps values, then you should specify in the post-conditions of your sorting function that all iterators or node pointers previously obtained to elements of the list are invalidated. This all boils down to the interface specification. In the STL, the linked-list implementation std::list specifies that the sort function does not invalidate iterators to the nodes, implying that node positions are swapped, not their values. One could relax this specification by specifying a sort function that could invalidate iterators, which would allow for value swapping as an optimization for small data elements. However, that would be cumbersome for people using it as they would often expect iterators to remain valid through all mutations of the linked-list, and it would have very limited application since there is rarely much advantage to storing very small data elements in a linked-list structure because the performance problems associated to the lack of locality of references are often much worse than the overhead in copying data around when storing in a contiguous array (e.g. std::vector or std::deque). And if what you are looking for is invariant iterators, then you probably prefer a linked-list implementation that never invalidate iterators. I would imagine that is the rationale behind the std::list interface specification.

Thank you to everyone contributed. I have a working program now. Thank you again. Here is my code:

#include <iostream>
#include <iomanip>
using namespace std;

typedef struct node
{
    int DATA;
    node *NEXT;
};

node *HEAD = NULL;

void Create(int data);
void Display();
void Sort();

int main()
{
    int numOfEl, num;
    cout << "Enter number of elements: ";
    cin >> numOfEl;
    cout << "Enter " << numOfEl << " numbers: ";
    for(int i = 0 ; i < numOfEl ; i++)
    {
        cin >> num;
        Create(num);
    }
    cout << "\nDisplay before sorting.\n";
    Display();
    cout << "\nDisplay after sorting.\n";
    Sort();
    Display();
}

void Sort()
{
    node* curr = HEAD;
    int count = 0;
    while(curr!=NULL)
    {
        count++;
        curr = curr->NEXT;
    }
    for(int i = count ; i > 1 ; i-- )
    {
        node *temp, *swap1;
        swap1 = HEAD;
        for(int j = 0 ; j < count-1 ; j++ )
        {
            if(swap1->DATA > swap1->NEXT->DATA)
            {
                node *swap2 = swap1->NEXT;
                swap1->NEXT = swap2->NEXT;
                swap2->NEXT = swap1;
                if(swap1 == HEAD)
                {
                    HEAD = swap2;
                    swap1 = swap2;
                }
                else
                {
                    swap1 = swap2;
                    temp->NEXT = swap2;
                }
            }
            temp = swap1;
            swap1 = swap1->NEXT;
        }
    }
}

void Create(int data)
{
    node *front, *tail;
    tail = new node;
    tail->DATA = data;
    tail->NEXT = NULL;
    if(HEAD == NULL)
        HEAD = tail;
    else
    {
        front = HEAD;
        while(front->NEXT!=NULL)
            front = front->NEXT;
        front->NEXT = tail;
    }
}

void Display()
{
    node *curr;
    cout << setw(20) << "LAST" << setw(20) << "NUMBER" << setw(20) << "NEXT" << endl;
    curr = HEAD;
    while(curr!=NULL)
    {
        cout << setw(20) << curr << setw(20) << curr->DATA << setw(20) << curr->NEXT << endl;
        curr = curr->NEXT;
    }
    system("pause>0");
}

If I may suggest an improvement, notice that you don't really need to count the number of nodes in your list before you do the sorting. The bubble sort algorithm has the effect of pushing that maximum value at the end of the list. So, at every outer-loop iteration, you increase by one the number of sorted nodes at the end of the list. If you keep track of the last sorted element from after terminating the inner-loop, you have the node at which you should stop the next inner-loop. As for stopping the outer-loop, you just need to stop when the last sorted element is equal to HEAD.

void Sort()
{
    node * list_end = NULL;
    while(list_end != HEAD)  // this also takes care of the HEAD == NULL case, which you forgot!
    {
        node *temp, *swap1;
        swap1 = HEAD;
        while( swap1->NEXT != list_end )
        {
            if(swap1->DATA > swap1->NEXT->DATA)
            {
                node *swap2 = swap1->NEXT;
                swap1->NEXT = swap2->NEXT;
                swap2->NEXT = swap1;
                if(swap1 == HEAD)
                {
                    HEAD = swap2;
                    swap1 = swap2;
                }
                else
                {
                    swap1 = swap2;
                    temp->NEXT = swap2;
                }
            }
            temp = swap1;
            swap1 = swap1->NEXT;
        }
        // update the list_end to the last sorted element:
        list_end = swap1;
    }
}

Another important optimization that you missed is to check for no-swaps in the inner-loop. During your inner-loop, you should keep a bool value to tell whether a swapped has occurred or not through the inner-loop. The reason for this is that if there were no swaps required throughout the inner-loop, then it is a guarantee that the entire list is sorted already. So, if no swap occurred in the inner-loop, you can stop the outer-loop and thus the whole algorithm.

Still can't help but feel the linked list shouting 'Insertion sort!', as insertion to linked list is cheap.

This article has been dead for over six months. Start a new discussion instead.