Chapter 24 Check Point Questions
Section 24.2
▼24.2.1
Suppose list is an instance of MyList, can you get an iterator for list using list.iterator()?
▼24.2.2
Can you create a list using new MyList()?
▼24.2.3
What methods in Collection are overridden as default methods in MyList?
▼24.2.4
What are the benefits of overriding the methods in Collection as
default methods in MyList?
Section 24.3
▼24.3.1
What are the limitations of the array data type?
▼24.3.2
MyArrayList is implemented using an array, and an array is a fixed-size data structure. Why is MyArrayList considered a dynamic data structure?
▼24.3.3
Show the length of the array in MyArrayList after each of the following statements is executed.
1 MyArrayList<Double> list = new MyArrayList<>(); 2 list.add(1.5); 3 list.trimToSize(); 4 list.add(3.4); 5 list.add(7.4); 6 list.add(17.4);
▼24.3.4
What is wrong if lines 11-12 in Listing 24.2, MyArrayList.java,
for (int i = 0; i < objects.length; i++)
add(objects[i]);
are replaced by
data = objects; size = objects.length;
▼24.3.5
If you change the code in line 33 in Listing 24.2, MyArrayList.java, from
E[] newData = (E[])(new Object[size * 2 + 1]);to
E[] newData = (E[])(new Object[size * 2]);the program is incorrect. Can you find the reason?
▼24.3.6
Will the MyArrayList class have memory leak if the following code in line 41 is deleted?
data = (E[])new Object[INITIAL_CAPACITY];
▼24.3.7
The get(index) method invokes the checkIndex(index) method
(lines 59-63 in Listing 24.2) to throw
an IndexOutOfBoundsException if the index is out of bounds.
Suppose the add(index, e) method is implemented as follows:
public void add(int index, E e) { checkIndex(index); // Same as lines 23-33 in Listing 24.2 MyArrayList.java }What will happen if you run the following code?
MyArrayList<> list = new MyArrayList<>(); list.add("New York");
Section 24.4
▼24.4.1
If a linked list does not contain any nodes, what are the values in head and tail?
▼24.4.2
If a linked list has only one node, is head == tail true?
List all cases in which head == tail is true.
▼24.4.3
Draw a diagram to show the linked list after each of the following statements is executed.
MyLinkedList<Double> list = new MyLinkedList<>(); list.add(1.5); list.add(6.2); list.add(3.4); list.add(7.4); list.remove(1.5); list.remove(2);
▼24.4.4
When a new node is inserted to the head of a linked list,
will the head and the tail be changed?
▼24.4.5
When a new node is appended to the end of a linked list, will
the head and the tail be changed?
▼24.4.6
Simplify the following code in Listing 24.5 using a conditional expression.
if (current != null) { result.append(", "); // Separate two elements with a comma } else { result.append("]"); // Insert the closing ] in the string }
▼24.4.7
Simplify the code for the removeLast() method by invoking the removeFirst()
method when the size is less than or equal to 1. Is the new code more efficient
in execution time?
▼24.4.8
What is the time complexity of the addFirst(e) and removeFirst() methods in MyLinkedList?
▼24.4.9
What would be the time complexity for the size()
method if the size data field is not used in MyLinkedList?
▼24.4.10
Suppose you need to store a list of elements. If the number of elements in the program is fixed, what data structure should you use? If the number of elements in the program changes, what data structure should you use?
▼24.4.11
If you have to add or delete the elements at the beginning of a list, should you use MyArrayList or MyLinkedList? If most of the operations on a list involve retrieving an element at a given index, should you use MyArrayList or MyLinkedList?
▼24.4.12
Both MyArrayList and MyLinkedList are used to store a list of objects. Why do we need both types of lists?
▼24.4.13
Implement the removeLast() method in a doubly
linked list in O(1) time.
Section 24.5
▼24.5.1
You can use inheritance or composition to design the data structures for stacks and queues. Discuss the pros and cons of these two approaches.
▼24.5.2
If LinkedList is replaced by ArrayList in lines 2-3 in Listing 24.6 GenericQueue.java, what will be the time complexity for the enqueue and dequeue methods?
▼24.5.3
Which lines of the following code are wrong?
1 List<String> list = new ArrayList<>(); 2 list.add("Tom"); 3 list = new LinkedList<>(); 4 list.add("Tom"); 5 list = new GenericStack<>(); 6 list.add("Tom");
Section 24.6
▼24.6.1
What is a priority queue?
▼24.6.2
What are the time complexity of the enqueue, dequeue , and getSize methods in MyProrityQueue?
▼24.6.3
Which of the following statements are wrong?
1 MyPriorityQueue<Object> q1 = new MyPriorityQueue<>(); 2 MyPriorityQueue<Number> q2 = new MyPriorityQueue<>(); 3 MyPriorityQueue<Integer> q3 = new MyPriorityQueue<>(); 4 MyPriorityQueue<Date> q4 = new MyPriorityQueue<>(); 5 MyPriorityQueue<> q5 = new MyPriorityQueue<>();