Chapter 22 - Lists, Stacks, Queues, and Priority Queues

Question 1

In object-oriented thinking, what is a data structure?

Answer 1

A data structure is a collection of data organized in some fashion. In object-oriented thinking, a data structure, also known as a container or container object, is an object that stores other objects, referred to as data or elements.

Question 2

What is the Java Collections Framework?

Answer 2

The Java collections framework (JCF) is a set of classes and interfaces that implement commonly reusable collection data structures

Question 3

The Java Collections Framework supports two types of containers. What are these two types?

Answer 3

One for storing a collection of elements is simply called a collection.
The other, for storing key/value pairs, is called a map.

Question 4

What are the three different kinds of collections data structures?

Answer 4

1. Sets store a group of nonduplicate elements.
2. Lists store an ordered collection of elements.
3. Queues store objects that are processed in first-in, first-out fashion.

Question 5

Which package are the Java Collections Framework classes grouped in?

Answer 5

They’re all grouped in the java.util package.

Question 6

What are the concrete classes in the Java Collections Framework?

Answer 6

TreeSet, HashSet, LinkedHashSet, Vector, Stack, ArrayList, LinkedList, and PriorityQueue

Question 7

Which of the concrete classes in the Java Collections Framework implement the java.lang.Clonable interface and the java.io.Serializable interface?

Answer 7

All classes except java.util.PriorityQueue implement the Clonable interface.
All classes implement the Serializable interface.

Question 8

What is an iterator?

Answer 8

Each collection has an Iterator object that can be used to traverse all the elements in the collection.
The Collection interface extends the Iterable interface. The Iterable interface defines the iterator method, which returns an iterator. Methods:
next() : gives access to next element
hasNext() : true if there are elements yet to be read
remove() : removes the last element returned by the iterator.

Question 9

Describe the List interface.

Answer 9

The List interface extends the Collection interface and defines a collection for storing elements in a sequential order. To create a list, use on of its two concrete classes: ArrayList or LinkedList.
The List interface contains methods for storing elements in sequence, and permits duplicates.

Question 10

What does the listIterator method of the List interface do?

Answer 10

listIterator() returns an instance of ListIterator. The ListIterator interface extends the Iterator interface to add bidirectional traversal of the list. The methods are:
add(object) : Adds the specified object to the list.
hasPrevious() : Returns true if this list iterator has more elements when traversing backward.
nextIndex() : Returns the index of the next element.
previous() : Returns the previous element in this list iterator.
previousIndex() : Returns the index of the previous element.
set() : Replaces the last element returned by the previous or next method with the specified element.

Question 11

When should you use an ArrayList, and when should you use a LinkedList?

Answer 11

ArrayList is efficient for retrieving elements and LinkedList is efficient for inserting and removing elements at the beginning of the list. Both have the same performance for inserting and removing elements in the middle or at the end of the list. The type of work you need to do should tell you which list to use.

Question 12

Does an ArrayList automatically grow/shrink?

Answer 12

An ArrayList automatically grows. It’s always at least as large as the list size.
An ArrayList does not automatically shrink. You can (and often should) use the trimToSize() method to reduce the array capacity to the size of the list.

Question 13

If you must traverse a LinkedList, how should you do it?

Answer 13

The get(i) method is available for a linked list, but it is a time-consuming operation. Do not use it to traverse all the elements in a list. Instead you should use an iterator. Note that a for-each loop uses an iterator implicitly.

Do not do this:
for(int i = 0; i < linkedList.size(); i++) {
- doSomeThing linkedList.get(i);
}

Instead, do this:
for(listElementType e: linkedList) {
- doSomeThing e;
}

Question 14

What is the Comparator interface?

Answer 14

Comparator can be used to compare the objects of a class that doesn't implement Comparable.
You can define a comparator to compare the elements of different classes. To do so, define a class that implements the java.util.Comparator interface. The Comparator interface has two methods, compare and equals.

public int compare(T element1, T element2)
returns a negative value if element1 is less than element2, a positive value if element1 is greater than element2, and zero if they are equal.

public boolean equals(Object element)
Returns true if the specified object is also a comparator and imposes the same ordering as this comparator.

Question 15

Explain the terms “natural order” and “comparator”.

Answer 15

Comparing elements using the Comparable interface is referred to as comparing using natural order, and comparing elements using the Comparator interface is referred to as comparing using comparator.

Question 16

What is the java.util.Collections class for? (not the Collection interface)

Answer 16

The Collections class contains static methods to perform common operations in a collection and a list.
For working with lists, the Collections class contains the static methods:
sort, binarySearch, reverse, shuffle, copy, and fill.
For working with collections, the Collections class contains the static methods:
max, min, disjoint, and frequency.

Question 17

How can you randomly reorder the elements of a list?

Answer 17

You can use the shuffle method (one of many useful methods in the Collections class) like this:
List list = Arrays.asList(“yellow”, “red”, “green”, “blue”);
Collections.shuffle(list);
The list is now randomly shuffled.

Question 18

Describe the Vector and Stack classes.

Answer 18

The Vector and Stack classes were supported before the Java Collections Framework was introduced in Java 1.2. They contain synchronized methods for accessing data. Synchronized methods can prevent data corruption when a vector/stack is accessed and modified by two or more threads concurrently.
Except for the synchronized methods, Vector is the same as ArrayList. ArrayList is much faster if you don’t need synchronized methods.

Question 19

What is the difference between a queue and a priority queue?

Answer 19

A queue is a first-in, first-out data structure. Elements are appended to the end of the queue and are removed from the beginning of the queue.
In a priority queue, elements are assigned priorities. When accessing elements, the element with the highest priority is removed first.

Question 20

Describe the Queue interface.

Answer 20

The Queue interface extends java.util.Collection with additional insertion, extraction, and inspection operations.
The offer method is used to add an element to the queue. This method is similar to the add method in the Collection interface, but the offer method is preferred for queues. Methods:

offer(element: E) : Inserts an element into the queue.
poll() : Retrieves and removes the head of this queue, or null if this queue is empty.
remove() : Retrieves and removes the head of this queue and throws an exception if this queue is empty.
peek() : Retrieves, but does not remove, the head of this queue, returning null if this queue is empty.
element() : Retrieves, but does not remove, the head of this queue, throwing an exception if this queue is empty.

Question 21

Describe the Deque interface and the LinkedList class, and their connection.

Answer 21

The LinkedList class implements the Deque interface, which extends the Queue interface. Therefore, you can use LinkedList to create a queue. LinkedList is ideal for queue operations because it is efficient for inserting and removing elements from both ends of a list.
Deque supports element insertion and removal at both ends. The name deque is short for "double-ended queue" and is usually pronounced "deck". The methods addFirst(e), removeFirst(), addLast(e), removeLast, getFirst(), and getLast() are defined in the Deque interface.

Question 22

How does the PriorityQueue class set the priority of elements?

Answer 22

By default, a priority queue orders its elements according to their natural ordering using Comparable. The element with the least value is assigned the highest priority and thus is removed from the queue first. If there are several elements with the same highest priority, the tie is broken arbitrarily.
You can also specify and ordering using Comparator in the constructor PriorityQueue(initialCapacity, comparator).

Question 23

Which of the following statements are true?

A. The Collection interface is the root interface for manipulating a collection of objects.
B. The Collection interface provides the basic operations for adding and removing elements in a collection.
C. The AbstractCollection class is a convenience class that provides partial implementation for the Collection interface.
D. Some of the methods in the Collection interface cannot be implemented in the concrete subclass. In this case, the method would throw java.lang.UnsupportedOperationException, a subclass of RuntimeException.
E. All interfaces and classes in the Collections framework are declared using generic type since JDK 1.5.

Answer 23

All are true

Question 24

Which of the following methods are in the Collection interface?

A. clear()
B. isEmpty()
C. size()
D. getSize()

Answer 24

All but D

Question 25

Which of the following methods are in the Collection interface?

A. add(o: E)
B. addAll(c: Collection)
C. contains(o: Object): boolean
D. containsAll(c: Collection): boolean

Answer 25

All

Question 26

Which of the following methods are in the Collection interface?

A. remove(o: E): boolean
B. removeAll(c: Collection): boolean
C. delete(o: E): boolean
D. deleteAll(c: Collection): boolean

Answer 26

A and B

Question 27

For an instance of Collection, you can obtain its iterator using ____

A. c.getIterator()
B. c.iterator()
C. c.iterators()
D. c.iterable()

Answer 27

B. c.iterator()

Question 28

The iterator() method is defined in the ____ interface.

A. Iterator
B. Collection
C. Iterable
D. ArrayList

Answer 28

C. Iterable

Question 29

The iterator() method returns an instance of the ___ interface.

A. Iterator
B. Collection
C. Iterable
D. ArrayList

Answer 29

A. Iterator

Question 30

Which of the following statements are true?

A. java.util.List inherits all the methods from java.util.Collection. Additionally, it contains new methods for manipulating a list.
B. The AbstractList class provides a partial implementation for the List interface.
C. ArrayList is a concrete implementation of List using an array.
D. LinkedList is a concrete implementation of List using a linked list. LinkedList contains all the methods in List and additional new methods for manipulating a linked list.
E. ListIterator is a subinterface of Iterator and it provides the methods to support bi-directional traversal of a list.

Answer 30

All are true

Question 31

Which of the following statements are true?

A. An ArrayList can grow automatically.
B. An ArrayList can shrink automatically.
C. You can reduce the capacity of an ArrayList by invoking the trimToSize() method on the list.
D. You can reduce the capacity of a LinkedList by invoking the trimToSize() method on the list.

Answer 31

The correct answer is AC

Explanation: A LinkedList does not have excess capacity.

Question 32

Which of the following are true?

A. You can insert an element anywhere is an arraylist.
B. You can insert an element anywhere is a linked list.
C. You can use a linked list to improve efficiency for adding and removing elements at the beginning of a list.
D. You should use an array list if your application does not require adding and removing elements at the beginning of a list.

Answer 32

All are true

Question 33

Suppose list1 is an ArrayList and list2 is a LinkedList. Both contains 1 million double values. Analyze the following code:

A:
for (int i = 0; i

Answer 33

A. Code fragment A runs faster than code fragment B.

Question 34

Suppose ArrayList x contains three strings [Beijing, Singapore, Tokyo]. Which of the following methods will cause runtime errors?

A. x.get(2)
B. x.set(3, "New York");
C. x.get(3)
D. x.remove(3)
E. x.size()

Answer 34

The correct answer is BCD

Explanation: There is no element at index 3.

Question 35

What will be displayed by the following code?
        List list = new ArrayList();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        for (int i = 0; i

Answer 35

The correct answer is C
Explanation: Before the loop, the list is [A, B, C, D]. After invoking list.remove(0), the list becomes [B, C, D] and size becomes 3. Invoking remove(1) now deletes C from the list. The list becomes [B, D]. Now the list size is 2 and i is 2. So the loop ends.

Remember that the method remove(e) retrieves an element in addition to removing it.

Question 36

Which of the following statements are correct.

A. When you create an array using new int[10], an array object is created with ten integers of value 0.
B. When you create an array using new int[10], an array object is created with no values in the array.
C. When you create an ArrayList using new ArrayList(), an ArrayList object is created with no elements in the ArrayList object.
D. When you create an array using int[] x = new int[10], x.length() is 10.
E. When you create an array using ArrayList x = new ArrayList(10), x.size() is 10.

Answer 36

A, C and D are correct

Question 37

Which of the following statements are true?

A. The Comparable interface contains the compareTo method with the signature “public int compareTo(Object)”.
B. The Comparator interface contains the compare method with the signature “public int compare(Object, Object)”.
C. A Comparable object can compare this object with the other object.
D. A Comparator object contains the compare method that compares two objects.

Answer 37

All are true

Question 38

Which of the following is correct to sort the elements in a list lst?

A. lst.sort()
B. Collections.sort(lst)
C. Arrays.sort(lst)
D. new LinkedList(new String[]{“red”, “green”, “blue”})

Answer 38

B is correct

Question 39

Which of the following statements are true?

A. Collections.shuffle(list) returns a new list while the original list is not changed.
B. Collections.reverse(list) returns a new list while the original list is not changed.
C. Collections.sort(list) returns a new list while the original list is not changed.
D. Collections.nCopies(int, Object) returns a new list that consists of n copies of the object.

Answer 39

D is true

Question 40

To create a set that consists of string elements “red”, “green”, and “blue”, use

A. new HashSet({"red", "green", "blue"})
B. new HashSet(new String[]{"red", "green", "blue"})
C. new HashSet(Arrays.asList(new String[]{"red", "green", "blue"}))
D. new LinkedHashSet(Arrays.asList(new String[]{"red", "green", "blue"}))
E. new Set(Arrays.asList(new String[]{"red", "green", "blue"}))

Answer 40

C and D are correct

Question 41

java.util.Vector is a subtype of ___

A. java.util.ArrayList
B. java.util.LinkedList
C. java.util.AbstractList
D. java.util.Vector
E. java.util.List

Answer 41

C and E are correct

Question 42

Which of the following statements are true?

A. java.util.LinkedList implements the java.util.Queue interface.
B. java.util.ArrayList implements the java.util.Queue interface.
C. java.util.HashSet implements the java.util.Queue interface.
D. java.util.LinkedHashSet implements the java.util.Queue interface.
E. java.util.PriorityQueue implements the java.util.Queue interface.

Answer 42

A and E are true

Question 43

Which of the following statements are true?

A. A PriorityQueue orders its elements according to their natural ordering using the Comparable interface if no Comparator is specified.
B. A PriorityQueue orders its elements according to the Comparator if a Comparator is specified in the constructor.
C. The priority of a PriorityQueue cannot be changed once a PriorityQueue is created.D. The priority of a PriorityQueue cannot be reversed once a PriorityQueue is created.

Answer 43

A and B are true

Question 44

What is list after the following code is executed?

ArrayList list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.remove(2);
System.out.println(list);

A. [1, 2, 3, 4, 5]
B. [2, 3, 4, 5]
C. [1, 3, 4, 5]
D. [1, 2, 4, 5]
E. [1, 2, 3, 4]

Answer 44

D. [1, 2, 4, 5]

Question 45

What is the difference between the Comparable and the Comparator interfaces? How do you decide which to use?

Answer 45

Implementing Comparable means “I can compare myself with another object.” This is typically useful when there’s a single natural default comparison.

Implementing Comparator means “I can compare two other objects.” This is typically useful when there are multiple ways of comparing two instances of a type - e.g. you could compare people by age, name etc.

When your class implements Comparable it is defining the natural ordering of that object. That method is contractually obligated (though not demanded) to be in line with other methods on that object, such as a 0 should always be returned for objects when the .equals() comparisons return true.

A Comparator is it’s own definition of how to compare two objects, and can be used to compare objects in a way that might not align with the natural ordering.

In short, there isn’t much difference. They are both ends to similar means. In general implement comparable for natural order, (natural order definition is obviously open to interpretation), and write a comparator for other sorting or comparison needs.