Write a java program to insert one element in a singly linked list before a given element. Your program will print the original list, request the user to put in an element to be inserted, and an...

Write a java program to insert one element in a singly linked list before a given element. Your program will print the original list, request the user to put in an element to be inserted, and an element to indicate the location of the insertion, then print the final list after the insertion is done. If the element doesn't exist in the list, add the new element to the end of the list. No duplicate values are allowed to store in list. Once you done insertion operation (at least 10 element inserted) in your list, Draw a binary search tree and AVL tree ( show all rotations ) as per your inserted values .

Use the following as your test cases to evaluate whether your program works correctly:

If you have a linked list: 6à2à7.

• With user input 8 and 2. Your list should become 6à8à2à7:


• With user input 8 and -1. Your list should become 6à2à7à8:


• Let suppose your final linked list . 6à2à7à8à5à10à1à9à3