A Linked list data structure is efficient enough comparing to an Array. In this article, we will discuss how to implement the selection sort algorithm using Linked List.

*[This article is applicable especially for a singly linked list, but it is also applicable in a doubly linked list. I prefer C++ for this article. But you are free to use C or another programming languages for which, you feel comfortable.]*

*If you have visited this page accidentally and don’t know what is linked list or how to implement it, you are invited to the following article:*

What is Linked list? How to implement a linked list with C++?

**Step – 1:***First of all, we need to implement a normal singly linked list. After implementation, we have the following code:*

#include <iostream> using namespace std; struct Node { int data; //the data part of the Node. Node *next; //Pointer that have the link (reference) to the next node. }; Node *head = NULL; int getData() { int data; cout << "Input an integer as data: "; cin >> data; return data; } void addData(Node *targetNode, int data) { targetNode -> data = data; } void createNewNode(Node *prevNode) { Node *newNode = new Node; addData(newNode, getData()); //storing data to the new node. newNode -> next = NULL; prevNode -> next = newNode; } void createList(int total) { Node *Current = head = new Node; addData(Current, getData()); for(int i = 1; i < total; i++) { createNewNode(Current); Current = Current -> next; } } void showList() { Node *Current = head; cout << "Showing the linked list:" << endl; if(Current == NULL) { cout << "Empty list!" << endl; return; } while(Current != NULL) { cout << Current -> data << " "; Current = Current -> next; //Now, Current pointer is pointing it next Node. } cout << endl; } void selectionSort() { Node *selectedNode = head; while(selectedNode -> next != NULL) { Node *currentNode = selectedNode; Node *minimumNode = currentNode; int minimumData = currentNode -> data; while(currentNode != NULL) { if(minimumData > currentNode -> data) { minimumData = currentNode -> data; minimumNode = currentNode; } currentNode = currentNode -> next; } int tempSwap = minimumNode -> data; minimumNode -> data = selectedNode -> data; selectedNode -> data = tempSwap; selectedNode = selectedNode -> next; } } int main() { createList(5); showList(); selectionSort(); showList(); return 0; }

**Step – 2:***Let’s discuss the Selection Sort algorithm for a Linked List:*

**Selection sort** algorithm for a linked list is *almost*

*the same as the ***selection sort** algorithm for an** array**.

**selection sort**algorithm for an

**array**.

- We have to take a pointer to
**Node(struct)**that will point at**head**. - Using a loop, we will traverse the linked list till we don’t get the next Node is
**NULL**. - We will take a normal variable to store the minimum value of data.
- Then we will traverse the linked list (using a nested loop) each time from the selected node to the last node to get the minimum value between the currently selected node to the last node.
- After that will store the reference of the minimum node to a pointer which will keep track of the current minimum node. At the same time, we will store the minimum value of data in a normal variable.
- Now, we will swap the data values between the currently selected node and the minimum node.

And, this is our simple algorithm to sort a linked list.