[Solved] COMP2140 Assignment2-An add method that takes a list2 and adds its values

When writing code for this course, follow the programming standards, available on this courses website on UM Learn. Failure to do so will result in the loss of marks.

What you should implement: Implement the following algorithms and methods (you can add any necessary private helper methods):

1. add(): In the LinkedList class implement an add method that takes a list2 and adds its values (not nodes) to the current list list1. Please consider these points:
   • Both lists are circular single linked list.
   • Both lists are ordered. Order of list1 must be preserved while adding values from list2.
   • The list2 should not change.

The following three methods are designed to familiarize you with linked list improvements.

2. convertCircularToOrdinary() In the LinkedList class convert a circular list to an ordinary linked list (a single linked list without dummy header or trailer).
   • The existing linkedList.java class is implemented for a circular linked list.
   • This conversion will only change address pointers; we will not rewrite insert or search functions for an ordinary linked list.
   • When the function returns, the last pointer of the LinkedList class will point to the first node in the list, and the last node will have a null for the forward (next) node.
3. convertOrdinaryToCircular() In the LinkedList class convert an ordinary linked list to a circular linked list.
   • This conversion will only change address pointers.
   • When the function returns, the last pointer of the LinkedList class will point to the last node in the list, and the last.next will point to the first node of the linked list.
4. reset(): Reset the linked list to an empty circular link list.
5. addDummies(): In the LinkedList class add a dummy header and a dummy trailer to the linked list. Use Integer.MIN VALUE and Integer.MAX VALUE as values.
6. hasDummies(): In the LinkedList class check if the linked list has a dummy header with Integer.MIN VALUE and a dummy trailer with Integer.MAX VALUE.
7. deleteOddNodes(): In the LinkedList class delete all nodes that have an odd item value.
   • Delete by reassigning pointers.
   • Do not create a new linked list.

Figure 1: An ordinary linked list

The following two methods are designed to show the efficiency of array operations when the data size is fixed.

8. testInsertion(): In A1<your last name><your first name>.java, write a method to insert size new integers into the list (for example, you can insert a dummy 1 every time), and record the time it takes to complete these insertions.
9. testInsertion()(version 2): In A1<your last name><your first name>.java, write a method to insert size new integers into the array (you can insert a dummy 1 every time), and record the time it takes to complete these insertions.

Reminder: These two insertion methods are overloaded; they have the same name but different signatures.

(https://www.geeksforgeeks.org/different-ways-method-overloading-java/)

The following two methods are designed to show the efficiency of Linked Lists when data size changes in time.

10. insertValue(): In A1<your last name><your first name>.java, insert the given value into the link list.
11. insertValue() (version 2): In A1<your last name><your first name>.java, insert the given value into the array. If the array size is exceeded, you must create a new array and copy the old array into the new array. Afterwards, insert the new item value to the new array.

The following two methods are designed to familiarize you with a well known linked list algorithm.

12. corrupt(): In the LinkedList.java write a method that corrupts a given ordinary linked list by changing the last nodes forward pointer (which is supposed to be null) to point to a node at the given index. In Figure 1 a clean list is shown. In Figure 2, its corrupted version is shown. The task in corrupt() is to convert a clean linked list to a corrupted one. The position to corrupt is determined by the line

index = r1.nextInt(list1.getSize()/2); which chooses the corruption index from the first half of the linked list.

13. findCorruption(): In the LinkedList.java write a method that finds if the linked list contains a loop (This is a popular software interview question).
    • In the main class, a sorted list is given as the parameter to this method (for ease of debugging). Do not use the sorted nature of the linked list to detect the corruption.
    • Do not store visited nodes to detect a loop. That would be a very lazy solution. If the linked list is big, you would store too much information.

Figure 2: A corrupted linked list

Concerns.

It is not optimal to have hard-coded parameters in your class such as final int list1Size = 1500;

Ideally, your main class should be passed an array of arguments. In this assignment, we are receiving list sizes (list1Size=1500 and list2Size=1300) from the argument array args and parsing them to integers with the following lines.

int list1Size = Integer.parseInt(args[0]); int list2Size = Integer.parseInt(args[1]);

Please avoid magical numbers in your code. There should be only ONE return per method. See the programming standards (under content/course documents) file on UMLearn, and follow the suggestions. Assignments will be graded by considering these standards. Your code must not give any warnings or errors when compiled and run.