JavaScript program to sort a linked list of 0, 1 and 2

In this tutorial, we will learn a JavaScript program to sort a linked list of 0, 1 and 2. Sorting algorithms are essential for any programming language, and JavaScript is no exception. Sorting a linked list of 0s, 1s, and 2s is a common problem developers face in coding interviews and real-world applications.

So, let’s dive into how to sort a linked list of 0, 1, and 2 using JavaScript programming.

What is sorting?

Sort is the process of arranging elements in a specific order (ascending or descending). It is a fundamental operation in computer science and has numerous applications in real-world scenarios. Sorting algorithms are used to organize data for efficient searches, reduce redundancy, and optimize space and time complexity.

Here are some examples of sorting in JavaScript:

Example 1 - Sort an array of numbers in ascending order:

Input: ar[]= [5, 3, 8, 1, 2, 9]
Output: [1, 2, 3, 5, 8, 9]

Example 2 - Sort an array of strings alphabetically:

Input: ['apple', 'banana', 'orange', 'grape']
Output: ['apple', 'banana', 'grape', 'orange']

What is a linked list?

A linked list is a linear data structure consisting of nodes linked together by pointers. Each node contains a data element and a reference to the next node in the list. Linked lists are often used in dynamic data structures where the size of the data changes frequently.

Problem Statement

The goal is to arrange and display the linked list consisting of 0, 1 and 2 in order. Let us understand it with an example:

Example

Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL 
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL
Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL 

Algorithm for sorting the linked list of 0, 1 and 2

Steps to sort linked list of 0, 1 and 2 using counting sort algorithm -

Step 1 - Define a function sortList(head) that takes as input the head of the linked list.

STEP2 - Initialize a count array count[] of size 3, with all elements equal to 0.

STEP 3 - Traverse the linked list and increment the count of the node data at the corresponding index in the array.

STEP 4 - Traverse the linked list again and replace the node data with the lowest index value with a count greater than 0.

Step 5 - Reduce the node data count for each replacement.

Step 6 - Print the linked list before and after sorting.

Now let us try to understand the above algorithm with an example of implementing it using JavaScript.

Example

The following JavaScript program sorts a linked list containing 0, 1, and 2 using the counting sort algorithm. The algorithm first counts the frequency of occurrence of 0, 1, and 2 in the list, and then updates the value of the node in the list based on the count of each value.

/* Link list node */
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
   }
   push(new_data) {
      const new_node = new Node(new_data);
      new_node.next = this.head;
      this.head = new_node;
   }
   printList() {
      let currentNode = this.head;
      let value = "";
      while (currentNode !== null) {
         value += currentNode.data + " -> ";
         currentNode = currentNode.next;
      }
      console.log(value + "null");
   }
   sortList() {
      const count = [0, 0, 0]; // Initialize count of '0', '1' and '2' as 0
      let ptr = this.head;
      while (ptr !== null) {
         count[ptr.data] += 1;
         ptr = ptr.next;
      }
      ptr = this.head;
      let i = 0;
      while (ptr !== null) {
         if (count[i] === 0) {
            ++i;
         } else {
            ptr.data = i;
            --count[i];
            ptr = ptr.next;
         }
      }
   }
}
const linkedList = new LinkedList();
linkedList.push(0);
linkedList.push(1);
linkedList.push(0);
linkedList.push(2);
linkedList.push(1);
linkedList.push(1);
linkedList.push(2);
linkedList.push(1);
linkedList.push(2);
console.log("Before sorting:");
linkedList.printList();
linkedList.sortList();
console.log("After sorting:");
linkedList.printList();

in conclusion

Overall, the above Javascript program demonstrates an efficient way to sort a linked list containing only 0, 1, and 2 using counting techniques. The algorithm has a time complexity of O(n) and a space complexity of O(1), making it the optimal solution for this particular sorting problem.

The above is the detailed content of JavaScript program to sort a linked list of 0, 1 and 2. For more information, please follow other related articles on the PHP Chinese website!