List vs Queue vs Set of collections in Java

Question

what is the difference among list, queue and set?

Solution

In brief:

A list is an ordered list of objects, where the same object may well appear more than once. For example: [1, 7, 1, 3, 1, 1, 1, 5]. It makes sense to talk about the "third element" in a list. You can add an element anywhere in the list, change an element anywhere in the list, or remove an element from any position in the list.

A queue is also ordered, but you'll only ever touch elements at one end. All elements get inserted at the "end" and removed from the "beginning" (or head) of the queue. You can find out how many elements are in the queue, but you can't find out what, say, the "third" element is. You'll see it when you get there.

A set is not ordered and cannot contain duplicates. Any given object either is or isn't in the set. {7, 5, 3, 1} is the exact same set as {1, 7, 1, 3, 1, 1, 1, 5}. You again can't ask for the "third" element or even the "first" element, since they are not in any particular order. You can add or remove elements, and you can find out if a certain element exists (e.g., "is 7 in this set?")

Comments

[Legato]

This is helpful, but I don't like that proceeding your saying that sets cannot contain duplicates you list a 'set' with duplicates.

[VoteyDisciple]

You think that {1, 7, 1, 3, 1, 1, 1, 5} contains duplicates, but Java doesn't think so. Put another way, you can always add an object to a set even if that same object is already there, That addition just doesn't change the makeup of the set or the outcome of any operations you might perform on it. That's different from a list, where adding another "1" creates a fundamentally different list.

[Vineet]

Generically speaking, a queue in computer science is FIFO (inserted at the "end" and removed from the "beginning") as you've described, but the Java interface doesn't actually require this. Implementations of Java's Queue interface can return elements in different orders, such as LIFO or based on some specified ordering, or whatever makes sense for a particular implementation.

[HopeKing]

@VoteyDisciple I didn't understand the {1, 7, 1, 3, 1, 1, 1, 5} example....how can a Set have duplicates ?

[VoteyDisciple]

@Ratatouille You only think that set contains duplicates because you're looking at all the numbers written out in a row and counting how many 1s you see. That's not how a set works. You add one value at a time, and only keep track of which values you've seen. Imagine I ask you to keep track of which cities I've visited. "I went to London, New York, London, Boston, and then London." So where have I been? You'd say "New York, London, and Boston." It's not your job to count how many times I went to London, and it's not my job to remember I already told you twice. That's why we have sets.

[HopeKing]

ok - so we can go ahead and add to the set, but the output of the set will still be unique values. Yes that was my understanding too - was probably confused by the wording. Thanks.

[Jonathan Vukadinovic]

a set can be ordered, treesets are ordered

[VoteyDisciple]

@JonathanVukadinovic No, Treesets define an order that elements will be given back to you; that's not quite the same thing. With a List, you can say "Add the element foo at position 3." With a Treeset, you can only say .add( foo ). You do not get to dictate which position it will end up.