Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

2 Linked List Your task is to complete the following functions in the LinkedList.java file: void insertAfter(ListNode argNode, int value) for Java: Function inserts a

2 Linked List Your task is to complete the following functions in the LinkedList.java file: void insertAfter(ListNode argNode, int value) for Java: Function inserts a node with value value after the node argNode. You may assume that argNode is not null. 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. 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 f alse. 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), selection sort must achieve a complexity of O(n 2 ) 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 newNodess next points to argNodes next argNodes next points to newNode 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 ARGNODES NEXT IS TAIL, THEN GET RID OF ALL REFERENCES TO TAIL (JAVA) argNode becomes tail 4 decrement size else use a placeholder variable to point argNodes next argNodes next points to placeholders next GET RID OF ALL REFERENCES FROM PLACEHOLDER (JAVA) 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 jNode to point to the ListNode on which the outer loop j is iterating Initially iNode points to head Within the outer-loop, minNode is initially iNode and jNode is the node after iNode Within the inner-loop, you compare the values of jNode and minNode and you set minNode to jNode, if the latter has a smaller value. Set jNode to its next node. Once the inner loop terminates, you swap the values of iNode 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 nodea , then you can delete the duplicate value in the next node by calling deleteAfter on the placeholder, else move placeholder to its next node. a output on JAVA should be this

: ****************** 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]

PLEASE SOLVE DELETEAFTER METHOD, I KEEP GETTING ERROR MESSAGE SAYING CANNOT READ VALUE BECAUSE ARGNODE.NEXT IS NULL

here is current code for delete after method:

public void deleteAfter(ListNode argNode) { // complete this method

if(argNode == tail) {

System.out.println("Cannot delete after tail");

}else if(argNode.next == tail) {

tail = null; argNode = tail; size--;

} else {

ListNode temp = argNode.next;

argNode.next = temp.next;

temp = null; size--;

}

}

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Concepts of Database Management

Authors: Philip J. Pratt, Mary Z. Last

8th edition

1285427106, 978-1285427102

More Books

Students also viewed these Databases questions

Question

How many Tables Will Base HCMSs typically have? Why?

Answered: 1 week ago

Question

What is the process of normalization?

Answered: 1 week ago