public class linkedList<Type> {
	
    private theNode<Type> head;
	
    public linkedList () {
	head = null;
    }
    
    public boolean isEmpty () {
        return head == null;
    }

	public addStart (Type item) {
		head = new theNode<Type> (item, head);
	}
    
    public Type removeStart () {
        Type temp = getFirst();
        head = head.next;
        return temp;
    }

	public addEnd (Type item) {
		if (head==null) addStart(item);
		else {
			theNode<Type> temp = head;
			while( temp.next != null ) temp=temp.next;
			temp.next = new theNode<Type> (item ,null);
		}
	}

	public int searchElement (Type target) {
		theNode<Type> temp = head;
		int location=0;
		while( temp.next != target ) {
			location++;
			temp = temp.next;
		}
	}

    public int getSize () {
        theNode<Type> temp = head;
        int size=0;
        while( temp.next != null ) {
            size++;
            temp = temp.next;
        }
    }
    
    public Type getFirst () {
        return head.data;
    }

    public Type getData (int position) {
        theNode<Type> temp = head;
        for (int i=1; i<position; i++) temp = temp.next;
        return temp.data;
    }
    
    public void insert (Type key, Type toInsert) {
        if (head == null) return;
        if (head.data.equals(toInsert)) {
            addStart(toInsert);
            return;
        }
        theNode<Type> prev = null;
        theNode<Type> current = head;
        while (current != null && !current.data.equals(key)) {
            prev = current;
            current = current.next;
        }
        if (current != null) {
            prev.next = new theNode<Type> (toInsert, current);
        }
    }

    public void exchange (Type tarKey, Type desKey) {
        theNode<Type> current = head, last, beforeTar, beforeDes, tar, des;
        while(current != null) {
            if(current.data.equals(tarKey)) {
                beforeTar = last;
                tar = current;
            } else {
                if(current.data.equals(desKey)) {
                    beforeDes = last;
                    des = current;
                }
            }
            last = current;
            current = current.next;
        }
        des.next = beforeTar.next.next;
        tar.next = beforeDes.next.next;
        beforeTar.next = des;
        beforeDes.next = tar;
    }
    
    public void del (Type key) {
        if (head.data.equals(key)) {
            head = head.next;
        }
        theNode prev = null;
        theNode current = head;
        while (current != null && !current.data.equals(key)) {
            prev = current;
            current = current.next;
        }
        prev.next = current.next;
    }
    
    public theNode<Type> sortList (theNode<Type> targetList) {
        if(head == null || head.next == null) {
            return;
        }
        int total = 0, midCounter = 0;
        theNode<Type> temp = head,part1 = head,part2 = head,cuttingTemp = null;
        while (temp != null) {
            temp = temp.next;
            total++;
        }
        int mid = total/2;
        boolean alreadyCut = false;
        while (part2 != null) {
            midCounter++;
            if (mid == midCounter) {
                cuttingTemp = part2.next;
                part2.next == null;
                alreadyCut = !alreadyCut;
            }
            if (alreadyCut) {
                part2 = cuttingTemp;
            } else {
                part2 = part2.next;
            }
        }
        theNode<Type> desList = mergeAndSortData (sortList (part1), sortList(cuttingTemp));
    }
    
    public theNode<Type> mergeAndSortData (theNode<Type> desListPart1, theNode<Type> desListPart2) {
        theNode<Type> thePart1 = desListPart1;
        theNode<Type> thePart2 = desListPart2;
        theNode<Type> theSortedHead = new theNode<Type> (100);
        theNode<Type> thePartNew = theSortedHead;
        while (thePart1 != null || thePart2 != null) {
            if (thePart1 == null) {
                thePartNew.next = new theNode<Type> (thePart2.data);
                thePart2 = thePart2.next;
                thePartNew = thePartNew.next;
            } else {
                if (thePart2 == null) {
                    thePartNew.next = new theNode<Type> (thePart1.data);
                    thePart1 = thePart1.next;
                    thePartNew = thePartNew.next;
                } else {
                    if (thePart1.data < thePart2.data) {
                        thePartNew.next = new theNode<Type> (thePart1.data);
                        thePart1 = thePart1.next;
                        thePartNew = thePartNew.next;
                    } else {
                        if (thePart1.data == thePart2.data) {
                            thePartNew.next = new theNode<Type> (thePart1.data);
                            thePartNew.next.next = new theNode<Type> (thePart2.data);
                            thePartNew = thePartNew.next.next;
                            thePart1 = thePart1.next;
                            thePart2 = thePart2.next;
                        } else {
                            thePartNew.next = new theNode<Type> (thePart2.data);
                            thePart2 = thePart2.next;
                            thePartNew = thePartNew.next;
                        }
                    }
                }
            }
        }
        return theSortedHead.next;
    }
    
}