Search code examples
javasortingnodes

Sorting a singly linked list by changing the value of elements


According to my assignment, I need to sort the elements of a single linked list in two ways. The first is by changing the pointers. As far as I believe bubble sorting is meant. And the second is by changing the values of the elements. What could it be? Insert?


Solution

  • You are confusing the sorting algorithm with the swap method.

    To sort a list, you can use the bubble sort algorithm, the insertion sort algorithm, or any of many others.

    But no matter what algorithm you use, sorting will involve changing the order of elements in the list. How will you do that? A list is a bunch of nodes connected by pointers; you must either change the pointers, or change the nodes. (I suppose you could do both, if you wanted a challenge.)

    Suppose you have a list. Three nodes which we will call A, B and C, each containing a number. When you begin, A contains 22, B contains 55 and C contains 33, and the pointers are A->B->C. So the order of the list is {22, 55, 33}, and you want to sort it into {22, 33, 55}. Once the algorithm (whichever one you choose) tells you that B and C are out of order, you can either redirect the pointers to get A->C->B (leaving the contents of the nodes undisturbed), or swap the contents of B and C (leaving the pointers as they are).