1) A) Write a method to find the maximum value of a list of integers. The node d
ID: 3684020 • Letter: 1
Question
1)
A) Write a method to find the maximum value of a list of integers. The node definition is given below. Assume your method signature is public static int listMax(IntNode node) and that node will not be null initially. Your solution may not use recursion.
public class IntNode {
private int value;
private IntNode next;
public int getInt() { return value; }
public void setInt(int v) { value = v; }
public IntNode getNext() { return next; }
public void setNext(IntNode n) { next = n; }
}
B) In this unit, we introduced three kinds of list ADTs, including the actual indexed list ADT provided by Java (see table). There are two primary ways such a table could be implemented: arrays and linked structures. Based on your knowledge of these data structures, complete the following table:
On the table, make bold the operations which have a different order. Give a brief explanation for the difference below.
C) In order to properly answer the last question, several assumptions may have been made. What did you assume? For example, did write your Big-Oh in terms of array resizing? Or did you assume that the array didn't need to resize?
Method Description Array Big-Oh Linked Big-Oh void add(E element) Adds element to the end of the list. void add(int index, E element) Inserts element at the index. E get(int index) Returns element at the index. void remove(int index) Removes element at the index. void remove(E object) Removes first occurrence of the object. void set(int index, E element) Replaces element at the index. int size() Returns number of elements in the list.Explanation / Answer
C) In order to properly answer the last question, several assumptions may have been made. What did you assume? For example, did write your Big-Oh in terms of array resizing? Or did you assume that the array didn't need to resize?
A classic example is storing your data in an array vs a linked list. An array is constant lookup time, but adding new elements requires the array to be resized (potentially). A list is O(n) lookup time, but very fast for adding and removing elements from the head and tail of the list. Your program may not care that it takes longer to find an item in a list, but absolutely requires the most optimal add/remove time, in which case you'd look at a list or other data structure that's not backed by an array.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.