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:
- Using a pair of square brackets to denote the empty list.
- Using square brackets, separating items with commas.
- Using a list comprehension.
- 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 fornumeric comparison
: if two numbers compare equal (such as1
and1.0
) then they can be used interchangeably to index the samedictionary 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:
- Use a comma-separated list of key: value pairs within braces.
- Use a dict comprehension.
- 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
from1k
entries to10M
entries, using adict
is over5000x
faster than using alist
! (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 thePyPy dict
implementation. This resulted in dictionaries using20% to 25%
less memory when compared toPython 3.5
. (Source : python.org)
Thanks For reading.
Top comments (0)