# Sort the linked list elements by node frequency

Given a linked list, its node include the value of the integer element. Our goal is to arrange linked list element by node element frequency (lower to higher order).

```Example 1 :
------------
2 → 2 → 6 → 3 → 6 → 2 → NULL
Here frequency
2 -> 3 times
6 -> 2 times
3 -> 1 times

So sorted frequency
3 -> 1 times
6 -> 2 times
2 -> 3 times

Output
3 → 6 → 6 → 2 → 2 → 2 → NULL
Example 2
----------
1 → 1 → 2 → 3 → 2 → 1 → 3 →NULL
Here frequency
1 -> 3 times
2 -> 2 times
3 -> 2 times

So sorted frequency
2 -> 2 times
3 -> 2 times [Same frequency]
1 -> 3 times

Output
2 → 2 → 3 → 3 → 1 → 1 → 1 →NULL
or [because 2 and 3 are exist in same frequency]
3 → 3 → 2 → 2 → 1 → 1 → 1 →NULL
[Note that when 2 or more frequency are same
Then there element sequences appearance not important]
```

Here given code implementation process.

``````// C Program
// Sort the linked list elements by node frequency
#include <stdio.h>

#include <stdlib.h> //for malloc function

struct Node
{
int data;
struct Node *next;
};
struct Frequency
{
int key;
int counter;
struct Frequency *next;
};
//Create a node of linked list
struct Node *create_node(int data)
{
//Create dynamic node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
//Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
struct Node *add_node(struct Node *tail, int data)
{
struct Node *node = create_node(data);
if (tail != NULL)
{
tail->next = node;
}
return node;
}
struct Frequency *add_frequency(struct Frequency *collection, int key, int counter)
{
//Create dynamic node
struct Frequency *element = (struct Frequency *) malloc(sizeof(struct Frequency));
if (element == NULL)
{
printf("Memory overflow\n");
}
else
{
// Add the value of new element
element->key = key;
element->counter = counter;
element->next = NULL;
if (collection == NULL)
{
return element;
}
else if (collection->counter >= counter)
{
//When need to add node at beginning
element->next = collection;
return element;
}
else
{
struct Frequency *temp = collection;
while (temp != NULL && temp->next != NULL && temp->next->counter < counter)
{
//visit to next node
temp = temp->next;
}
element->next = temp->next;
temp->next = element;
}
}
return collection;
}
{
{
return;
}
while (temp != NULL)
{
{
printf(" →");
}
printf(" %d", temp->data);
//visit to next node
temp = temp->next;
}
printf(" → NULL\n");
}
struct Node *count_and_delete(struct Node *first, int *counter, int key)
{
//Define some auxiliary variables
struct Node *current = first;
struct Node *front = first;
struct Node *auxiliary = NULL;
struct Node *back = NULL;
first = NULL;
while (current != NULL)
{
if (current->data == key)
{
//When get delete node node
auxiliary = current;
//node counter
*counter = ( *counter) + 1;
}
else
{
back = current;
}
//visit to next node
current = current->next;
if (auxiliary != NULL)
{
//When Deleted node exists
if (back == NULL)
{
// When front node is delete
// head visit to next node
front = current;
}
else
{
// Deleted node are exist in intermediate or last position of linked list
// Before delete node, there left node is connecting to next upcoming node
back->next = current;
}
auxiliary->next = NULL;
//free node
free(auxiliary);
auxiliary = NULL;
}
}
return front;
}
void sort_by_frequency(struct Node **head, struct Node **tail)
{
{
}
else
{
struct Frequency *collection = NULL;
struct Frequency *temp = NULL;
int counter = 0;
int key = 0;
//set last node to null
*tail = NULL;
//Count node frequency and arrange in sorted order
while (current != NULL)
{
counter = 0;
}
while (collection != NULL)
{
counter = collection->counter;
key = collection->key;
while (counter > 0)
{
{
}
counter--;
}
temp = collection;
//visit to next node
collection = collection->next;
//Free node
temp->next = NULL;
free(temp);
temp = NULL;
}
}
}
int main()
{
struct Node *tail = NULL;
printf("Before sort by frequency\n");
// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
printf("Before sort by frequency\n");
//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
return 0;
}``````

#### Output

``````Before sort by frequency
2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Sort the linked list elements by node frequency
class Node
{
public: int data;
Node *next;
Node(int data)
{
//Set node value
this->data = data;
this->next = NULL;
}
};
class Frequency
{
public: int key;
int counter;
Frequency *next;
Frequency(int key, int size)
{
//Set node value
this->key = key;
this->counter = size;
this->next = NULL;
}
};
{
Node *tail;
//Class constructor
{
this->tail = NULL;
}
//insert node at last of linke list
{
//Create a node
Node *node = new Node(data);
{
this->tail = node;
}
else
{
this->tail->next = node;
this->tail = node;
}
}
void display()
{
{
return;
}
cout << "Linked List : ";
while (temp != NULL)
{
{
cout << " →";
}
cout << " " << temp->data;
//visit to next node
temp = temp->next;
}
cout << " → NULL\n";
}
Frequency *add_frequency(Frequency *collection, int key, int counter)
{
Frequency *element = new Frequency(key, counter);
if (element == NULL)
{
cout << "Memory overflow\n";
}
else
{
if (collection == NULL)
{
return element;
}
else if (collection->counter >= counter)
{
//When need to add node at beginning
element->next = collection;
return element;
}
else
{
Frequency *temp = collection;
while (temp != NULL && temp->next != NULL && temp->next->counter < counter)
{
//visit to next node
temp = temp->next;
}
element->next = temp->next;
temp->next = element;
}
}
return collection;
}
//Count and delete node which value is equal to front node
int count_and_delete()
{
//Define some auxiliary variables
Node *auxiliary = NULL;
Node *back = NULL;
int counter = 0;
while (current != NULL)
{
if (current->data == key)
{
//When get delete node node
auxiliary = current;
//node counter
counter = counter + 1;
}
else
{
back = current;
}
//visit to next node
current = current->next;
if (auxiliary != NULL)
{
//When Deleted node exists
{
// When delete first node
// head visit to next node
}
else
{
// Deleted node are exist in intermediate or last position of linked list
// Before delete node, there left node is connecting to next upcoming node
back->next = current;
}
auxiliary->next = NULL;
//free node
auxiliary = NULL;
}
}
return counter;
}
void sort_by_frequency()
{
{
cout << "\n Empty linked List";
}
else
{
Frequency *collection = NULL;
Frequency *temp = NULL;
int counter = 0;
int key = 0;
//Set last node to null
this->tail = NULL;
//Count node frequency and arrange in sorted order
while (current != NULL)
{
key = current->data;
counter = this->count_and_delete();
}
while (collection != NULL)
{
counter = collection->counter;
key = collection->key;
while (counter > 0)
{
counter--;
}
temp = collection;
//visit to next node
collection = collection->next;
//Free node
temp->next = NULL;
delete temp;
temp = NULL;
}
}
}
};
int main()
{
cout << "Before sort by frequency\n";
// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
obj.display();
obj.sort_by_frequency();
cout << "Before sort by frequency\n";
//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
obj.display();
return 0;
}``````

#### Output

``````Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL``````
``````// Java Program
// Sort the linked list elements by node frequency

class Node
{
public int data;
public Node next;
public Node(int data)
{
//Set node value
this.data = data;
this.next = null;
}
}
class Frequency
{
public int key;
public int counter;
public Frequency next;
public Frequency(int key, int size)
{
//Set node value
this.key = key;
this.counter = size;
this.next = null;
}
}
{
public Node tail;
//Class constructor
{
this.tail = null;
}
//insert node at last of linke list
{
//Create a node
Node node = new Node(data);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
public void display()
{
{
return;
}
while (temp != null)
{
{
System.out.print(" →");
}
System.out.print(" " + temp.data);
//visit to next node
temp = temp.next;
}
System.out.print(" → NULL\n");
}
public Frequency add_frequency(Frequency collection, int key, int counter)
{
Frequency element = new Frequency(key, counter);
if (element == null)
{
System.out.print("Memory overflow\n");
}
else
{
if (collection == null)
{
return element;
}
else if (collection.counter >= counter)
{
//When need to add node at beginning
element.next = collection;
return element;
}
else
{
Frequency temp = collection;
while (temp != null && temp.next != null && temp.next.counter < counter)
{
//visit to next node
temp = temp.next;
}
element.next = temp.next;
temp.next = element;
}
}
return collection;
}
//Count and delete node which value is equal to front node
public int count_and_delete()
{
//Define some auxiliary variables
Node auxiliary = null;
Node back = null;
int counter = 0;
while (current != null)
{
if (current.data == key)
{
//When get delete node node
auxiliary = current;
//node counter
counter = counter + 1;
}
else
{
back = current;
}
//visit to next node
current = current.next;
if (auxiliary != null)
{
//When Deleted node exists
{
// When delete first node
// head visit to next node
}
else
{
// Deleted node are exist in intermediate or last position of linked list
// Before delete node, there left node is connecting to next upcoming node
back.next = current;
}
auxiliary.next = null;
//free node
auxiliary = null;
}
}
return counter;
}
public void sort_by_frequency()
{
{
}
else
{
Frequency collection = null;
Frequency temp = null;
int counter = 0;
int key = 0;
//Set last node to null
this.tail = null;
//Count node frequency and arrange in sorted order
while (current != null)
{
key = current.data;
counter = count_and_delete();
}
while (collection != null)
{
counter = collection.counter;
key = collection.key;
while (counter > 0)
{
counter--;
}
temp = collection;
//visit to next node
collection = collection.next;
//Free node
temp.next = null;
temp = null;
}
}
}
public static void main(String[] args)
{
System.out.print("Before sort by frequency\n");
// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
obj.display();
obj.sort_by_frequency();
System.out.print("Before sort by frequency\n");
//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
obj.display();
}
}``````

#### Output

``````Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL``````
``````//Include namespace system
using System;
// C# Program
// Sort the linked list elements by node frequency

class Node
{
public int data;
public Node next;
public Node(int data)
{
//Set node value
this.data = data;
this.next = null;
}
}
class Frequency
{
public int key;
public int counter;
public Frequency next;
public Frequency(int key, int size)
{
//Set node value
this.key = key;
this.counter = size;
this.next = null;
}
}
{
public Node tail;
//Class constructor
{
this.tail = null;
}
//insert node at last of linke list
{
//Create a node
Node node = new Node(data);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
public void display()
{
{
return;
}
while (temp != null)
{
{
Console.Write(" →");
}
Console.Write(" " + temp.data);
//visit to next node
temp = temp.next;
}
Console.Write(" → NULL\n");
}
public Frequency add_frequency(Frequency collection, int key, int counter)
{
Frequency element = new Frequency(key, counter);
if (element == null)
{
Console.Write("Memory overflow\n");
}
else
{
if (collection == null)
{
return element;
}
else if (collection.counter >= counter)
{
//When need to add node at beginning
element.next = collection;
return element;
}
else
{
Frequency temp = collection;
while (temp != null && temp.next != null && temp.next.counter < counter)
{
//visit to next node
temp = temp.next;
}
element.next = temp.next;
temp.next = element;
}
}
return collection;
}
//Count and delete node which value is equal to front node
public int count_and_delete()
{
//Define some auxiliary variables
Node auxiliary = null;
Node back = null;
int counter = 0;
while (current != null)
{
if (current.data == key)
{
//When get delete node node
auxiliary = current;
//node counter
counter = counter + 1;
}
else
{
back = current;
}
//visit to next node
current = current.next;
if (auxiliary != null)
{
//When Deleted node exists
{
// When delete first node
// head visit to next node
}
else
{
// Deleted node are exist in intermediate or last position of linked list
// Before delete node, there left node is connecting to next upcoming node
back.next = current;
}
auxiliary.next = null;
//free node
auxiliary = null;
}
}
return counter;
}
public void sort_by_frequency()
{
{
}
else
{
Frequency collection = null;
Frequency temp = null;
int counter = 0;
int key = 0;
//Set last node to null
this.tail = null;
//Count node frequency and arrange in sorted order
while (current != null)
{
key = current.data;
counter = count_and_delete();
}
while (collection != null)
{
counter = collection.counter;
key = collection.key;
while (counter > 0)
{
counter--;
}
temp = collection;
//visit to next node
collection = collection.next;
//Free node
temp.next = null;
temp = null;
}
}
}
public static void Main(String[] args)
{
Console.Write("Before sort by frequency\n");
// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
obj.display();
obj.sort_by_frequency();
Console.Write("Before sort by frequency\n");
//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
obj.display();
}
}``````

#### Output

``````Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL``````
``````<?php
// Php Program
// Sort the linked list elements by node frequency

class Node
{
public \$data;
public \$next;

function __construct(\$data)
{
//Set node value
\$this->data = \$data;
\$this->next = null;
}
}
class Frequency
{
public \$key;
public \$counter;
public \$next;

function __construct(\$key, \$size)
{
//Set node value
\$this->key = \$key;
\$this->counter = \$size;
\$this->next = null;
}
}
{
public \$tail;
//Class constructor
function __construct()
{
\$this->tail = null;
}
//insert node at last of linke list
{
//Create a node
\$node = new Node(\$data);
{
\$this->tail = \$node;
}
else
{
\$this->tail->next = \$node;
\$this->tail = \$node;
}
}
public	function display()
{
{
return;
}
while (\$temp != null)
{
{
echo " →";
}
echo " ". \$temp->data;
//visit to next node
\$temp = \$temp->next;
}
echo " → NULL\n";
}
{
\$element = new Frequency(\$key, \$counter);
if (\$element == null)
{
echo "Memory overflow\n";
}
else
{
if (\$collection == null)
{
return \$element;
}
else if (\$collection->counter >= \$counter)
{
//When need to add node at beginning
\$element->next = \$collection;
return \$element;
}
else
{
\$temp = \$collection;
while (\$temp != null && \$temp->next != null && \$temp->next->counter < \$counter)
{
//visit to next node
\$temp = \$temp->next;
}
\$element->next = \$temp->next;
\$temp->next = \$element;
}
}
return \$collection;
}
//Count and delete node which value is equal to front node
public	function count_and_delete()
{
//Define some auxiliary variables
\$auxiliary = null;
\$back = null;
\$counter = 0;
while (\$current != null)
{
if (\$current->data == \$key)
{
//When get delete node node
\$auxiliary = \$current;
//node counter
\$counter = \$counter + 1;
}
else
{
\$back = \$current;
}
//visit to next node
\$current = \$current->next;
if (\$auxiliary != null)
{
//When Deleted node exists
{
// When delete first node
// head visit to next node
}
else
{
// Deleted node are exist in intermediate or last position of linked list
// Before delete node, there left node is connecting to next upcoming node
\$back->next = \$current;
}
\$auxiliary->next = null;
//free node
\$auxiliary = null;
}
}
return \$counter;
}
public	function sort_by_frequency()
{
{
}
else
{
\$collection = null;
\$temp = null;
\$counter = 0;
\$key = 0;
//Set last node to null
\$this->tail = null;
//Count node frequency and arrange in sorted order
while (\$current != null)
{
\$key = \$current->data;
\$counter = \$this->count_and_delete();
}
while (\$collection != null)
{
\$counter = \$collection->counter;
\$key = \$collection->key;
while (\$counter > 0)
{
\$counter--;
}
\$temp = \$collection;
//visit to next node
\$collection = \$collection->next;
//Free node
\$temp->next = null;
\$temp = null;
}
}
}
}

function main()
{
echo "Before sort by frequency\n";
// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
\$obj->display();
\$obj->sort_by_frequency();
echo "Before sort by frequency\n";
//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
\$obj->display();
}
main();``````

#### Output

``````Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL``````
``````// Node Js Program
// Sort the linked list elements by node frequency
class Node
{
constructor(data)
{
//Set node value
this.data = data;
this.next = null;
}
}
class Frequency
{
constructor(key, size)
{
//Set node value
this.key = key;
this.counter = size;
this.next = null;
}
}
{
//Class constructor
constructor()
{
this.tail = null;
}
//insert node at last of linke list
{
//Create a node
var node = new Node(data);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
display()
{
{
return;
}
while (temp != null)
{
{
process.stdout.write(" →");
}
process.stdout.write(" " + temp.data);
//visit to next node
temp = temp.next;
}
process.stdout.write(" → NULL\n");
}
{
var element = new Frequency(key, counter);
if (element == null)
{
process.stdout.write("Memory overflow\n");
}
else
{
if (collection == null)
{
return element;
}
else if (collection.counter >= counter)
{
//When need to add node at beginning
element.next = collection;
return element;
}
else
{
var temp = collection;
while (temp != null && temp.next != null && temp.next.counter < counter)
{
//visit to next node
temp = temp.next;
}
element.next = temp.next;
temp.next = element;
}
}
return collection;
}
//Count and delete node which value is equal to front node
count_and_delete()
{
//Define some auxiliary variables
var auxiliary = null;
var back = null;
var counter = 0;
while (current != null)
{
if (current.data == key)
{
//When get delete node node
auxiliary = current;
//node counter
counter = counter + 1;
}
else
{
back = current;
}
//visit to next node
current = current.next;
if (auxiliary != null)
{
//When Deleted node exists
{
// When delete first node
// head visit to next node
}
else
{
// Deleted node are exist in intermediate or last position of linked list
// Before delete node, there left node is connecting to next upcoming node
back.next = current;
}
auxiliary.next = null;
//free node
auxiliary = null;
}
}
return counter;
}
sort_by_frequency()
{
{
}
else
{
var collection = null;
var temp = null;
var counter = 0;
var key = 0;
//Set last node to null
this.tail = null;
//Count node frequency and arrange in sorted order
while (current != null)
{
key = current.data;
counter = this.count_and_delete();
}
while (collection != null)
{
counter = collection.counter;
key = collection.key;
while (counter > 0)
{
counter--;
}
temp = collection;
//visit to next node
collection = collection.next;
//Free node
temp.next = null;
temp = null;
}
}
}
}

function main()
{
process.stdout.write("Before sort by frequency\n");
// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
obj.display();
obj.sort_by_frequency();
process.stdout.write("Before sort by frequency\n");
//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
obj.display();
}
main();``````

#### Output

``````Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL``````
``````#  Python 3 Program
#  Sort the linked list elements by node frequency

class Node :

def __init__(self, data) :
# Set node value
self.data = data
self.next = None

class Frequency :

def __init__(self, key, size) :
# Set node value
self.key = key
self.counter = size
self.next = None

# Class constructor
def __init__(self) :
self.tail = None

# insert node at last of linke list
# Create a node
node = Node(data)
self.tail = node
else :
self.tail.next = node
self.tail = node

def display(self) :
print("\nEmpty linked list\n", end = "")
return

print("Linked List : ", end = "")
while (temp != None) :
print(" →", end = "")

print(" ", temp.data, end = "")
# visit to next node
temp = temp.next

print(" → NULL\n", end = "")

def add_frequency(self, collection, key, counter) :
element = Frequency(key, counter)
if (element == None) :
print("Memory overflow\n", end = "")
else :
if (collection == None) :
return element

elif(collection.counter >= counter) :
# When need to add node at beginning
element.next = collection
return element
else :
temp = collection
while (temp != None and temp.next != None and temp.next.counter < counter) :
# visit to next node
temp = temp.next

element.next = temp.next
# add element into given collection
temp.next = element

return collection

# Count and delete node which value is equal to front node
def count_and_delete(self) :
# Define some auxiliary variables
auxiliary = None
back = None
counter = 0
while (current != None) :
if (current.data == key) :
# When get delete node node
auxiliary = current
# node counter
counter = counter + 1
else :
back = current

# visit to next node
current = current.next
if (auxiliary != None) :
# When Deleted node exists
#  When delete first node
#  head visit to next node
else :
#  Deleted node are exist in intermediate or last position of linked list
#  Before delete node, there left node is connecting to next upcoming node
back.next = current

auxiliary.next = None
# free node
auxiliary = None

return counter

def sort_by_frequency(self) :
print("\n Empty linked List", end = "")
else :
collection = None
temp = None
counter = 0
key = 0
# Set last node to null
self.tail = None
# Count node frequency and arrange in sorted order
while (current != None) :
key = current.data
counter = self.count_and_delete()

while (collection != None) :
counter = collection.counter
key = collection.key
while (counter > 0) :
counter -= 1

temp = collection
# visit to next node
collection = collection.next
# Free node
temp.next = None
temp = None

def main() :
print("Before sort by frequency\n", end = "")
#  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
obj.display()
obj.sort_by_frequency()
print("Before sort by frequency\n", end = "")
# 9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
obj.display()

if __name__ == "__main__": main()``````

#### Output

``````Before sort by frequency
Linked List :   2 →  6 →  7 →  6 →  3 →  6 →  2 →  3 →  1 →  7 →  3 →  6 →  7 →  1 →  5 →  6 →  9 →  3 → NULL
Before sort by frequency
Linked List :   9 →  5 →  1 →  1 →  2 →  2 →  7 →  7 →  7 →  3 →  3 →  3 →  3 →  6 →  6 →  6 →  6 →  6 → NULL``````
``````#  Ruby Program
#  Sort the linked list elements by node frequency

class Node

# Define the accessor and reader of class Node
attr_accessor :data, :next

def initialize(data)
# Set node value
self.data = data
self.next = nil
end
end
class Frequency

# Define the accessor and reader of class Frequency
attr_accessor :key, :counter, :next

def initialize(key, size)

# Set node value
self.key = key
self.counter = size
self.next = nil
end
end

# Class constructor
def initialize()

self.tail = nil
end
# insert node at last of linke list

# Create a node
node = Node.new(data)

self.tail = node
else

self.tail.next = node
self.tail = node
end
end
def display()

return
end
while (temp != nil)

print(" →")
end
print(" ", temp.data)
# visit to next node
temp = temp.next
end
print(" → NULL\n")
end

element = Frequency.new(key, counter)
if (element == nil)

print("Memory overflow\n")
else

if (collection == nil)

return element
elsif(collection.counter >= counter)

# When need to add node at beginning
element.next = collection
return element
else

temp = collection
while (temp != nil && temp.next != nil && temp.next.counter < counter)

# visit to next node
temp = temp.next
end
element.next = temp.next
# add element into given collection
temp.next = element
end
end
return collection
end
# Count and delete node which value is equal to front node
def count_and_delete()

# Define some auxiliary variables
auxiliary = nil
back = nil
counter = 0
while (current != nil)

if (current.data == key)

# When get delete node node
auxiliary = current
# node counter
counter = counter + 1
else

back = current
end
# visit to next node
current = current.next
if (auxiliary != nil)

# When Deleted node exists

#  When delete first node
#  head visit to next node
else

#  Deleted node are exist in intermediate or last position of linked list
#  Before delete node, there left node is connecting to next upcoming node
back.next = current
end
auxiliary.next = nil
# free node
auxiliary = nil
end
end
return counter
end
def sort_by_frequency()

else

collection = nil
temp = nil
counter = 0
key = 0
# Set last node to null
self.tail = nil
# Count node frequency and arrange in sorted order
while (current != nil)

key = current.data
counter = self.count_and_delete()
end
while (collection != nil)

counter = collection.counter
key = collection.key
while (counter > 0)

counter -= 1
end
temp = collection
# visit to next node
collection = collection.next
# Free node
temp.next = nil
temp = nil
end
end
end
end
def main()

print("Before sort by frequency\n")
#  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
obj.display()
obj.sort_by_frequency()
print("Before sort by frequency\n")
# 9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
obj.display()
end
main()``````

#### Output

``````Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
``````
``````// Scala Program
// Sort the linked list elements by node frequency

class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
class Frequency(var key: Int,
var counter: Int,
var next: Frequency)
{
def this(key: Int, size: Int)
{
this(key, size, null);
}
}
var tail: Node)
{
//Class constructor
def this()
{
this(null, null);
}
//insert node at last of linke list
def add_node(data: Int): Unit = {
//Create a node
var node: Node = new Node(data);
{
this.tail = node;
}
else
{
this.tail.next = node;
this.tail = node;
}
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
{
print(" →");
}
print(" " + temp.data);
//visit to next node
temp = temp.next;
}
print(" → NULL\n");
}
def add_frequency(collection: Frequency, key: Int, counter: Int): Frequency = {
var element: Frequency = new Frequency(key, counter);
if (element == null)
{
print("Memory overflow\n");
}
else
{
if (collection == null)
{
return element;
}
else if (collection.counter >= counter)
{
//When need to add node at beginning
element.next = collection;
return element;
}
else
{
var temp: Frequency = collection;
while (temp != null && temp.next != null && temp.next.counter < counter)
{
//visit to next node
temp = temp.next;
}
element.next = temp.next;
temp.next = element;
}
}
return collection;
}
//Count and delete node which value is equal to front node
def count_and_delete(): Int = {
//Define some auxiliary variables
var auxiliary: Node = null;
var back: Node = null;
var counter: Int = 0;
while (current != null)
{
if (current.data == key)
{
//When get delete node node
auxiliary = current;
//node counter
counter = counter + 1;
}
else
{
back = current;
}
//visit to next node
current = current.next;
if (auxiliary != null)
{
//When Deleted node exists
{
// When delete first node
// head visit to next node
}
else
{
// Deleted node are exist in intermediate or last position of linked list
// Before delete node, there left node is connecting to next upcoming node
back.next = current;
}
auxiliary.next = null;
//free node
auxiliary = null;
}
}
return counter;
}
def sort_by_frequency(): Unit = {
{
}
else
{
var collection: Frequency = null;
var temp: Frequency = null;
var counter: Int = 0;
var key: Int = 0;
//Set last node to null
this.tail = null;
//Count node frequency and arrange in sorted order
while (current != null)
{
key = current.data;
counter = count_and_delete();
}
while (collection != null)
{
counter = collection.counter;
key = collection.key;
while (counter > 0)
{
counter -= 1;
}
temp = collection;
//visit to next node
collection = collection.next;
//Free node
temp.next = null;
temp = null;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
print("Before sort by frequency\n");
// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
obj.display();
obj.sort_by_frequency();
print("Before sort by frequency\n");
//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
obj.display();
}
}``````

#### Output

``````Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL``````
``````// Swift 4 Program
// Sort the linked list elements by node frequency

class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
//Set node value
self.data = data;
self.next = nil;
}
}
class Frequency
{
var key: Int;
var counter: Int;
var next: Frequency? ;
init(_ key: Int, _ size: Int)
{
//Set node value
self.key = key;
self.counter = size;
self.next = nil;
}
}
{
var tail: Node? ;
//Class constructor
init()
{
self.tail = nil;
}
//insert node at last of linke list
{
//Create a node
let node: Node? = Node(data);
{
self.tail = node;
}
else
{
self.tail!.next = node;
self.tail = node;
}
}
func display()
{
{
return;
}
print("Linked List : ", terminator: "");
while (temp != nil)
{

print(temp!.data,"→ " ,terminator: "");
//visit to next node
temp = temp!.next;
}
print(" NULL\n", terminator: "");
}
func add_frequency(_ collection: Frequency? , _ key : Int, _ counter: Int) -> Frequency?
{
let element: Frequency? = Frequency(key, counter);
if (element == nil)
{
print("Memory overflow\n", terminator: "");
}
else
{
if (collection == nil)
{
return element;
}
else if (collection!.counter >= counter)
{
//When need to add node at beginning
element!.next = collection;
return element;
}
else
{
var temp: Frequency? = collection;
while (temp != nil && temp!.next != nil && temp!.next!.counter < counter)
{
//visit to next node
temp = temp!.next;
}
element!.next = temp!.next;
temp!.next = element;
}
}
return collection;
}
//Count and delete node which value is equal to front node
func count_and_delete() -> Int
{
//Define some auxiliary variables
var auxiliary: Node? = nil;
var back: Node? = nil;
var counter: Int = 0;
while (current != nil)
{
if (current!.data == key)
{
//When get delete node node
auxiliary = current;
//node counter
counter = counter + 1;
}
else
{
back = current;
}
//visit to next node
current = current!.next;
if (auxiliary != nil)
{
//When Deleted node exists
{
// When delete first node
// head visit to next node
}
else
{
// Deleted node are exist in intermediate or last position of linked list
// Before delete node, there left node is connecting to next upcoming node
back!.next = current;
}
auxiliary!.next = nil;
//free node
auxiliary = nil;
}
}
return counter;
}
func sort_by_frequency()
{
{
print("\n Empty linked List", terminator: "");
}
else
{
var collection: Frequency? = nil;
var temp: Frequency? = nil;
var counter: Int = 0;
var key: Int = 0;
//Set last node to null
self.tail = nil;
//Count node frequency and arrange in sorted order
while (current != nil)
{
key = current!.data;
counter = self.count_and_delete();
}
while (collection != nil)
{
counter = collection!.counter;
key = collection!.key;
while (counter > 0)
{
counter -= 1;
}
temp = collection;
//visit to next node
collection = collection!.next;
//Free node
temp!.next = nil;
temp = nil;
}
}
}
}
func main()
{
print("Before sort by frequency\n", terminator: "");
// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
obj.display();
obj.sort_by_frequency();
print("Before sort by frequency\n", terminator: "");
//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
obj.display();
}
main();``````

#### Output

``````Before sort by frequency
Linked List : 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 →  NULL
Before sort by frequency
Linked List : 9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 →  NULL``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.