Several fundamental data types involve collections of objects. Specifically, the set of values is a collection of objects, and the operations revolve around adding, removing, or examining objects in the collection. In this section, we consider three such data types, known as the bag, the queue, and the stack. They differ in the specification of which object is to be removed or examined next.
APIs.
We define the APIs for bags, queues, and stacks. Beyond the basics, these APIs reflect two Java features: generics and iterable collections.
Array and resizing array implementations of collections.
- Fixed-capacity stack of strings. FixedCapacityStackOfString.java implements a fixed-capacity stack of strings using an array.
- Fixed-capacity generic stack. FixedCapacityStack.java implements a generic fixed-capacity stack.
- Array resizing stack. ResizingArrayStack.java implements a generic stack using a resizing array. With a resizing array, we dynamically adjust the size of the array so that it is both sufficiently large to hold all of the items and not so large as to waste an excessive amount of space. Wedouble the size of the array in push() if it is full; we halve the size of the array in pop() if it is less than one-quarter full.
- Array resizing queue. ResizingArrayQueue.java implements the queue API with a resizing array.
Linked lists.
A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list. To implement a linked list, we start with a nested class that defines the node abstractionprivate class Node {
Item item;
Node next;
} |
- Building a linked list. To build a linked list that contains the items to, be, and or, we create a Node for each item, set the item field in each of th
- Insert at the beginning. The easiest place to insert a new node in a linked list is at the beginning.
- Remove from the beginning. Removing the first node in a linked list is also easy.
- Insert at the end. To insert a node at the end of a linked list, we maintain a link to the last node in the list.
- Traversal. The following is the idiom for traversing the nodes in a linked list.
for (Node x = first; x != null; x = x.next) {
// process x.item
} |
Linked-list implementations of collections.
- Linked list implementation of a stack. Stack.java implements a generic stack using a linked list. It maintains the stack as a linked list, with the top of the stack at the beginning, referenced by an instance variable first. To push() an item, we add it to the beginning of the list; to pop()an item, we remove it from the beginning of the list.
- Linked list implementation of a queue. Program Queue.java implements a generic FIFO queue using a linked list. It maintains the queue as a linked list in order from least recently to most recently added items, with the beginning of the queue referenced by an instance variable firstand the end of the queue referenced by an instance variable last. To enqueue() an item, we add it to the end of the list; to dequeue() an item, we remove it from the beginning of the list.
- Linked list implementation of a bag. Program Bag.java implements a generic bag using a linked list. The implementation is the same as Stack.javaexcept for changing the name of push() to add() and removing pop().
Iteration.
To consider the task of implementing iteration, we start with a snippet of client code that prints all of the items in a collection of strings, one per line:Stack<String> collection = new Stack<String>();
...
for (String s : collection)
StdOut.println(s);
... |
This foreach statement is shorthand for the following while statement:Iterator<String> i = collection.iterator();
while (i.hasNext()) {
String s = i.next();
StdOut.println(s);
} |
To implement iteration in a collection:- Include the following import statement so that our code can refer to Java's java.util.Iterator interface:
import java.util.Iterator; |
- Add the following to the class declaration, a promise to provide an iterator() method, as specified in the java.lang.Iterable interface:
implements Iterable<Item> |
- Implement a method iterator() that returns an object from a class that implements the Iterator interface:
public Iterator<Item> iterator() {
return new ListIterator();
} |
- Implement a nested class that implements the Iterator interface by including the methods hasNext(), next(), and remove(). We always use an empty method for the optional remove() method because interleaving iteration with operations that modify the data structure is best avoided.
- The nested class ListIterator in Bag.java illustrates how to implement a class that implements the Iterator interface when the underlying data structure is a linked list.
- The nested class ArrayIterator in ArrayResizingBag.java does the same when the underlying data structure is an array.
Autoboxing Q + A
Q. How does auto-boxing handle the following code fragment?
Integer a = null; int b = a; |
A. It results in a run-time error. Primitive type can store every value of their corresponding wrapper type except null.
Q. Why does the first group of statements print true, but the second false?
Integer a1 = 100;
Integer a2 = 100;
System.out.println(a1 == a2);
// true Integer b1 = new Integer(100);
Integer b2 = new Integer(100);
System.out.println(b1 == b2);
// false Integer c1 = 150;
Integer c2 = 150;
System.out.println(c1 == c2);
// false |
A. The second prints false because b1 and b2 are references to different Integer objects. The first and third code fragments rely on autoboxing. Surprisingly the first prints true because values between -128 and 127 appear to refer to the same immutable Integer objects (Java's implementation of valueOf() retrieves a cached values if the integer is between -128 and 127), while Java constructs new objects for each integer outside this range.
Here is another Autoboxing.java anomaly.
Generics Q + A
Q. Are generics solely for auto-casting?
A. No, but we will use them only for "concrete parameterized types", where each data type is parameterized by a single type. The primary benefit is to discover type mismatch errors at compile-time instead of run-time. There are other more general (and more complicated) uses of generics, including wildcards. This generality is useful for handling subtypes and inheritance. For more information, see this Generics FAQ and this generics tutorial.
Q. Can concrete parameterized types be used in the same way as normal types?
A. Yes, with a few exceptions (array creation, exception handling, with instanceof, and in a class literal).
Q. Why do I get a "can't create an array of generics" error when I try to create an array of generics?
public class ResizingArrayStack<Item> {
Item[] a = new Item[1];
} |
A. Unfortunately, creating arrays of generics is not possible in Java 1.5. The underlying cause is that arrays in Java are covariant, but generics are not. In other words, String[] is a subtype of Object[], but Stack<String> is not a subtype of Stack<Object>. To get around this defect, you need to perform an unchecked cast as in ResizingArrayStack.java.
Q. So, why are arrays covariant?
A. Many programmers (and programming language theorists) consider covariant arrays to be a serious defect in Java's type system: they incur unnecessary run-time performance overhead (for example, see ArrayStoreException) and can lead to subtle bugs. Covariant arrays were introduced in Java to circumvent the problem that Java didn't originally include generics in its design, e.g., to implement Arrays.sort(Comparable[]) and have it be callable with an input array of type String[].
Q. Can I create and return a new array of a parameterized type, e.g., to implement a toArray() method for a generic queue?
A. Not easily. You can do it using reflection provided that the client passes an object of the desired concrete type to toArray() This is the (awkward) approach taken by Java's Collection Framework.
-----------------------------------------------------
Silence, the way to avoid many problems;
Smile, the way to solve many problems;