Linked List

Write a program to sort the elements in the linked list using insertion sort

Pinterest LinkedIn Tumblr

Insertion sort is a sorting algorithm uses to sort items in the array or linked list. It can sort the elements in ascending order or descending order. Insertion sort is a simple sorting algorithm. It works efficiently for small data sets. Insertion sort builds the sorted array. It is best suitable for nearly sorted arrays and a small set of elements.

Write a program to sort the elements in the linked list using insertion sort.

Algorithm Explanation

Take unsorted array and divide into two parts. sorted array and unsorted array.
Take an element from a unsorted array and add to the sorted array repeatedly.
Arrange the elements when to add elements into the sorted array.
When unsorted array becomes empty, the sorted array contains all the elements sorted.

Source Code

package com.dsacode.DataStructre.linkedlist;
 
import java.util.ArrayList;
import java.util.Hashtable;
 
public class IntersectionList {
    public static ArrayList < Integer > findIntersection(ArrayList < Integer > s1, ArrayList < Integer > s2) {
        Hashtable < Integer, Integer > hashTable = new Hashtable < Integer, Integer >();
        ArrayList < Integer > intersection = new ArrayList < Integer >();
        for(int i = 0; i < s1.size(); i++) {
            if(s1.get(i) != null) {
                if(hashTable.get(s1.get(i)) != null) {
                    hashTable.put(s1.get(i), hashTable.get(s1.get(i)) + 1);
                } else {
                    hashTable.put(s1.get(i), 1);
                }
            }
        }
         
        for(int i = 0; i < s2.size(); i++) {
            int s2Val = s2.get(i);
            int value;
            if(hashTable.get(s2Val) != null) {
                value = hashTable.get(s2Val);
            } else {
                continue;
            }
             
            if(hashTable.get(s2Val)!= 0) {
                hashTable.put(s2Val, value - 1);
                intersection.add(s2Val);
            }
        }
     
        return intersection;
    }
     
      
     
    public static void main(String[] args) {
        ArrayList < Integer > a1 = new ArrayList < Integer >();
        a1.add(1);
        a1.add(1);
        a1.add(1);
        a1.add(4);
        System.out.println("Items from the first list: " + a1.toString());
        ArrayList < Integer > a2 = new ArrayList < Integer >();
        a2.add(2);
        a2.add(2);
        a2.add(2);
        a2.add(1);
        a2.add(4);
        System.out.println("Items from the Secound list: " + a1.toString());
         
        ArrayList < Integer > a3 = findIntersection(a1, a2);
        System.out.println("Intersection  Items: "+a3.toString());
    }
}

Output

Print the list of items: 21->52->33->67->NULL

Write A Comment