# 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;
}
//Add new node at end of linked list
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
{
//sorted add new node
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;
//add element into given collection
temp->next = element;
}
}
return collection;
}
//Display linked list element
void display(struct Node *head)
{
if (head == NULL)
{
printf("\n Empty linked list\n");
return;
}
struct Node *temp = head;
//iterating linked list elements
while (temp != NULL)
{
if (temp != head)
{
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;
//iterating linked list elements
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)
{
if (head == NULL)
{
printf("\n Empty linked List");
}
else
{
struct Frequency *collection = NULL;
struct Frequency *temp = NULL;
int counter = 0;
int key = 0;
struct Node *current = *head;
//set last node to null
*tail = NULL;
//Count node frequency and arrange in sorted order
while (current != NULL)
{
key = current->data;*head = count_and_delete( *head, &counter, key);
collection = add_frequency(collection, key, counter);
counter = 0;
}
while (collection != NULL)
{
counter = collection->counter;
key = collection->key;
while (counter > 0)
{
*tail = add_node( *tail, key);
if ( *head == NULL)
{
}
counter--;
}
temp = collection;
//visit to next node
collection = collection->next;
//Free node
temp->next = NULL;
free(temp);
temp = NULL;
}
}
}
int main()
{
struct Node *head = NULL;
struct Node *tail = NULL;
tail = add_node(tail, 6);
tail = add_node(tail, 7);
tail = add_node(tail, 6);
tail = add_node(tail, 3);
tail = add_node(tail, 6);
tail = add_node(tail, 2);
tail = add_node(tail, 3);
tail = add_node(tail, 1);
tail = add_node(tail, 7);
tail = add_node(tail, 3);
tail = add_node(tail, 6);
tail = add_node(tail, 7);
tail = add_node(tail, 1);
tail = add_node(tail, 5);
tail = add_node(tail, 6);
tail = add_node(tail, 9);
tail = add_node(tail, 3);
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);
if (this->head == NULL)
{
//When linked list empty add first node
this->tail = node;
}
else
{
//Add new node at end of linked list
this->tail->next = node;
this->tail = node;
}
}
//Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\nEmpty linked list\n";
return;
}
Node *temp = this->head;
cout << "Linked List : ";
//iterating linked list elements
while (temp != NULL)
{
if (temp != this->head)
{
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
{
//Sorted add new node
Frequency *temp = collection;
while (temp != NULL && temp->next != NULL && 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
int count_and_delete()
{
int key = this->head->data;
//Define some auxiliary variables
Node *current = this->head;
Node *auxiliary = NULL;
Node *back = NULL;
int counter = 0;
//iterating linked list elements
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 (this->head == auxiliary)
{
// 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()
{
if (this->head == NULL)
{
cout << "\n Empty linked List";
}
else
{
Frequency *collection = NULL;
Frequency *temp = NULL;
int counter = 0;
int key = 0;
Node *current = this->head;
//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();
collection = this->add_frequency(collection, key, counter);
}
// Add node in linked list by node frequency
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
public void add_node(int data)
{
//Create a node
Node node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
public void display()
{
if (this.head == null)
{
return;
}
Node temp = this.head;
System.out.print("Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
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
{
//Sorted add new node
Frequency temp = collection;
while (temp != null && temp.next != null && 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
public int count_and_delete()
{
int key = this.head.data;
//Define some auxiliary variables
Node current = this.head;
Node auxiliary = null;
Node back = null;
int counter = 0;
//iterating linked list elements
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 (this.head == auxiliary)
{
// 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()
{
if (this.head == null)
{
System.out.print("\n Empty linked List");
}
else
{
Frequency collection = null;
Frequency temp = null;
int counter = 0;
int key = 0;
Node current = this.head;
//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();
collection = add_frequency(collection, key, counter);
}
// Add node in linked list by node frequency
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
public void add_node(int data)
{
//Create a node
Node node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
public void display()
{
if (this.head == null)
{
return;
}
Node temp = this.head;
Console.Write("Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
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
{
//Sorted add new node
Frequency temp = collection;
while (temp != null && temp.next != null && 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
public int count_and_delete()
{
int key = this.head.data;
//Define some auxiliary variables
Node current = this.head;
Node auxiliary = null;
Node back = null;
int counter = 0;
//iterating linked list elements
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 (this.head == auxiliary)
{
// 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()
{
if (this.head == null)
{
Console.Write("\n Empty linked List");
}
else
{
Frequency collection = null;
Frequency temp = null;
int counter = 0;
int key = 0;
Node current = this.head;
//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();
collection = add_frequency(collection, key, counter);
}
// Add node in linked list by node frequency
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);
if (\$this->head == null)
{
//When linked list empty add first node
\$this->tail = \$node;
}
else
{
//Add new node at end of linked list
\$this->tail->next = \$node;
\$this->tail = \$node;
}
}
//Display linked list element
public	function display()
{
if (\$this->head == null)
{
echo "\nEmpty linked list\n";
return;
}
echo "Linked List : ";
//iterating linked list elements
while (\$temp != null)
{
if (\$temp != \$this->head)
{
echo " →";
}
echo " ". \$temp->data;
//visit to next node
\$temp = \$temp->next;
}
echo " → NULL\n";
}
public	function add_frequency(\$collection, \$key, \$counter)
{
\$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
{
//Sorted add new node
\$temp = \$collection;
while (\$temp != null && \$temp->next != null && \$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
public	function count_and_delete()
{
//Define some auxiliary variables
\$auxiliary = null;
\$back = null;
\$counter = 0;
//iterating linked list elements
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 (\$this->head == \$auxiliary)
{
// 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()
{
if (\$this->head == null)
{
echo "\n Empty linked List";
}
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();
\$collection = \$this->add_frequency(\$collection, \$key, \$counter);
}
// Add node in linked list by node frequency
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()
{
\$obj = new MyLinkedList();
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);
if (this.head == null)
{
//When linked list empty add first node
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
display()
{
if (this.head == null)
{
return;
}
var temp = this.head;
process.stdout.write("Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
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
{
//Sorted add new node
var temp = collection;
while (temp != null && temp.next != null && 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
count_and_delete()
{
var key = this.head.data;
//Define some auxiliary variables
var current = this.head;
var auxiliary = null;
var back = null;
var counter = 0;
//iterating linked list elements
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 (this.head == auxiliary)
{
// 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()
{
if (this.head == null)
{
process.stdout.write("\n Empty linked List");
}
else
{
var collection = null;
var temp = null;
var counter = 0;
var key = 0;
var current = this.head;
//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();
collection = this.add_frequency(collection, key, counter);
}
// Add node in linked list by node frequency
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()
{
var obj = new MyLinkedList();
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

# Node of LinkedList
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
def add_node(self, data) :
# Create a node
node = Node(data)
if (self.head == None) :
# When linked list empty add first node
self.tail = node
else :
# Add new node at end of linked list
self.tail.next = node
self.tail = node

# Display linked list element
def display(self) :
if (self.head == None) :
print("\nEmpty linked list\n", end = "")
return

print("Linked List : ", end = "")
# iterating linked list elements
while (temp != None) :
if (temp != self.head) :
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 :
# Sorted add new node
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
# iterating linked list elements
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
if (self.head == auxiliary) :
#  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

# unlink deleted node
auxiliary.next = None
# free node
auxiliary = None

return counter

def sort_by_frequency(self) :
if (self.head == None) :
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()
collection = self.add_frequency(collection, key, counter)

#  Add node in linked list by node frequency
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

# Node of LinkedList
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_reader :key, :counter, :next
attr_accessor :key, :counter, :next

def initialize(key, size)

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

# Define the accessor and reader of class MyLinkedList

# Class constructor
def initialize()

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

# Create a node
node = Node.new(data)
if (self.head == nil)

# When linked list empty add first node
self.tail = node
else

# Add new node at end of linked list
self.tail.next = node
self.tail = node
end
end
# Display linked list element
def display()

if (self.head == nil)

return
end
print("Linked List : ")
# iterating linked list elements
while (temp != nil)

if (temp != self.head)

print(" →")
end
print(" ", temp.data)
# visit to next node
temp = temp.next
end
print(" → NULL\n")
end
def add_frequency(collection, key, counter)

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

# Sorted add new node
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
# iterating linked list elements
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
if (self.head == auxiliary)

#  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
# unlink deleted node
auxiliary.next = nil
# free node
auxiliary = nil
end
end
return counter
end
def sort_by_frequency()

if (self.head == nil)

print("\n Empty linked List")
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()
collection = self.add_frequency(collection, key, counter)
end
#  Add node in linked list by node frequency
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);
if (this.head == null)
{
//When linked list empty add first node
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
def display(): Unit = {
if (this.head == null)
{
return;
}
var temp: Node = this.head;
print("Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
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
{
//Sorted add new node
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;
//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(): Int = {
var key: Int = this.head.data;
//Define some auxiliary variables
var current: Node = this.head;
var auxiliary: Node = null;
var back: Node = null;
var counter: Int = 0;
//iterating linked list elements
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 (this.head == auxiliary)
{
// 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 = {
if (this.head == null)
{
print("\n Empty linked List");
}
else
{
var collection: Frequency = null;
var temp: Frequency = null;
var counter: Int = 0;
var key: Int = 0;
var current: Node = this.head;
//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();
collection = add_frequency(collection, key, counter);
}
// Add node in linked list by node frequency
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 head: Node? ;
var tail: Node? ;
//Class constructor
init()
{
self.tail = nil;
}
//insert node at last of linke list
func add_node(_ data: Int)
{
//Create a node
let node: Node? = Node(data);
if (self.head == nil)
{
//When linked list empty add first node
self.tail = node;
}
else
{
//Add new node at end of linked list
self.tail!.next = node;
self.tail = node;
}
}
//Display linked list element
func display()
{
if (self.head == nil)
{
print("\nEmpty linked list\n", terminator: "");
return;
}
var temp: Node? = self.head;
print("Linked List : ", terminator: "");
//iterating linked list elements
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
{
//Sorted add new node
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;
//add element into given collection
temp!.next = element;
}
}
return collection;
}
//Count and delete node which value is equal to front node
func count_and_delete() -> Int
{
let key: Int = self.head!.data;
//Define some auxiliary variables
var current: Node? = self.head;
var auxiliary: Node? = nil;
var back: Node? = nil;
var counter: Int = 0;
//iterating linked list elements
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
if (self.head === auxiliary)
{
// 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()
{
if (self.head == nil)
{
print("\n Empty linked List", terminator: "");
}
else
{
var collection: Frequency? = nil;
var temp: Frequency? = nil;
var counter: Int = 0;
var key: Int = 0;
var current: Node? = self.head;
//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();
collection = self.add_frequency(collection, key, counter);
}
// Add node in linked list by node frequency
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.