Sort a linked list in C

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.

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

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.

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.

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.

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

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.

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.

Last update on December 20 2021 09:10:09 [UTC/GMT +8 hours]

Write a C programming to sort a given linked list by bubble sort.

Sample Solution:

C Code:

// Licence: //bit.ly/2JK1psc #include #include struct node { int data; struct node *next; }; int main[] { struct node *temp1,*temp2, *t,*newNode, *startList; int n,k,i,j; startList=NULL; printf["Input number of elements in the linked list?"]; scanf["%d",&n]; printf["Input the elements in the linked list:\n"]; for[i=1;idata]; newNode->next=NULL; startList = newNode; temp1=startList; } else { newNode=[struct node *]malloc[sizeof[struct node]]; scanf["%d",&newNode->data]; newNode->next=NULL; temp1->next = newNode; temp1=newNode; } } for[i=n-2;i>=0;i--] { temp1=startList; temp2=temp1->next; for[j=0;jdata > temp2->data] { k=temp1->data; temp1->data=temp2->data; temp2->data=k; } temp1=temp2; temp2=temp2->next; } } printf["Sorted order is: \n"]; t=startList; while[t!=NULL] { printf["%d\t",t->data]; t=t->next; } }

Sample Output:

Input number of elements in the linked list? 5 Input the elements in the linked list: 15 33 49 6 65 Sorted order is: 6 15 33 49 65

Flowchart :

C Programming Code Editor:

Have another way to solve this solution? Contribute your code [and comments] through Disqus.

Previous: Write a program in C to search an element in a circular linked list.
Next: C Programming Exercises on Numbers Home

What is the difficulty level of this exercise?

C Programming - typedef struct vs struct definitions

The common idiom is using both:

typedef struct S { int x; } S;

They are different definitions. To make the discussion clearer I will split the sentence:

struct S { int x; }; typedef struct S S;

In the first line you are defining the identifier S within the struct name space [not in the C++ sense]. You can use it and define variables or function arguments of the newly defined type by defining the type of the argument as struct S:

void f[ struct S argument ]; // struct is required here

The second line adds a type alias S in the global name space and thus allows you to just write:

void f[ S argument ]; // struct keyword no longer needed

Note that since both identifier name spaces are different, defining S both in the structs and global spaces is not an error, as it is not redefining the same identifier, but rather creating a different identifier in a different place.

To make the difference clearer:

typedef struct S { int x; } T; void S[] { } // correct //void T[] {} // error: symbol T already defined as an alias to 'struct S'

You can define a function with the same name of the struct as the identifiers are kept in different spaces, but you cannot define a function with the same name as a typedef as those identifiers collide.

Ref : //bit.ly/37uzmZS