In this recipe, we will learn how to create a singly linked list comprising integer elements, and then we will learn how to sort this linked list in ascending order.
A singly linked list consists of several nodes that are connected through pointers. A node of a singly linked list might appear as follows:
As you can see, a node of a singly linked list is a structure composed of two parts:
- Data: This can be one or more variables (also called members) of integer, float, string, or any data type. To keep the program simple, we will take data as a single variable of the integer type.
- Pointer: This will point to the structure of the type node. Let's call this pointer next in this program, though it can be under any name.
We will use bubble sort for sorting the linked list. Bubble sort is a sequential sorting technique that sorts by comparing adjacent elements. It compares the first element with the second element, the second element with the third element, and so on. The elements are interchanged if they are not in the preferred order. For example, if you are sorting elements into ascending order and the first element is larger than the second element, their values will be interchanged. Similarly, if the second element is larger than the third element, their values will be interchanged too.
This way, you will find that, by the end of the first iteration, the largest value will bubble down towards the end of the list. After the second iteration, the second largest value will be bubbled down to the end of the list. In all, n-1 iterations will be required to sort the n elements using bubble sort algorithm.
Let's understand the steps in creating and sorting a singly linked list.