What is the difference between how dictionary and list datastructures appear in memory?

Question

For instance, if I was to create the following code:

a_list = ['this', 'is', 'a', 'sentence']
a_dict = { 0: 'this', 1 : 'is', 2 : 'a', 3 : 'sentence'}

then typing in the command prompt

>a_list[0]

yields

>'this'

as does

>a_dict[0]

yield

>'this'

Is there anything wrong with saying that a list is a type of dictionary if used strictly in the above manner so that the keys are the integers beginning at 0? Functionally they seem the same to me at this level of abstraction, so what is the difference in space that the - I assume functionally - equivalent structures take up in memory, and the speed in which we can access the values in python? A dictionary is a mathematical map, and a map that maps the positive integers to values is mathematically equivalent to a list. Am I wrong in saying given the above restrictions they are functionally the same at this level of abstraction. So what is the practical or computational difference in python?

Answer 1

When you are looking for performance comparisions, in CPython implementation they are close when it comes to certain operations like Get item and Set item etc. Look at this page explaining the details of time complexity.

But you have to remember that a list is list and dict a dict. You cannot sort a dict, it does not make any sense and you can do that to a list. You insert an item to a list, but to set a key,value pair in the dict. They are different operations.

Answer 2

What is wrong with saying that a list is a type of dictionary in where the keys are the integers beginning at 0?

Because that's factually incorrect. A dictionary can have keys like 0,2,4,6,8,10. A list cannot. A list doesn't have keys. It has indices to elements.

Functionally they must be the same,

Why? They're not the same. A list is a data structure designed for efficient iteration and sequential access. A dictionary is an implementation of a hash table designed for random access.

so what is the difference in space that they equivalent structures take up in memory, and the speed in which we can access the values in python

The objects are completely different. The code that's actually executed inside the interpreter when you access or use these types are completely different. They're designed for different purposes.

So what is the practical or computational difference in python?

You should read up on data structures. Arrays and hash tables have different uses and applications. Python's lists and dictionaries are implementations of these structures and are used for different purposes. The performance characters, abstract data types and applications are completely different.

Answer 3

Python dictionaries are not limited to integers as keys - anything that's hashable can be keys - strings, tuples, etc. In fact, using integer keys in Python dicts is far from being the most common use.

Python lists can be viewed as simple dynamic arrays (similar to C++'s std::vector). On the other hand, dicts are implemented as hash tables (std::unordered_map in the upcoming C++0x standard).

Why not always use dicts instead of lists? Because for many operations lists are the right data structure for the job - faster and smaller than dicts. For example, if all you need is a linear list of items you should use a list, not a dict - the list will consume less space, it will be faster in index access and it preserves insertion order. Yes, if you don't care about performance and about order, you can probably live with dicts instead of lists.

---

P.S. In some languages (Lua IIRC), arrays are implemented in terms of hash tables with numeric keys, so the equivalence you're trying to define exists.

Answer 4

List.

Dictionary.

Try to not confuse them.