Difference between Dictionaries and Lists/Arrays?

Question

I am trying to understand the concept of each and its differences. I want to understand in which situations to use one or the other.

Answer 1

In general the 3 are used to contain diverse elements (objects) (can be of the same type or not, depends on the language and form of use of them) and the access to the elements are made through an index. We can say that it is an object that has other objects inside it. So if one variable is one of those objects you access what you really want through two parts:

• the variable that has the container;
• the variable that has the object that you really want, and that part is accessed by the index.

The list is a little harder to answer because it depends on how it is implemented, there is no single form of list. It is common for a list to be one array A little more flexible, but it can be a linked list, which changes the way you access each element. I’ll take the simplest form and close to the others.

Array and list have already been answered in What is actually the array?. In summary the list is the array that can increase in size.

The dictionary has by main and visible difference that the index may not be a number and may not be sequential, so we even talk that it is a key instead of an index. The most common key that is used is the string.

variavel["chave"]

Some language may have syntax sugar but it’s still a dictionary with an index being a string:

varivavel.chave

But depending on how the language implemented it may not be exactly a dictionary.

One of the most obvious consequences is that the data is not stored in the order they are placed, but in the order of the key, so the internal structure is quite different. I’ve seen implementation that actually there is no order at all (I don’t know if this can really be called a dictionary, has answer that help complete (or not :D), there are those who prefer to use map or other term).

Without considering other types of list, the 3 have complexity of space and access time to the elements constant (O(1)) or at least logarithmic (O(log n)).

In general the array should be used first, but depends on the language. In some languages the list is so simple and efficient, and more abstract that it is preferred and only if you have a very strong reason should you choose a array. Some languages almost require the use of array in many cases (usually due to language/library error). But in general if you do not need to grow the size of the array should not use the list. Reinforcement that this does not serve for much thing without considering the philosophy of language.

The dictionary is always a little worse, so it should only be used if it is very important, and usually when you cannot use a sequential numerical index, need otherwise, need the key organization.

Has language that mixes implementations.