The villain in many examples below is the garden-variety Mathematica list. This is of course unfair. Lists are the most useful of data structures in Mathematica. They are actually fixed-length vectors (often called vectors or arrays elsewhere in computer science, as distinct from what are called linked lists), and this is their chief drawback. Specifically, one cannot extend them efficiently. Indeed, much of this notebook is devoted to examples where extensible data structures are a must. That said, applications for which a fixed size table may be used are typically the most efficient.
There are several reasons for this. First, element retrieval is constant time. Second, all functional programming in Mathematica is geared toward list structures. Third, when elements may all be represented by machine numbers of the same type, Mathematica can used packed arrays internally which are both less memory-consumptive and faster for element access and other operations. Indeed, for many purposes one can use the Compile function, getting still further improvement in speed.
To give some indication of relative speed of building a fixed size table vs. a nested list, we show simple examples below.
While it is clear that tables are faster to build for such an example, one can show that nested list construction at least has the appropriate linear complexity, hence is not a bad alternative for applications where fixed-length tables are inappropriate. We will see an example of this sort presently. It should also be noted that much of the speed advantage of Table in the above example is due to use of packed arrays. For, say, tables of symbolic expressions, this is greatly diminished.