11: Collections of Objects

In basicTest( ) and iterMotion( ) the calls are made in order to show the proper syntax, and although the return value is captured, it is not used. In some cases, the return value isn’t captured at all. You should look up the full usage of each of these methods in the JDK documentation from java.sun.com before you use them. Feedback

Remember that a container is only a storage cabinet to hold objects. If that cabinet solves all of your needs, it doesn’t really matter how it is implemented (a basic concept with most types of objects). If you’re working in a programming environment that has built-in overhead due to other factors, then the cost difference between an ArrayList and a LinkedList might not matter. You might need only one type of sequence. You can even imagine the “perfect” container abstraction, which can automatically change its underlying implementation according to the way it is used. Feedback

Making a stack from a LinkedList

A stack is sometimes referred to as a “last-in, first-out” (LIFO) container. That is, whatever you “push” on the stack last is the first item you can “pop” out. Like all of the other containers in Java, what you push and pop are Objects, so you must cast what you pop, unless you’re just using Object behavior. Feedback

The LinkedList has methods that directly implement stack functionality, so you can also just use a LinkedList rather than making a stack class. However, a stack class can sometimes tell the story better: Feedback

//: c11:StackL.java
// Making a stack from a LinkedList.
import com.bruceeckel.simpletest.*;
import java.util.*;
import com.bruceeckel.util.*;

public class StackL {
  private static Test monitor = new Test();
  private LinkedList list = new LinkedList();
  public void push(Object v) { list.addFirst(v); }
  public Object top() { return list.getFirst(); }
  public Object pop() { return list.removeFirst(); }
  public static void main(String[] args) {
    StackL stack = new StackL();
    for(int i = 0; i < 10; i++)
      stack.push(Collections2.countries.next());
    System.out.println(stack.top());
    System.out.println(stack.top());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    monitor.expect(new String[] {
      "CHAD",
      "CHAD",
      "CHAD",
      "CENTRAL AFRICAN REPUBLIC",
      "CAPE VERDE"
    });
  }
} ///:~

If you want only stack behavior, inheritance is inappropriate here because it would produce a class with all the rest of the LinkedList methods (you’ll see later that this very mistake was made by the Java 1.0 library designers with Stack). Feedback

Making a queue from a LinkedList

A queue is a “first-in, first-out” (FIFO) container. That is, you put things in at one end and pull them out at the other. So the order in which you put them in will be the same order that they come out. LinkedList has methods to support queue behavior, so these can be used in a Queue class: Feedback

//: c11:Queue.java
// Making a queue from a LinkedList.
import com.bruceeckel.simpletest.*;
import java.util.*;

public class Queue {
  private static Test monitor = new Test();
  private LinkedList list = new LinkedList();
  public void put(Object v) { list.addFirst(v); }
  public Object get() { return list.removeLast(); }
  public boolean isEmpty() { return list.isEmpty(); }
  public static void main(String[] args) {
    Queue queue = new Queue();
    for(int i = 0; i < 10; i++)
      queue.put(Integer.toString(i));
    while(!queue.isEmpty())
      System.out.println(queue.get());
    monitor.expect(new String[] {
      "0",
      "1",
      "2",
      "3",
      "4",
      "5",
      "6",
      "7",
      "8",
      "9"
    });
  }
} ///:~

You can also easily create a deque (double-ended queue) from a LinkedList. This is like a queue, but you can add and remove elements from either end. Feedback

Set functionality

Set has exactly the same interface as Collection, so there isn’t any extra functionality like there is with the two different Lists. Instead, the Set is exactly a Collection—it just has different behavior. (This is the ideal use of inheritance and polymorphism: to express different behavior.) A Set refuses to hold more than one instance of each object value (what constitutes the “value” of an object is more complex, as you shall see).

The following example does not show everything you can do with a Set, since the interface is the same as Collection, and so was exercised in the previous example. Instead, this demonstrates the behavior that makes a Set unique: Feedback

//: c11:Set1.java
// Things you can do with Sets.
import com.bruceeckel.simpletest.*;
import java.util.*;

public class Set1 {
  private static Test monitor = new Test();
  static void fill(Set s) {
    s.addAll(Arrays.asList(
      "one two three four five six seven".split(" ")));
  }
  public static void test(Set s) {
    // Strip qualifiers from class name:
    System.out.println(
      s.getClass().getName().replaceAll("\w+\.", ""));
    fill(s); fill(s); fill(s);
    System.out.println(s); // No duplicates!
    // Add another set to this one:
    s.addAll(s);
    s.add("one");
    s.add("one");
    s.add("one");
    System.out.println(s);
    // Look something up:
    System.out.println("s.contains("one"): " +
      s.contains("one"));
  }
  public static void main(String[] args) {
    test(new HashSet());
    test(new TreeSet());
    test(new LinkedHashSet());
    monitor.expect(new String[] {
      "HashSet",
      "[one, two, five, four, three, seven, six]",
      "[one, two, five, four, three, seven, six]",
      "s.contains("one"): true",
      "TreeSet",
      "[five, four, one, seven, six, three, two]",
      "[five, four, one, seven, six, three, two]",
      "s.contains("one"): true",
      "LinkedHashSet",
      "[one, two, three, four, five, six, seven]",
      "[one, two, three, four, five, six, seven]",
      "s.contains("one"): true"
    });
  }
} ///:~