Differencebetween Set and List

What is the difference between Set and List?

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.

What is difference between list and set in python?

A few key differences between a set and a list.

The order of a set is undefined. e.g. You can't be sure of what the "first" element of a set is.
A set must be unique, It cannot contain a duplicate of elements.

This is all very simplified, but with a set having only unique items and with its order undetermined, it allows the location of the object in memory to be defined uniquely based on itself. So when you search for a particular object in a set, it will already know the expected location of that object in memory. This is why it is O(1) (It does not need to iterate through all the elements)

If you don't care about the order of your list and you will always have unique items, it is considered best to use sets.

The difference between Lists and Sets

A Set is unordered and can't have duplicate items.

scala> Set(1,2,3,1,2,3) == Set(3,2,1)
res2: Boolean = true

Sequences (Array, List, Vector, etc) are ordered and can have repeated elements.

To use your example (which, incidentally, doesn't compile...):

val stuff = Array(1, 2, 3, 4)
val apple = Set(1, 2, 3, 4)

stuff.map(x => x % 3)  // Array(1, 2, 0, 1)
apple.map(x => x % 3)  // Set(1, 2, 0)

What is the difference between Collection and List in Java?

First off: a List is a Collection. It is a specialized Collection, however.

A Collection is just that: a collection of items. You can add stuff, remove stuff, iterate over stuff and query how much stuff is in there.

A List adds the information about a defined sequence of stuff to it: You can get the element at position n, you can add an element at position n, you can remove the element at position n.

In a Collection you can't do that: "the 5th element in this collection" isn't defined, because there is no defined order.

There are other specialized Collections as well, for example a Set which adds the feature that it will never contain the same element twice.

List vs Queue vs Set of collections in Java

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?")

Run time difference for in searching through list and set using Python

This is a great question.

The issue with arrays is that there is no smarter way to search in some array a besides just comparing every element one by one.

Sometimes you'll get lucky and get a match on the first element of a.
Sometimes you'll get unlucky and not find a match until the last element of a, or perhaps none at all.
On average, you'll have to search half the elements of they array each time.

This is said to have a "time complexity" of O(len(a)), or colloquially, O(n). This means the time taken by the algorithm (searching for a value in array) is linearly propertional to the size of the input (the number of elements in the array to be searched). This is why it's called "linear search". Oh, your array got 2x bigger? Well your searches just got 2x slower. 1000x bigger? 1000x slower.

Arrays are great, but they're for searching if the element count gets too high.

Sets are clever. In Python, they're implemented as if they were a Dictionary with keys and no values. Like dictionaries, they're backed by data structure called a hash table.

A hash table uses the hash of a value as a quick way to get a "summary" of an object. This "summary" is then used to narrow down its search, so it only needs to linearly search a very small subset of all the elements. Searching in a hash table a time complexity of O(1). Notice that there's no "n" or len(the_set) in there. That's because the time taken to search in a hash table does not grow as the size of the hash table grows. So it's said to have constant time complexity.

By analogy, you only search the dairy isle when you're looking for milk. You know the hash value of milk (say, it's isle) is "dairy" and not "deli", so you don't have to waste any time searching for milk

A natural follow-up question is "then why don't we always use sets?". Well, there's a trade-off.

As you mentioned, sets can't contain duplicates, so if you want to store two of something, it's a non-starter.
Prior to Python 3.7, they were also unordered, so if you cared about
the order of elements, they won't do, either. * Sets generally have a
larger cpu/memory overhead, which adds up when using many sets containing small numbers of elements.
Also, it's possible
that because of fancy CPU features (like CPU caches and branch
prediction), linear searching through small arrays can actually be
faster than the hash-based look-up in sets.

I'd recommend you do some further reading into data structures and algorithms. This stuff is quite language-independent. Now that you know that set and dict use a Hash Table behind the scenes, you can look up resource that cover hash tables in any language, and that should help. There's also some Python-centric resoruces too, like https://www.interviewcake.com/concept/python/hash-map