Python: List vs Dictionaries

Python has multiple types of data structure and from those the List and Dictionary are one of them. so we are discussing here about which is efficient in which condition.
first see some introduction about both.

List:

In python list is a most versatile data structure which stores ordered sequence of objects of different types .
In python list are mutable, which means that these elements can be altered unlike str or tuple. These elements of list called items.
For creating list in python, there are many ways but the simplest way to do this is by just using [ ] and put items separated by ,.
Different ways to create a list:

1. Using a pair of square brackets to denote the empty list.
2. Using square brackets, separating items with commas.
3. Using a list comprehension.
4. Using the type constructor.

a = [] # provide empty list
b = [1,2,3] 
c = [x for x in iterable]
d = list('abc')
e = list((1,2,3))

Dictionary:

In python dictionary is a mapping object maps hashable values to arbitrary objects.It is python's Mapping type and there are only one standard mapping types which is dictionary. It is also mutable . Python dictionary has a key, value pair where keys are almost arbitrary and the values that are not Hashable like values that contain list, dictionary or other mutable types are not used as the keys in dictionary.

Numeric types used for keys obey the normal rules for numeric comparison: if two numbers compare equal (such as 1 and 1.0) then they can be used interchangeably to index the same dictionary entry.

As the lists, Dictionaries can be created by various ways, but the simplest way to create it is by passing : separated pair of keys and values inside a { }.
Different ways to create a dictionary:

1. Use a comma-separated list of key: value pairs within braces.
2. Use a dict comprehension.
3. Use the type constructor.

a = dict(one=1, two=2, three=3)
b = {'one': 1, 'two': 2, 'three': 3}
c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
d = dict([('two', 2), ('one', 1), ('three', 3)])
e = dict({'three': 3, 'one': 1, 'two': 2})
f = dict({'one': 1, 'three': 3}, two=2)

All the above examples return a dictionary equal to {"one": 1, "two": 2, "three": 3}.

---

Now , we come to our topic. We generally use list in our programs because the lists are easy to use but what if we have a huge number of items for example 5000000. Then the lists take much time to lookup any items but if we do same task with dictionary it is done pretty fast, because in Python, the average time complexity of a dictionary key lookup is O(1), since they are implemented as hash tables. The time complexity of lookup in a list is O(n) on average. But there are one more problem with use of dictionary that it takes a lots of space as store keys and values pair as compared to the lists. That is the best situation of space-time tradeoff.

If you search for a fixed number of keys, if you grow your haystack size (i.e. the size of the collection you’re searching through) by 10,000x from 1k entries to 10M entries, using a dict is over 5000x faster than using a list! (Source: Fluent Python by Luciano Ramalho)

But after the python 3.6 we have a new implementation of dict which takes less memory then previous so now it is not more a space-time tradeoff.

The dict type has been reimplemented to use a more compact representation based on a proposal by Raymond Hettinger and similar to the PyPy dict implementation. This resulted in dictionaries using 20% to 25% less memory when compared to Python 3.5. (Source : python.org)

Thanks For reading.