List, Set, and Queue

The previous lesson measured four families as a single whole and counted how many of fifteen observations came from the interface, how many from the chosen class. But the choice between list, set, and queue itself was never questioned — all three are collections, all three accept the same add call. This lesson opens that choice: when the same data is given to all three at once, what does each one hold, what does it silently let go of? The answer will show that none is “better” than the other; all three are designed to answer a different question.

The Data Structures course established list, stack, queue, and set as abstract data types and compared implementation options by complexity; that comparison is not repeated here. The question here is not size, it is promise: the difference between choosing a list and choosing a set is, before the speed of operations, a commitment about which information will be kept.

Even the three interfaces’ names carry a promise: a list evokes an ordered index, a set the mathematical set’s property of uniqueness, a queue a physical line’s two ends. This lesson drops the intuition the names evoke down to a measurable number: facing the same input, how many pieces of information does each interface keep, how many does it sacrifice — and whether what is sacrificed is coincidence or the interface’s own promise is tested separately.

The Same Workload, Three Promises

• CO7 — The workload is a fixed six-element list carrying two duplicate values (apple and pear each appear twice); all three families are filled from the same list, in the same order.
• CO8 — Three pieces of information are measured, independent of one another: whether the duplicate element is held, whether insertion order is preserved, whether a position (index) is directly accessible. How much information a family drops is the sum of these three.

Only one implementation was chosen from each family (ArrayList, HashSet, ArrayDeque) — comparing three implementations to separate interface from implementation, as in the previous lesson, is not repeated in this lesson, because the question here is different: while the implementation stays fixed, how much do the three interfaces diverge from one another? HashSet was chosen deliberately, because its iteration order does not coincide with the input; had an order-preserving set implementation been chosen, this section’s measurement would be hidden.

// ThreePromises.java — gives the same workload to three interfaces, counts what each drops
import java.util.*;

public class ThreePromises {
    static final List<String> WORKLOAD = List.of("apple", "pear", "apple", "cherry", "pear", "plum");

    static void measure(String family, Collection<String> container) {
        boolean duplicatesHeld = container.size() == WORKLOAD.size();
        boolean orderHeld = new ArrayList<>(container).equals(WORKLOAD);
        boolean indexAccess = container instanceof List;
        int dropped = (duplicatesHeld ? 0 : 1) + (orderHeld ? 0 : 1) + (indexAccess ? 0 : 1);
        System.out.printf("%-8s size=%-3d duplicates=%-6s order=%-6s index=%-6s dropped=%d%n",
                family, container.size(), duplicatesHeld, orderHeld, indexAccess, dropped);
    }

    public static void main(String[] args) {
        measure("list", new ArrayList<>(WORKLOAD));
        measure("set", new HashSet<>(WORKLOAD));
        measure("queue", new ArrayDeque<>(WORKLOAD));
    }
}

list     size=6   duplicates=true   order=true   index=true   dropped=0
set      size=4   duplicates=false  order=false  index=false  dropped=3
queue    size=6   duplicates=true   order=true   index=false  dropped=1

Three rows tell three separate commitments. ArrayList drops nothing from the input: all six elements remain, order is preserved, any position can be reached directly with get. HashSet drops all three at once: the six-element input shrinks to four (the two duplicates were dropped), the remaining four’s iteration order does not coincide with the input, there is no positional access at all. ArrayDeque drops only one: it holds the duplicate too, preserves order too, the only thing it drops is positional access.

The Promise Comes from the Promise, Not from Complexity

The three pieces of information the set drops are not a flaw, they are the price of uniqueness: if a container promises it will hold every element once, the moment the second apple arrives it is either rejected or merges with the first — either way produces the same result, a size that stays small. The set’s promise is single: uniqueness. It says nothing about what order will result, because which internal structure secures uniqueness (a hash table, a balanced tree, an insertion-ordered linked list) mixes into the order, and the interface does not choose that internal structure — the previous lesson’s measurement of HashSet, LinkedHashSet, and TreeSet giving three separate answers to the same question was exactly this.

Unlike uniqueness, the order information a set drops is not a loss the interface requires — this can be measured directly. The same workload is given to two set implementations and whether the result coincides with first-seen order (the order in which the four elements left after dropping duplicates first appeared in the input) is checked.

// Uniqueness.java — is the order a set drops something the interface requires
import java.util.*;

public class Uniqueness {
    static final List<String> WORKLOAD = List.of("apple", "pear", "apple", "cherry", "pear", "plum");
    static final List<String> FIRST_SEEN = List.of("apple", "pear", "cherry", "plum");

    static boolean orderMatchesFirstSeen(Collection<String> container) {
        return new ArrayList<>(container).equals(FIRST_SEEN);
    }

    public static void main(String[] args) {
        Set<String> hash = new HashSet<>(WORKLOAD);
        Set<String> linked = new LinkedHashSet<>(WORKLOAD);
        System.out.println("HashSet iteration order                 : " + hash);
        System.out.println("HashSet order same as first-seen         : " + orderMatchesFirstSeen(hash));
        System.out.println("LinkedHashSet iteration order            : " + linked);
        System.out.println("LinkedHashSet order same as first-seen   : " + orderMatchesFirstSeen(linked));
    }
}

HashSet iteration order                 : [plum, apple, cherry, pear]
HashSet order same as first-seen         : false
LinkedHashSet iteration order            : [apple, pear, cherry, plum]
LinkedHashSet order same as first-seen   : true

LinkedHashSet keeps the same uniqueness promise while also preserving order; HashSet does not. So a set dropping order is not something the interface imposes, it is a choice made by the chosen class — just like the previous lesson’s “is iteration order insertion order” rows, measured across four families, being marked implementation. The only thing the interface requires is uniqueness; order, like positional access, is an add-on that can change from class to class.

The queue’s promise is single too and separate from the set’s: the end. The Queue interface says, with the trio offer, poll, peek, “it is added at one end, removed from one end, and that end is fixed”; it does not say which element will wait at that end. ArrayDeque preserves insertion order in this workload not by coincidence but by its own implementation choice (an array used end to end); the previous lesson’s PriorityQueue, speaking the same interface, giving false to the same question already showed that order is not the queue’s promise. The only piece of information the queue loses here is positional access, because a container promising an end does not give an address to a middle element — giving an address is the list’s job.

The list, by contrast, carries two promises at once: order and duplication. Every element added to a list stays at its own position, even if its equal was added earlier before it; every position can be addressed with get. These two promises are not the sum of what the set and the queue give separately — the list does not promise uniqueness (both apples remain), and it is not limited to a single end like the queue (it can be read from any position). The three interfaces correspond to three separate needs, and the choice is made by looking at which information needs to be kept. Carrying these two promises at once has a cost too, but that cost is not measured in this lesson: inserting at a middle position or searching for whether a value exists carries a cost that varies by implementation, and that cost was already counted in the Data Structures course. What is measured here is only which information stays or does not stay; how long it stays is a separate axis.

The previous lesson’s optional-operation observation appears once more here. A fixed set produced with Set.of and a fixed list produced with List.of both rejected an add attempt with the same exception; this lesson does not measure the rejection’s form, it measures which information stays when it is not rejected. The two measurements complete each other: one answers “what happens if the addition is accepted,” the other “what do we see if the addition is rejected.” Both come to the same conclusion: understanding a container’s behavior takes more than a single call’s syntax — which interface gives which promise has to be known separately.

The Bounding Measurement: The Same Object, Two Meanings

LinkedList is the framework’s only dual-identity class: it implements both List and Queue (through Deque) at the same time. In the measurement above, the queue row was represented by ArrayDeque, the list row by ArrayList; both were pure classes carrying a single interface’s promise. LinkedList is not pure — the same object, depending on which reference it is called through, can carry both the list’s and the queue’s promise, and when these two promises share the same method name, which one applies cannot be seen from the call’s syntax. The rule measured in the Object-Oriented Java course applies here exactly: what method a call binds to is decided not by the runtime type, but by the declared type.

• CO9 — A single LinkedList object is built and assigned to two variables: one declared with type List, the other with type Queue. Both point to the same object; this could be confirmed with ==, but the measurement does not need it, because the second call’s effect changes the state the first one left behind.

// Ambiguity.java — same object, two interfaces, two separate remove methods
import java.util.*;

public class Ambiguity {
    public static void main(String[] args) {
        LinkedList<Integer> actual = new LinkedList<>(List.of(10, 20, 30, 40));
        List<Integer> listRef = actual;
        Queue<Integer> queueRef = actual;

        System.out.println("start                          : " + actual);
        boolean wasRemoved = queueRef.remove(1);
        System.out.println("remove(1) via queue reference  -> returned=" + wasRemoved
                + "  result=" + actual);

        Integer removedValue = listRef.remove(1);
        System.out.println("remove(1) via list reference   -> returned=" + removedValue
                + "  result=" + actual);
    }
}

start                          : [10, 20, 30, 40]
remove(1) via queue reference  -> returned=false  result=[10, 20, 30, 40]
remove(1) via list reference   -> returned=20  result=[10, 30, 40]

The line written is identical in both: remove(1). The result is not the same at all. The Queue interface has no method called remove(int); the compiler boxes the argument 1 into an Integer and binds it to remove(Object) coming from Collection — it searches the container for an element whose value is 1, does not find one, returns false, and changes nothing. In the List interface, remove(int) is defined directly and the compiler reads 1 as an index; the 20 sitting at the second position is deleted and the deleted value is returned. The same two characters — (1) — mean “find the value and delete it” in one place, “delete the second position” in the other.

No guarantee is broken here. Both interfaces keep their promise fully: Queue promised to delete an element by its value, List promised to delete an element by its position, and both did what they promised. The implementation is not at fault either; the object is the same LinkedList object from start to finish and nothing inside it is corrupted. The gap is in the line the caller writes: where two promises fall onto the same name and the same syntax, it is the caller’s obligation to say which one is wanted.

When this obligation is broken, the result is the silent one among the three kinds this course measures. A call written with the intent “delete the second element” throws no exception, does nothing at all, and returns false; if the return value is not read, the flaw passes unnoticed. LinkedList speaking two interfaces at once is not a convenience here, it is a trap — because a single class is one of the rare places where two promises can collide within the same call’s syntax.

• CO10 — What the caller has to say is not only which interface it is speaking through, but in what form it writes the argument. Through the same List, if the argument is explicitly boxed as Integer, the “delete by value” promise is selected — the measurement shows this with a single reference, without opening a second variable.

// Resolution.java — what decides is not the reference's type, it is the argument's type
import java.util.*;

public class Resolution {
    public static void main(String[] args) {
        LinkedList<Integer> actual = new LinkedList<>(List.of(10, 20, 30, 40));
        List<Integer> listRef = actual;

        boolean wasRemoved = listRef.remove(Integer.valueOf(1));
        System.out.println("list reference, remove(Integer.valueOf(1)) -> returned="
                + wasRemoved + "  result=" + actual);

        Integer removedValue = listRef.remove(1);
        System.out.println("list reference, remove(1) (int)            -> returned="
                + removedValue + "  result=" + actual);
    }
}

list reference, remove(Integer.valueOf(1)) -> returned=false  result=[10, 20, 30, 40]
list reference, remove(1) (int)            -> returned=20  result=[10, 30, 40]

The variable is the same listRef, the interface spoken through is the same List<Integer>. Only the argument’s form changed: in the first call, Integer.valueOf(1) is an object and falls onto the “delete by value” promise — the container is searched for an element equal to the value 1, none is found, false is returned. In the second call, 1 is an int constant and falls onto the “delete by position” promise. So the obligation does not end with choosing the interface: the caller, when writing the argument, is also saying which promise it wants, and can say this without realizing it. The Object-Oriented Java course measured which side this choice is made on; what is measured here is not the side of the choice, it is that the library leaving the choice to the caller never asks about it anywhere.

The reason this trap can only be shown on LinkedList is that it speaks two interfaces at once. ArrayList speaks only List, ArrayDeque speaks only Queue; on those classes the form remove(1) has a single counterpart and the collision never arises at all. LinkedList gathers both promises in the same object; this is why the measurement can be done not on two separate classes, but on a single object, with just two variables. “Delete by position” exists only on the List side, not at all on the Queue side — the distinction arises not from the object’s behavior, but from the set of promises the two interfaces give. This is a general rule that holds for every class in the library that implements more than one interface at once; LinkedList is the closest example to showing it with a single call.

Summary

• When the same six-element input is given to a list, a set, and a queue, the list drops no information, the set drops all three at once (duplication, order, positional access), the queue drops only positional access.
• The three interfaces’ selection criterion is not operation speed, it is promise: a list promises order and duplication, a set promises uniqueness, a queue promises the end. The complexity comparison was made in the Data Structures course and is not repeated here; what is measured here is only which information is still readable once it leaves the input.
• The information a set drops is not a flaw; it is the required price of keeping the uniqueness promise. That a queue preserves order, though, is not the interface’s promise, it is the chosen implementation’s preference.
• LinkedList carries both the List and Queue interfaces at once, and the two interfaces’ remove promises collide within a single call’s syntax: the identically written remove(1) deletes by position in one place, by value in another.
• No guarantee is broken in the collision — both interfaces keep their promise, the object does not change. What breaks is the caller’s obligation, and the break is silent: no exception falls, false is returned, and if the return value is not read, the flaw goes unnoticed.

Next Step

In this lesson, the list, the set, and the queue each reached the element they held through a single path: position, membership, or the end. What these three access paths had in common was that the container was self-sufficient — finding where an element was required no information from outside the container. A key-value mapping gives a promise different from all three: an element is reached by its key, and the interface promises to keep that key’s counterpart unique. But half of the promise about what the key itself can be does not sit in the library, it sits in the class the caller writes — the container only asks for the key, it does not check whether the key behaves consistently with itself. The next lesson measures this other half: when a key class is written incorrectly, where does the lookup land, which exception falls, and if none falls, what stands in its place?