Python: List vs Dictionaries
Tags: python, list, dictionary, fast
Published: 2021-01-18 03:43:14

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.
```python
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.

```python
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`. 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/qcf1jkddtxambpdj97p9.png)
> 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](https://mail.python.org/pipermail/python-dev/2012-December/123028.html) 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](https://docs.python.org/3/whatsnew/3.6.html#new-dict-implementation))

Thanks For reading.