C++

Sort Linked list C++

Linked list

A linked list is a sort of data structure. The items inside the linked list are connected by using pointers. It is a collection of nodes. A node contains two parts. One includes the data, and the second part consists of the pointer. This pointer is used to store the memory address of the node element adjacent to it in the linked list. The advantage of the linked list of an array is that it has a dynamic size.

Representation of a linked list

The first node of the linked list is called ahead. Its value is Null in the case of an empty array. In C++, we use a structure to represent a node.

This is a simple C++ code of linked list creation. We have created a class in which its public portion, a data variable of integer type, is created with a pointer type variable ‘next’ that will store the address of the node.

Three nodes are created inside the main program, with the top first node declared as the ‘head’ node. All three-pointers of these nodes are empty, so they are declared as NULL initially. After doing this, all three nodes are allocated in a heap. ‘head’ second, and third is assigned with the new node.

Now we will assign data, and data can be any random value. First, we will assign data in the first node.

Head->data =1;

This demonstration of data assigning shows that the first node’s data part will contain data in it. After assigning data, we will link the first node with the second one

Head->next = second;

We connect the ‘next’ pointer portion with the other node to link two nodes. We will assign data stored in the data part of the first node. Whereas the ‘next’ portion will contain the memory address of the node present after it. Similarly, we will now assign data to the second node, and the second node will be linked with the third node. Now add data in the third node. As we have created only three nodes, there is no other node, so the next part of the third pointer will be declared as NULL; this indicates that the linked list is terminated.

Third->next = NULL;

Example

Sort linked list

Here we have declared a structure representing a node of a single linked list. As described above, the concept of linked list declaration, the data variable, and the pointer variables are taken in the structure. Like the ‘next’ pointer part that stores the address, we have also declared two more pointer type variables: node head and node tail. These both are initially declared as NULL.

As insertion node deals with inserting data node in the linked list, we will use a function of adding a node. The data will also assign this node. So the parameter of this function will contain data as an argument. Before insertion, the node will be created with memory allocation by using a malloc() function. The data portion of the new node will be assigned with the passed data.

Newnode->data = data;

And similarly, the next portion is assigned as NULL, as there is no connection between this node with any other. As head and tail variables are declared to assist in insertion sort. Now we will utilize them here. First, by using an if-else statement, we will check if the head is null, as we have declared as null above, which means that the whole list is empty. That’s why the head is empty, so the head and the tail variables will point to the newly created node. Otherwise, in the else part, if the list is not empty, suppose while creating the list we have also entered data, then, in this case, the new node will be added at the last place.

Tail->next = newNode;

And now, this new node will act as a new tale.

Tail = newNode;

For further addition, the same process continues, but we need to sort the linked list. So we have added a single node that acts as a temp node to store data in it temporarily.

After adding the new node, we will use a function to sort/ arrange the list. As the sort type is not mentioned here, by default, the list will be sorted in ascending order.

Coming back towards the example, another current pointer points to the head, as we declared above. This is used to sort the list items. Another pointer type variable will be used here and then declared as NULL. Further usage will be in the program later.

Here we will apply a check to identify if the head pointer is at the NULL position then return to the main program. Else we will apply logic here that will follow a while loop. The index pointer will point to the next part of the current node. Inside that while loop, another while loop is used, and this will also last until the current node is not null. Here we will use an if-statement to check if the data in the current node is greater than the data inside the index’s node, then the data between them is swapped.

The temp variable will play an important role here in data swapping. First, the current node’s data is transferred to temp, and then the current node is now empty. This node will be assigned the value of index data. And at the end, the empty index node is assigned by the data present in the temp variable.

Outside the if-statement, the index node is also incremented with the new value of an index. Similarly, outside the while loop, the current node is also assigned by the new value.

Next, we have used a display function here to display the value of all the nodes. The current pointer will point towards the head. In another case, a while loop displays all the values until the current node is not NULL.

Now consider the main program, the function of addNode() is called with the values to add new values inside the list. Then the display function will display all the entered values before sorting. Then call the sort () function. And then again, call the display function to display the entire sorted list.

Save the code file and then execute it in the Ubuntu terminal with the help of a G++ compiler.

$ g++ -o file file.c

$./file

From the resultant value, you can observe that the values are arranged in ascending order as they were entered randomly in the linked list.

Conclusion

‘Sort linked list C++’ contains the description of the basic knowledge regarding the linked list and its creation. A sample code is enough to demonstrate the node creation and the working of all the nodes in the linked list. The elements inside the linked list are arranged in ascending order using a detailed process by adding new nodes and then sorting through a temp variable. Explanation with the code is done to assist the user.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.