Card 03/ 08
All 8 cards
ComparisonDifficulty: Intermediate1 min
List, Set and Queue on Order, Duplicates and Access
The three promises, laid out on the axes that actually separate them. Two of the rows decide almost every choice you will make.
| Compared on | List | Set | Queue |
|---|---|---|---|
| Keeps insertion order | Yes | Not promised | Yes, for the ends |
| Allows duplicates | Yes | No | Yes |
| Reach an element by position | Yes, get(i) | No | No |
| Which one comes out | Whichever you ask for | No such question | Decided by the queue |
| Ask whether something is in it | Walks the whole list | One hash lookup | Walks it |
The last row is the one people underuse. Asking a list whether it contains something means comparing against every element; asking a set means one hash and one bucket. A contains inside a loop over a list is the most common accidental loop-inside-a-loop in Java.
The decision rule. Need positions or duplicates, or the order they arrived in? List. Need to ask "have I seen this" often, or need each thing once? Set. Adding at one end and taking from the other? Queue.