if I have this java program how can write " Insertion sort"

import java.util.*;

public class LinkedList {

class ListNode {

protected T value;

protected ListNode next;

public ListNode(T val, ListNode nxt) {

value = val;

next = nxt;

}

public ListNode(T val) {

this(val, null);

}

public ListNode() {

this(null, null);

}

}

public class ListIterator {

private ListNode curr, previous;

public ListIterator() {

reset();

}

public void reset() {

previous = head;

curr = head.next;

}

public boolean hasNext() {

return (curr != null);

}

public T next() {

if (!hasNext())

throw new NoSuchElementException();

T retval = curr.value;

curr = curr.next;

previous = previous.next;

return retval;

}

public T get() {

if (!hasNext())

throw new NoSuchElementException();

return curr.value;

}

public void set(T val) {

if (!hasNext())

throw new NoSuchElementException();

curr.value = val;

}

public void add(T val) {

previous.next = new ListNode(val, curr);

previous = previous.next;

// curr = previous.next; // 2nd option

numVals++;

}

public void remove() {

if (!hasNext())

throw new NoSuchElementException();

previous.next = curr.next;

curr = curr.next;

numVals--;

}

}

protected ListNode head;

protected int numVals;

public LinkedList() {

head = new ListNode();

clear();

}

public void clear() {

head.next = null;

numVals = 0;

}

public boolean isEmpty() {

return (numVals == 0);

}

public int size() {

return numVals;

}

public void add(int index, T val) {

if (index < 0 || index > numVals)

throw new NoSuchElementException();

ListNode p = head;

for (int i = 0; i < index; i++)

p = p.next;

// ListNode newnode = new ListNode(val);

// newnode.next = p.next;

// p.next = newnode;

p.next = new ListNode(val, p.next);

numVals++;

}

public void add(T val) {

add(numVals, val);

}

public T get(int index) {

ListNode p = head.next;

for (int i = 0; i < index; i++)

p = p.next;

return p.value;

}

public void set(int index, T val) {

ListNode p = head.next;

for (int i = 0; i < index; i++)

p = p.next;

p.value = val;

}

public T remove(int index) {

ListNode p = head;

for (int i = 0; i < index; i++)

p = p.next;

T retVal = p.next.value;

p.next = p.next.next;

numVals--;

return retVal;

}

public void println() {

System.out.println("Current size = " + size());

if (isEmpty())

System.out.println("list is empty ");

else {

for (ListNode p = head.next; p != null; p = p.next)

System.out.print(p.value + " ");

System.out.println();

}

}

public boolean remove(T val) {

ListNode p = head;

while (p.next != null && !val.equals(p.next.value))

p = p.next;

if (p.next == null)

return false;

else {

p.next = p.next.next;

numVals--;

return true;

}

}

public int indexOf(T val) {

int index = 0;

ListNode current = head.next;

while (current != null) {

if (current.value.equals(val)) {

return index;

}

index++;

current = current.next;

}

return -1;

}

public boolean equals(LinkedList rhs) {

ListNode curr1 = head.next;

ListNode curr2 = rhs.head.next;

if (curr1 == null && curr2 == null)

return true;

if (curr1 == null || curr2 == null)

return false;

while (curr1 != null && curr2 != null) {

if (!curr1.value.equals(curr2.value))

return false;

curr1 = curr1.next;

curr2 = curr2.next;

}

if (curr1 != null || curr2 != null)

return false;

return true;

}

public boolean equals(LinkedList lhs, LinkedList rhs) {

ListNode head1 = lhs.head.next;

ListNode head2 = rhs.head.next;

if (head1 == null && head2 == null)

return true;

if (head1 == null || head2 == null)

return false;

while (head1 != null && head2 != null) {

if (!head1.value.equals(head2.value))

return false;

head1 = head1.next;

head2 = head2.next;

}

// all elements are same

if (head1 == null && head2 == null)

return true;

// length are not equal

else

return false;

}

public void printReverse(ListNode node) {

if (node == null)

return;

printReverse(node.next);

System.out.print(node.value + " ");

}

// (7) Write a method for the LinkedList class called boolean removeLast(T val)

public boolean removeLast(T val) {

int index = 1, valIndex = -1;

ListNode temp = head.next;

while (temp != null) {

if (temp.value.equals(val)) {

valIndex = index;

}

temp = temp.next;

index++;

}

if (valIndex == -1) // val is not in list

return false;

// now valIndex is the index of last occurence of val

// head is val

if (valIndex == 0) {

head = head.next;

} else {

// now traversing till valIndex-1

int k = 0;

temp = head;

while (k < valIndex - 1) {

temp = temp.next;

k++;

}

// removing elements at index valIndex

// temp pointing to node at index valIndex-1

temp.next = temp.next.next;

numVals--;

}

return true;

}

public static void main(String[] args) {

LinkedList list = new LinkedList();

LinkedList rhs = new LinkedList();

LinkedList lhs = new LinkedList();

// System.out.println("Current size = " + list.size());

// if (list.isEmpty())

// System.out.println("list is empty ");

list.println();

list.add("Chris");

list.add("MattB");

list.add("Joe");

list.println();

list.add(1, "Mattk");

list.add(0, "Phil");

list.add(list.size(), "Collin");

list.println();

list.set(4, "Alex");

list.set(0, "Nebal");

list.set(list.size() - 1, "Natalie");

list.println();

System.out.println("The third element = " + list.get(3));

list.remove(2);

list.remove(0);

list.println();

rhs.add("Alex");

rhs.add("MattB");

rhs.add("Chris");

rhs.add("Natalie");

lhs.add("Alex");

lhs.add("MattB");

lhs.add("Chris");

lhs.add("Nebal");

System.out.println(list.indexOf("Alex"));

System.out.println(list.equals(rhs));

System.out.println(list.equals(rhs, lhs));

list.printReverse(list.head);

System.out.println();

System.out.println(list.removeLast("Alex"));

list.println();

}

}