3 Approaches to Sorting a Linked list

Pre-Requisite knowledge: Ability to perform linked list insert/delete/find/modify operations. Knowledge of bubble sort algorithm for approach 2.

Approach 1: Create a new linked list in the different required sort order.

Make dummy node for new list 2

From start of list1 to end of list 1:

Unlink item from list 1 storing node address without freeing node.

Insert item into list 2 in required sorted postion

Free dummy node etc. in list 1.

Make list 2 the list

Approach 2: Use Bubble Sort Algorithm within original list

Count length of list n either at start or during first pass

Do n-1 passes:

For all node pairs on this pass:

Note address of node prior to pair of nodes to compare

If swap required (i.e. keys are not in required sort order)

Either:

unlink first node (delete but don't free it)

insert unlinked node after second node.

OR:

Leave chain intact but using a temp node,

swap all data fields between 1st and 2nd

Approach 3: Cheat using a dynamic pointer array declared as NODE**

NODE** temparray;

int nnodes;

...

//Count number of nodes as nnodes

temparray=(NODE**)malloc(sizeof(NODE*) * nnodes);

For each node in list:

store node address in temparray e.g. temparray[i++]=NodeAddress;

Use any conventional array sort algorithm based on temparray.

Free temp array.

Note: Swaps should affect data only, and leave linked list node order intact. This is made easier if you declare your data record as an embedded structure within your linked list structure e.g.

typedef struct data {

char student[20];

float mark;

} DATA;

typedef struct node {

DATA d;

struct node *next;

} NODE;

Nesting your DATA type in this way enables you to swap the DATA items directly as whole records without having to swap many DATA members, while leaving list linkage unchanged:

e.g.

DATA temp;

...

temp=temparray[i].d;

temparray[i].d=temparray[j].d;

temparray[j].d=temp;