What is the space complexity of HashTable, Array, ArrayList, LinkedList etc(if anything more)

Question

I want to know the space complexities of the basic data structures in popular languages.

Answer 1

Virtually all data structures with a non-trivial size are on the ORDER of n.

• Array = exactly n
• ArrayList = betweenn and k*n (default k=2)
• LinkedList = exactly n
• HashTable = worst is n/k (default k is .75)

Answer 2

All of these have space complexity O(n). All that changes is the coefficient, and that is completely dependent on the implementation. Especially when you start getting into things like pre-allocating space to reduce time complexity.

For instance, array list structures generally pre-allocate extra space. Therefore, their exact complexity for a number of objects is actually a range which is completely dependent on implementation and how they were created and used. For instance, if I write an array list that always allocates three extra spaces whenever more space is necessary, and always deallocates down to three open spaces when there's more than 5 open spaces, then actual complexity for n will be [n, n + 5] + overhead.

The big differences in choosing between these items when programming is usually ease-of-use and how well it fits with how you will be using it. For example, linked lists are horrible for random access, but great at iteration.

Answer 3

For Java: (Aproximates)

            Memory O(x) | General Case
Array     |       n     |    n
ArrayList |       n     |    2 * n
LinkedList|       n     |    n * (node size)
HashTable |       n     |    ~n
Map       |       n     |    (n * key_size) + n