Card 03/ 08
List vs Set vs Queue
Order, duplicates, access by position, and the cost of asking whether something is there.
List, Set and Queue all hold a group of elements and share Collection's methods. The table compares them on the axes that separate them, and two of the rows decide almost every choice.
| Compared on | List | Set | Queue |
|---|---|---|---|
| Keeps insertion order | Yes | Not promised | Depends on the queue: arrival order for ArrayDeque, priority for PriorityQueue |
| 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, for a HashSet | Walks it |
The last row is the one people underuse. Asking a list whether it contains something compares against every element; asking a HashSet means one hash and one bucket (one of the slots a hash table sorts its entries into). A contains on a list inside a loop is the most common accidental loop-inside-a-loop in Java.
The decision rule. Need positions, duplicates, or the order things 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, which is also how a pending-work list usually wants to be modelled.
← → move through sections and cards