--- title: 'List, Set, and Queue' source: 'https://academia.sh/en/courses/java-standard-library/list-set-and-queue' course: 'The Standard Library and Streams' language: en updated: '2026-08-17T18:09:42+00:00' license: 'CC BY-SA 4.0' --- # List, Set, and Queue The same six-element workload is given to a list, a set, and a queue implementation at once, and what each one drops from the input is counted: the list drops nothing, the set drops three pieces of information, the queue drops only positional access. The bounding measurement arises from LinkedList being both a list and a queue at the same time: both interfaces give a remove promise, the promises collide in a single call line, and the identically written remove(1) does two separate jobs — both guarantees hold, the gap is in the line the caller writes, and the break is silent. 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. ```java // ThreePromises.java — gives the same workload to three interfaces, counts what each drops import java.util.*; public class ThreePromises { static final List WORKLOAD = List.of("apple", "pear", "apple", "cherry", "pear", "plum"); static void measure(String family, Collection 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. ```java // Uniqueness.java — is the order a set drops something the interface requires import java.util.*; public class Uniqueness { static final List WORKLOAD = List.of("apple", "pear", "apple", "cherry", "pear", "plum"); static final List FIRST_SEEN = List.of("apple", "pear", "cherry", "plum"); static boolean orderMatchesFirstSeen(Collection container) { return new ArrayList<>(container).equals(FIRST_SEEN); } public static void main(String[] args) { Set hash = new HashSet<>(WORKLOAD); Set 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 `apple`s 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. ```java // Ambiguity.java — same object, two interfaces, two separate remove methods import java.util.*; public class Ambiguity { public static void main(String[] args) { LinkedList actual = new LinkedList<>(List.of(10, 20, 30, 40)); List listRef = actual; Queue 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. ```java // 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 actual = new LinkedList<>(List.of(10, 20, 30, 40)); List 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`. 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?