import java.util.Scanner;

class Node {
    private int data;
    private Node next;

    public Node (int value, Node ref){
        data = value;
        next = ref;
    }

    public int getData(){
        return data;
    }

    public Node getNextReference(){
        return next;
    }

    public void setNextReference(Node value){
        next = value;
    }
}
class LinkedList{
    private Node head;
    private Node tail;

    public LinkedList() {
        head = null;
        tail = null;
    }

    public void insertAtBack(int word){
        if (head == null){
            head = new Node(word, null);
            tail = head;
        }
        else{
            Node tempref = tail;
            tail = new Node (word, null);
            tempref.setNextReference(tail);
        }
    }

    public void insertAtFront (int word){
        Node tempref = new Node (word, null);

        if (head == null){
            head = tempref;
            tail = head;
        }
        else{
            tempref.setNextReference(head);
            head = tempref;
        }

    }   

    public boolean isEmpty(){
        if (head == null){
            return true;
        }
        else {
            return false;
        }
    }

    public void removeFromFront() {
        if (head == null)
        {
            System.out.println ("List is Empty");
        }
        else {
            Node tempref = head;
            head = head.getNextReference();
            tempref.setNextReference(null);
            tempref = null;
        }
    }  

    public void removeFromBack(){
        if (head != null & head == tail) {
            head = null;
            tail = head;
        }
        else if (head!= null){
            Node prev = head; 
            Node curr = head;
            while (curr != tail){

                prev = curr;
                curr = curr.getNextReference();
            }

            prev.setNextReference(null);
            tail = prev;
        }
    }  

    public int getMaxValue(){
        Node tempref = head;
        int  max = -1000;
        while (tempref != null){
            int value = tempref.getData();
            if (value > max){
                max = value;
            }
            tempref = tempref.getNextReference();
        }
        return max;
    }

    public Node getMaxReference(int value){
        Node tempref = head;
        while (tempref.getData()!=value)  {
            tempref = tempref.getNextReference();
        }
        return tempref;
    }   

    public void maxToBack(){  // inserts the maximum value to the end of the list
        if (head != null){
            int max = getMaxValue();
            Node maxad = getMaxReference (max);
            if (head != tail){
                if (head == maxad){
                    removeFromFront();
                    insertAtBack(max);
                }
                else if (tail != maxad){
                    Node curr= head;
                    Node prev = head;
                    while (curr != maxad){
                        prev = curr;
                        curr = curr.getNextReference();
                    }
                    prev.setNextReference(curr.getNextReference());
                    insertAtBack(max);
                }
            }
        }
    }

    public void bubbleSort(){
        boolean flag = true;
        Node last = null;
        int count = 0, count1 = 0;
        while (last != head.getNextReference() && flag){
            flag = false;
            Node pprev = head, prev = head;
            Node curr = head.getNextReference();
            count++;
            while (curr!= last){
                count1++;
                if (curr != null && curr.getData() < prev.getData()){
                    if (prev == head){
                        prev.setNextReference(curr.getNextReference());
                        curr.setNextReference(prev);
                        head = curr;
                    }
                    else{
                        prev.setNextReference(curr.getNextReference());
                        curr.setNextReference(prev);
                        pprev.setNextReference(curr);
                        if (curr == tail){
                            tail = prev;
                        }
                    }
                    flag = true;
                    pprev = curr;
                    curr = prev.getNextReference();
                }
                else{
                    pprev = prev;
                    prev = curr;
                    curr = curr.getNextReference();
                }
            }
            last = prev;
            System.out.println("After Pass#" + count);
            printList();

        }
        System.out.println ("Number of passes = " + count);
        System.out.println ("Number of comparisons = " + count1);
        System.out.println("\n");

    }

    public void printList(){
        if (head == null){
            System.out.println ("The List is Empty");
        }
        else {
            Node tempref = head;
            System.out.println("The values so far in the list : ");
            while (tempref != null) {
                System.out.print(tempref.getData());
                tempref = tempref.getNextReference();
                if (tempref != null) {
                    System.out.print (" --> ");
                }
            }
            System.out.println("\n");
        }
    }
}

public class LinkedListTestMethods {
    public static void Menu(){
        System.out.println ("1 - Insert At Back ");
        System.out.println ("2 - Insert At Front");
        System.out.println ("3- Remove From Front");
        System.out.println ("4- Remove From Back");
        System.out.println ("5- Move Maximum to Back");
        System.out.println ("6 - Bubble Sort");
        System.out.println ("7 - Quit");
    }

    public static void main (String args []) {
        System.out.println ("Linked Lists");
        Scanner scanner = new Scanner (System.in);
        Scanner scanner1 = new Scanner (System.in);
        int choice = 0, status = 0, entry = 0;
        boolean flag = true;
        LinkedList list = new LinkedList();
        while (flag){
            Menu();
            status = 0;
            try {
                choice = Integer.parseInt(scanner.nextLine());
            }
            catch (Exception e){
                System.out.println("Integers Only - Enter Again");
                status = 1;
            }
            if (choice == 1){
                System.out.println ("Enter the value?");
                entry = scanner1.nextInt();
                list.insertAtBack(entry);
            }
            else if (choice == 2){
                System.out.println ("Enter the value?");
                entry = scanner1.nextInt();
                list.insertAtFront(entry);
            }
            else if (choice == 3){
                list.removeFromFront();
            }
            else if (choice == 4){
                list.removeFromBack();
            }
            else if (choice == 5){
                list.maxToBack();
            }
            else if (choice == 6){
                list.bubbleSort();
            }
            else if (choice == 7){
                flag = false;
                System.out.println ("End of Program");
            }
            else if (status == 0){
                System.out.println ("Invalid Entry - Choose From Menu");
            }
            list.printList();
        }
    }
}