EXPECTED OUTPUT

COMPLETE FOR JAVA

****************** Test Linked List Correctness ******************

Inserting 5 at front. Current list: [5]

Inserting 32 at end. Current list: [5 -> 32]

Inserting 16 at front. Current list: [16 -> 5 -> 32]

Inserting 61 after position 1. Current list: [16 -> 5 -> 61 -> 32]

Inserting 99 after tail. Current list: [16 -> 5 -> 61 -> 32 -> 99]

Deleting after position 1. Current list: [16 -> 5 -> 32 -> 99]

Deleting after position 2. Current list: [16 -> 5 -> 32]

Trying to delete after position 2: Cannot delete after tail.

Inserting 5 at front. Current list: [5 -> 16 -> 5 -> 32]

Inserting 32 at end. Current list: [5 -> 16 -> 5 -> 32 -> 32]

Inserting 16 at front. Current list: [16 -> 5 -> 16 -> 5 -> 32 -> 32]

Inserting 8 at front. Current list: [8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32]

Inserting 21 at end. Current list: [8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21]

Inserting 50 at end. Current list: [8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21 -> 50]

Inserting 32 at end. Current list: [8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21 -> 50 -> 32]

Inserting 66 at front. Current list: [66 -> 8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21 -> 50 -> 32]

Inserting 66 at front. Current list: [66 -> 66 -> 8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21 -> 50 -> 32]

Trying to remove duplicates from: Cannot remove duplicates unless sorted!

Sorted List: [5 -> 5 -> 8 -> 16 -> 16 -> 21 -> 32 -> 32 -> 32 -> 50 -> 66 -> 66]

Remove duplicates: [5 -> 8 -> 16 -> 21 -> 32 -> 50 -> 66]

Push odd indexes to the back: [5 -> 16 -> 32 -> 66 -> 8 -> 21 -> 50]

Inserting -12 at front. Current list: [-12 -> 5 -> 16 -> 32 -> 66 -> 8 -> 21 -> 50]

Push odd indexes to the back: [-12 -> 16 -> 66 -> 21 -> 5 -> 32 -> 8 -> 50]

Reversing List: [50 -> 8 -> 32 -> 5 -> 21 -> 66 -> 16 -> -12]

****************** Test Dynamic Array Correctness ******************

[0] Num elements: 1, Length: 1

[0, 5] Num elements: 2, Length: 2

[0, 5, 10] Num elements: 3, Length: 4

[0, 5, 10, 15] Num elements: 4, Length: 4

[0, 5, 10, 15, 20] Num elements: 5, Length: 8

[0, 5, 10, 15, 20, 25] Num elements: 6, Length: 8

[0, 5, 10, 15, 20, 25, 30] Num elements: 7, Length: 8

[0, 5, 10, 15, 20, 25, 30, 35] Num elements: 8, Length: 8

[0, 5, 10, 15, 20, 25, 30, 35, 40] Num elements: 9, Length: 16

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45] Num elements: 10, Length: 16

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] Num elements: 11, Length: 16

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55] Num elements: 12, Length: 16

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60] Num elements: 13, Length: 16

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65] Num elements: 14, Length: 16

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70] Num elements: 15, Length: 16

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75] Num elements: 16, Length: 16

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80] Num elements: 17, Length: 32

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75] Num elements: 16, Length: 32

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70] Num elements: 15, Length: 32

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65] Num elements: 14, Length: 32

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60] Num elements: 13, Length: 32

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55] Num elements: 12, Length: 32

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] Num elements: 11, Length: 32

[0, 5, 10, 15, 20, 25, 30, 35, 40, 45] Num elements: 10, Length: 32

[0, 5, 10, 15, 20, 25, 30, 35, 40] Num elements: 9, Length: 32

[0, 5, 10, 15, 20, 25, 30, 35] Num elements: 8, Length: 16

[0, 5, 10, 15, 20, 25, 30] Num elements: 7, Length: 16

[0, 5, 10, 15, 20, 25] Num elements: 6, Length: 16

[0, 5, 10, 15, 20] Num elements: 5, Length: 16

[0, 5, 10, 15] Num elements: 4, Length: 8

[0, 5, 10] Num elements: 3, Length: 8

[0, 5] Num elements: 2, Length: 4

[0] Num elements: 1, Length: 2

[] Num elements: 0, Length: 1

2 Linked List Your task is to complete the following functions in the LinkedList.h/LinkedList.java file: - void insertAfter(ListNode argNode, int value) for C++, or void insertAfter(ListNode argNode, int value) for Java: Function inserts a node with value value after the node argNode. You may assume that arg Node is not null. - void deleteAfter(ListNode argNode) for C++, or void deleteAfter(ListNode argNode) : Function deletes the node after argNode. You may assume that argNode is not null. - void selectionSort () : Function that sorts the linked list using selection sort method. - bool removeDuplicatesSorted() for C++, or boolean removeDuplicatesSorted(): 3 Function that checks whether or not the linked list is sorted in ascending order. If it is not sorted, then the function returns false. Otherwise, the function removes the duplicate occurrences of each number from the list (i.e., only one occurrence of each number remains). Then the function returns true. - void pushOddIndexesToTheBack () : Function that pushes all the odd indexes to the back of the linked list, starting with index 1 , then 3 , then 5 , and so on. - void reverse(): This function reverses a linked list in-place, i.e., without using any extra space (such as an array or another linked list) other than variables. Caution: For the last 4 methods, you CANNOT use any other data structure (linked list or arrays) for storage. You CAN ONLY use variables. Also on a linked list of length n : - the first two functions must have a complexity of O(1), Caution: For the last 4 methods, you CANNOT use any other data structure (linked list or arrays) for storage. You CAN ONLY use variables. Also on a linked list of length n : - the first two functions must have a complexity of O(1), - selection sort must achieve a complexity of O(n2) - removing the duplicates method must achieve a complexity of O(n) - pushing the odd indexes to the back must achieve a complexity of O(n) - reverse the linked list must achieve a complexity of O(n) 2.1 insertAfter An explanation video can be found in the lecture videos. Pseudo-code - create a newNode - newNodes's next points to argNode's next - argNodesnextpointstonewNode - if argNode is tail, then newNode becomes tail - increment size 2.2 deleteAfter An explanation video can be found in the lecture videos. Pseudo-code - if argNode is tail, then there is nothing to delete - else if argNode's next is tail, then - get rid of all references to tail (Java) or invoke delete (C++) - argNode becomes tail - decrement size - else - use a placeholder variable to point argNode's next - argNode's next points to placeholder's next - get rid of all references from placeholder (Java) or invoke delete (C++) - decrement size 2.3 Selection Sort Pseudo-code - You will use virtually the same idea as in a selection sort algorithm on arrays - Since random accesses are not possible, use three placeholder variables - iNode to point to the ListNode on which the outer loop i is iterating, minNode to point to the minimum valued node in the portion of the linked list starting from i all the way to the end, and j Node to point to the ListNode on which the outer loop j is iterating - Initially i Node points to head - Within the outer-loop, minNode is initially i Node and j Node is the node after iNode - Within the inner-loop, you compare the values of jNode and minNode and you set minNode to j Node, if the latter has a smaller value. Set jNode to its next node. - Once the inner loop terminates, you swap the values of i Node and minNode (if needed). Then, set iNode to its next node. 2.4 Removing Duplicates in Ascending Sorted List Pseudo-code - To check if the linked list is ascending sorted, use a loop with a place holder variable (similar to getNodeAt function). At any point, if the value of the placeholder node is larger than the value of the next node, then you return false, else move placeholder to its next node. - Once you are done with the above for-loop (and did not return false), it is guaranteed that the linked list is sorted. - Once again scan through the linked list using a loop and a placeholder. If the value of the placeholder equals the value of the next node a, then you can delete the duplicate value in the next node by calling deleteAfter on the placeholder, else move placeholder to its next node. 2.5 Pushing Odd Indexes to the End - If the input list is [581621325066], then after executing this function the list will become [516326682150] - If the input list is [12516326682150], then after executing this function the list will become [12166621532850] Pseudo-code - Scan through the linked list using a loop and a placeholder, but this time only loop over the even indexes 0,2,4,6, and so on. - Within the loop, insert the value in the node immediately after the placeholder at the end of the linked list and delete the node after the placeholder. Move placeholder to its next node. 2.6 Reversing a Linked List See assignment folder for an explanation video. Pseudo-code - Set prev to head, and set curr to head's next - As long as (curr != null) - Set tmp to curr's next, and set curr's next to prev - Set prev to curr, and set curr to tmp - Swap head and tail - Set tail's next to null 3 Dynamic Array Use the notes posted on Dynamic Array to implement the insertAtEnd and deleteLast methods in the DynamicArray.h/ DynamicArray.java files. 4 Correctness Use the TestCorrectness.cpp/ TestCorrectness.java files to test your code. The expected output is provided in ExpectedOutput file. You can use www. diff checker. com to tally the output. 5 Comparative Analysis Recall that for insertion, dynamic arrays have amortized O(1) complexity, whereas linked lists have worst case O(1) complexity. However, as shown in Fig. 1 below, dynamic arrays outperform linked lists. This is because of the way arrays and linked lists are stored in memory. Remember that an 6 array occupies a contiguous block in memory, whereas a linked list is scattered all through out. This makes arrays more cache friendly, as we bring in a larger chunk of the array into the cache from the RAM in one shot as opposed to linked lists. Hence, using arrays lead to fewer page faults, causing fewer accesses to the RAM, making them practically faster (or at least comparable)