"These questions concern the following definition of class List, intended to be used to represent a list of objects (note that the List class uses the standard ListNode class).
Code: Select all
Public class List {
/*** fields ***/
private ListNode first; //pointer to the first node
//in the list
private ListNode last; //pointer to the last node
//in the list
/*** methods ***/
public List ( ) {first = last = null} //constructor
public void addToEnd(Object ob) {
ListNode tmp = new ListNode (ob, null);
if (last != null) last.setNext(tmp);
last = tmp;
}
}
An empty list is intended to be represented by a List in which first and last are both null. A nonempty list is intended to be represented by a List in which:
- The first items in the list are stored in a linked list.
- first points to the first node in the linked list.
- last points to the last node in the linked list.
1. What is the problem with the implementation of the List class?
- The constructor is not implemented correctly.
- The types of first and last fields are wrong.
- The addToEnd method will not work correctly when the first value is added to the list.
- The addToEnd method will not work correctly when a value other than the first is added to the list.
- The addToEnd method will not work correctly when a duplicate value is added to the list.
2. Which of the following best characterizes the running time of the version of addToEnd given above for a list that initially contains n values?
- O(1)
- O(log n)
- O(n)
- O(n log n)
- O(n^2)"
Any thoughts?
