What is the difference between Set and List?

Question

What is the fundamental difference between the Set<E> and List<E> interfaces?

Solution 1

List is an ordered sequence of elements whereas Set is a distinct list of elements which is unordered (thank you, Quinn Taylor).

List<E>:

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

Set<E>:

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

Solution 2

	List	Set
Duplicates	Yes	No
Order	Ordered	Depends on implementation
Position Access	Yes	No

Solution 3

Ordered lists of element (unique or not)
Conform to Java's interface named List
Can be accessed by index

Implemented using

• LinkedList
• ArrayList

Lists of unique elements:
Conform to Java's interface named Set
Can not be accessed by index

Implemented using

• HashSet (unordered)
• LinkedHashSet (ordered)
• TreeSet (sorted by natural order or by provided comparator)

Both interfaces Set and List conform to Java's interface named Collection

Solution 4

A Set cannot contain duplicate elements while a List can. A List (in Java) also implies order.

Solution 5

• A List is an ordered grouping of items
• A Set is an unordered grouping of items with no duplicates allowed (usually)

Conceptually we usually refer to an unordered grouping that allows duplicates as a Bag and doesn't allow duplicates is a Set.

View more solutions

Comments

[karim79]

A set cannot have duplicates.

[palantus]

Some set implementations are ordered (such as LinkedHashSet, which maintains a LinkedList behind the scenes). But the Set ADT does not have ordering.

[palantus]

The Set ADT does not specifiy ordering, but some Set implementations (such as LinkedHashSet) keep insertion order.

[Quinn Taylor]

However, the more important difference is that sets don't allow duplicates. A bag/multiset does.

[Quinn Taylor]

Maps store objects by key, but sets store objects using a unique value related to the object, usually its hash code. (Maps may also use hash codes to check for key uniqueness, but they are not required to.)

[Vishy]

For a SortedSet, there are no two elements where compareTo() == 0, as equals is not called.

[Samuel EUSTACHI]

A Set CAN be ordered, so the first statement of this answer is misleading, even if of course a List must be choosen to enforce the Collection order

[stackoverflowuser2010]

WRONG! A Java set can be ordered, depending on the implementation; for example, a Java TreeSet is ordered. In the context of Java, the only difference between a List and a Set is that the Set contains unique items. In the context of mathematics, the items of a set are unique and unordered.

[stackoverflowuser2010]

A TreeSet has ordering.

[Spanky Quigman]

Yes, a Java Set CAN be BUT is not NECESSARILY ordered. Yes, if you have a TreeSet, you can count on that being ordered. But you have to KNOW that you have a TreeSet and not just a Set. If you are returned a Set, you can't depend on that to be ordered. A List on the other hand is ordered by its very nature and any implementation of List must be ordered. So, on the terms of the interface definition, it is not particularly wrong to say that a Set is unordered, but it's maybe a little more technically correct to say that a Set provides no guarantee of element order.

[ggb667]

Correct. LinkedHashSet contains elements in insertion order.

[FGreg]

It is wrong to say that a Set (in Java) is un-ordered because that is "guaranteeing" that the collection has no order. If all you know about a collection is that its elements are ordered, you cannot distinguish whether that collection is a Set or a List. By saying Set is un-ordered, it is implying that a collection of ordered elements cannot be a Set, which is not true.

[lilbyrdie]

Don't conflate "ordered" with "sorted." Likewise, don't conflate the contract of an interface and implementations of the interface. It is also wrong to say that something which is "unordered" has no order, it simply means there are no guarantees about the implementation of the order (and that the order may not be stable between calls, unlike with an ordered list).

[Vinay]

@stackoverflowuser2010 : What is the implementation difference between Java TreeSet (which is both ordered and unique) and C++ STL Set (which is only unique)?

[glen3b]

For one, List and Set are interfaces which also have "base" implementations in the form of an abstract class (which you mentioned). Also, #3 is completely inaccurate, as most sets allow null values (but implementation dependent). I don't understand #5 and #7, and for #6 Vector is not legacy, but is just synchronized and not preferred for use except when synchronization is needed.

[glen3b]

Lists also maintain ordering.

[Murali VP]

For anyone wondering how List is ordered, it is not sort order such as increasing or decreasing, the order is not by value of any of the elements in the list, so what does ordered mean? The insertion, the order in which elements where inserted.

[sara]

Playing the devil's advocate here, but if you wanna claim that "a set can be ordered" you could also claim that it's wrong to say a list IS ordered, because that too depends on the implementation. I think this is a silly way to reason. An interface is decoupled from the implementation, the interface just defines a contract. With this reasoning we could say "Well, Serializeable doesn't really mean a class can be serialized, it depends, maybe the implementation just throws an exception?" What use is this?

[sara]

It's an interface, EVERYTHING depends on the implementation. List.get() could create a file containing the first 5 decimals of pi and throw a StackOverFlowException in some implementations, this does not imply that you can say "A list is something that can create files", since that is not part of the contract defined by the interface. The docs claim Set is modeled after the mathematical concept of a set, which by definition is un-ordered. Given a set in your code you cannot assume it is ordered without violating SOLID principles.

[Christophe Roussy]

One thing to note: positional access performance depends a lot on the underlying implementation, array vs linked list stackoverflow.com/questions/322715/…

[Christophe Roussy]

@kai, I usually keep LinkedHashSet on the left-hand side if the code relies on the ordering later on. I only use Set if I really use it like one, as you cannot assume that the underlying implementation is a LinkedHashSet or such, it may be today, but tomorrow the code changes and it will fail.

[sara]

If you declare a LinkedHashSet you are not dealing with a Set, so making claims about how Sets should behave is hardly relevant. I'd say attributing (possible) orderedness to sets based on some implementations is akin to saying "Instances of Runnable have a run method meant to be run on some thread. Also they open a DB connection and read customer data depending on the implementation." Of course some implementations may do that, but that is not what is implied by the Runnable Interface.

[user2256009]

Set cant have null element. As mentioned in the answer "at most one null element" is wrong.

[malhobayyeb]

I am confused 😕 ! What does ordered/unordered means in this context? Is it related to ascending order and descending order? If so, List is not ordered 😕

[Akhil]

Ordered is when the input data are arranged exactly as inputted by the user whereas Sorted is when the input data is sorted lexicographically or ascending/descending order(in terms of integer values). Unordered means that the input data may or maynot be stored in the user inputted order.

[Panadol Chong]

Hi @Vibha, If I wan the both condition? I means I do not want my data contain duplicates, and I also want it be order.

[tplive]

How are Sets indexed if not by positional access? (+1 for the ASCII-table)

[Yash]

@BalusC please do not comment with out seeing the post date. See the post worthy at that time.

[Peter]

@smurti this is a bit late, and am not sure whether you have noted, but your first point contradicts itself: "Most of the List implementations (ArrayList,Vector) implement RandomAccess..." and "...None of the List implementations do that"

[help-info.de]

Welcome to Stack Overflow! Please note you are answering a very old and already answered question. Here is a guide on How to Answer.

[Omar Essam]

this is most detailed

[Gaj Julije]

Set allow null values, but as all it can not store dupicate null value. So someone can confuse by the comments that you make in the code example.

[Rishav]

I don't like to read. This makes it very concise and simple.

[fatimasajjad]

Nicely summed up information. Great!