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

1
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the Java Collections Framework?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the three different kinds of collections data structures?

A
  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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Which package are the Java Collections Framework classes grouped in?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the concrete classes in the Java Collections Framework?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is an iterator?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Describe the List interface.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does the listIterator method of the List interface do?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Does an ArrayList automatically grow/shrink?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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;
}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the Comparator interface?

A
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A
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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How can you randomly reorder the elements of a list?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Describe the Vector and Stack classes.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

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.

20
Q

Describe the Queue interface.

A

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.

21
Q

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

A
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.
22
Q

How does the PriorityQueue class set the priority of elements?

A

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).

23
Q

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.
A

All are true

24
Q

Which of the following methods are in the Collection interface?

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

A

All but D

25
Q

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

A

All

26
Q

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

A

A and B

27
Q

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

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

A

B. c.iterator()

28
Q

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

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

A

C. Iterable

29
Q

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

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

A

A. Iterator

30
Q

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.

A

All are true

31
Q

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.

A

The correct answer is AC

Explanation: A LinkedList does not have excess capacity.

32
Q

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.

A

All are true

33
Q

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

A

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

34
Q

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()
A

The correct answer is BCD

Explanation: There is no element at index 3.

35
Q
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
A

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.

36
Q

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.
A

A, C and D are correct

37
Q

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.

A

All are true

38
Q

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”})

A

B is correct

39
Q

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.

A

D is true

40
Q

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"}))
A

C and D are correct

41
Q

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
A

C and E are correct

42
Q

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.

A

A and E are true

43
Q

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.

A

A and B are true

44
Q

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]
A

D. [1, 2, 4, 5]

45
Q

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

A

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.