sorting a link list

[Gunjan Rathi]

how a single linked list can be sorted by swapping the pointers??

[Gunjan Rathi]

we have swapped the values of nodes..
but that is not an efficient method.

[tinstaafl]

Have you looked at std::sort? It accepts a custom comparator.

[Gunjan Rathi]

no i have not looked something that. I don't know about it anything. Please explain it in details.

[tinstaafl]

The link in my post is a reference article.

[1stDAN]

c is not cplusplus, so std::sort might not be suitable.

/* to swap data d of two nodes in principle: */
if(p->d > q->d){
  t=p->d;
  p->d=q->d;
  q->d=t;
}

[Gunjan_1]

hey i m not to swap data. I m to swap nodes means direct pointers. Our teacher said that swapping data of nodes is not an efficient method.

[deceptikon]

Our teacher said that swapping data of nodes is not an efficient method.

That's an unfair statement by your teacher. Pointer surgery may be less efficient depending on the type of data stored by each node. Typically in a well designed list the data is itself a single pointer, which means swapping data is more efficient. If you're directly storing a complex structure then pointer surgery is likely more efficient, but I'd argue that the difference is largely negligible.

In my experience, if you're trying to squeeze out CPU cycles, the list will nearly always be simple enough such that swapping data is the better choice.

That said, there are two ways to go about a pointer swap. If you're working with a single linked list then you must start at the previous pointer to the one being swapped, otherwise the structure of the list will be broken:

a = p->next;
b = p->next->next;

a->next = b->next;
b->next = a;
p->next = b;

If you're working with a double linked list, you can start at the first node to swap, but also must update the previous links:

gp = p->prev;
a = p;
b = p->next;

a->next = b->next;
b->next = a;
gp->next = b;

a->prev = b;
b->prev = gp;

Note that this logic does not take into account edge cases such as where gp or b are NULL. You'll need to add conditional statements to account for such situations.

[Gunjan_1]

no i m not to perform this code with double linked list, instead i m to perform this with the use of single linked list.

[rubberman]

I wish there were a way to comment without up/down voting, so I commented on tinstaafl's post about std::sort with an up vote (I didn't feel it deserved a down vote).

Anyway, I had to do this in some production real-time code in the past. What I did was to put the nodes into an array, and then use qsort to sort the nodes, and finally to re-construct the linked list with the sorted nodes. It was efficient, and never caused a problem. There are still factories and US Navy facilities using that code (written in the late 1980's and early 1990's). I think I used it for some code in the US Navy RAMP (Rapid Aquisition of Manufactured Parts) project around 1990-1991.

[deceptikon]

What I did was to put the nodes into an array, and then use qsort to sort the nodes, and finally to re-construct the linked list with the sorted nodes.

I've done that as well, it works nicely. Other option that works is to keep the list sorted as you construct it in the first place, thus eliminating the need to perform a global sort. A few times I've transferred the list to a balanced binary tree and then back to a list with an inorder traversal as an implicit sort. That was surprisingly effective.

If you want to get deeper into less common data structures, instead of a single linked list you could use a skip list. Those are fun, and in a way the best of both worlds between a tree and a list.