I've seen several different definitions by googling, but I am still not sure. David kept saying "array gives us random access, and trie, too". What does 'random access' mean?
Random acccess, in this case, refers to having the "ability" of accessing any element in particular at a given point in time.
You simply "ask" for a certain element, as in
array and get the value stored in such position in constant time. There's no need to perform a search for such value, since the indexed structure provides you with access to any particular point in such array at any moment.
The name "random" is thought of from the computer's POV: any random position in the array the user asks for, he/she/it ;) is able to access it and return it by performing a (hopefully few) definite amount of steps (aka: constant time). He/she/it doesn't need to rely on any search algorithm.
In computer science, random access (more precisely and more generally called direct access) is the ability to access an item of data at any given coordinates in a population of addressable elements.
In terms of arrays, this basically means that, given the index of an element that you want to get/access from an array, you can directly access this element.
This is a constant-time operation — it always takes you a fixed number of steps to get it done.
If you're curious to know how, given an array
a that starts at location
100 in memory, if you're trying to access
a (assuming the array has at least 121 elements), this index (i.e., 120) is added to the starting location of the array (i.e., 100) and you get 220 which is the location of
a in memory.
This clearly relies on the fact that array elements are contiguous in memory — they live next to each others in order.
When you deal with recursive data structures (e.g., linked-lists, hash tables, etc.) you use dynamic memory allocation. Unlike arrays, the elements of these data structures could be in different locations in memory. So you can never rely on a fact that these elements are contiguous as it's the case with arrays. Therefore, to access an element, you need to access it through a previous/next element. This clearly means that this is not a constant-time operation and thus, you don't have random/direct access.
As for tries, they use a combination of dynamic memory allocation and arrays. We can probably think of them as having random-access either in case we know the maximum length a word could have assuming the process of allocating memory is a constant operation. If we don't know the maximum length that a word could have however, then accessing a word mainly depends on its length.
A trie does not have random access because you have to iterate over the nodes of the trie before you can find a word (for example). You would only find it by following pointers.
On the other hand, an array does have random access. For example, if you stored the
char 'a' in position 3 of the array, then you would have random access because you could get at 'a' by simply asking for