class Link {

    private class Node {

        int data;

        Node next;

        public Node(int x) {

            data = x;

        }

        public void addNode(Node newNode){

            if(this.next == null){

                this.next = newNode;

            }else{

                this.next.addNode(newNode);

            }

        }

    }

    public Node root;

    public void add(int data){

        Node newNode = new Node(data);

        if(this.root==null){

            this.root=newNode;

        }else{

            this.root.addNode(newNode);

        }

    }

    public void printLink(){

        Node head = this.root;

        while(head!=null) {

            System.out.println(head.data);

            head = head.next;

        }

    }

    public void insertionSortList() {

        Node head = this.root;

        if(head==null || head.next==null)

            return;

        Node dummy = new Node(-1);

        dummy.next = head;

        Node cur = head.next;

        head.next = null;

        while(cur != null) {

            Node pre = dummy;

            Node temp = cur.next;

            while (pre.next!=null && cur.data > pre.next.data){

                pre = pre.next;

            }

            cur.next = pre.next;

            pre.next = cur;

            cur = temp;

        }

        this.root=dummy.next;

        return;

    }

}

import java.lang.reflect.Array;

public class Main {

    public static void main(String[] args) {

       Link all = new Link();

       int data[] = new int[]{5,4,3,2,1};

//       for(int i = 0;i < data.length;i++){

//           data[i] = i;

//       }

//       data[0] = 0;

//       int j = data.length-1;

//       for(int i = 1;i < data.length;i++){

//           data[i] = j;

//           j--;

//       }

//        int j = data.length;

//        for(int i = 0;i < data.length;i++){

//            data[i] = j;

//            j--;

//        }

        for(int i = 0;i < data.length;i++){

            System.out.println(data[i]);

        }

       for(int i = 0;i < data.length;i++){

           all.add(data[i]);

       }

        long startTime=System.currentTimeMillis();

        all.insertionSortList();

        long endTime=System.currentTimeMillis();

        System.out.println(endTime-startTime);

        System.out.println("==================");

        all.printLink();

    }

}