Chapter 22 - Lists, Stacks, Queues, and Priority Queues Flashcards
In object-oriented thinking, what is a data structure?
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.
What is the Java Collections Framework?
The Java collections framework (JCF) is a set of classes and interfaces that implement commonly reusable collection data structures
The Java Collections Framework supports two types of containers. What are these two types?
One for storing a collection of elements is simply called a collection.
The other, for storing key/value pairs, is called a map.
What are the three different kinds of collections data structures?
- Sets store a group of nonduplicate elements.
- Lists store an ordered collection of elements.
- Queues store objects that are processed in first-in, first-out fashion.
Which package are the Java Collections Framework classes grouped in?
They’re all grouped in the java.util package.
What are the concrete classes in the Java Collections Framework?
TreeSet, HashSet, LinkedHashSet, Vector, Stack, ArrayList, LinkedList, and PriorityQueue
Which of the concrete classes in the Java Collections Framework implement the java.lang.Clonable interface and the java.io.Serializable interface?
All classes except java.util.PriorityQueue implement the Clonable interface.
All classes implement the Serializable interface.
What is an iterator?
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.
Describe the List interface.
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.
What does the listIterator method of the List interface do?
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.
When should you use an ArrayList, and when should you use a LinkedList?
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.
Does an ArrayList automatically grow/shrink?
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.
If you must traverse a LinkedList, how should you do it?
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;
}
What is the Comparator interface?
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.
Explain the terms “natural order” and “comparator”.
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.
What is the java.util.Collections class for? (not the Collection interface)
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 can you randomly reorder the elements of a list?
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.
Describe the Vector and Stack classes.
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.
What is the difference between a queue and a priority queue?
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.
Describe the Queue interface.
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.
Describe the Deque interface and the LinkedList class, and their connection.
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.
How does the PriorityQueue class set the priority of elements?
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).
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.
All are true
Which of the following methods are in the Collection interface?
A. clear()
B. isEmpty()
C. size()
D. getSize()
All but D
