# What is wasted space parameter and why is it O(n) for a linked list

I'm reading a book on data structures and there is a comparison between linked list, array and dynamic array. The parameter name is wasted space. Here are the values:

\begin{array}{cc} \text{Linked list} & O(n)\\ \text{array} & 0 \\ \text{dynamic array}& O(n) \end{array}

What is the wasted space parameter and why is it $O(n)$ for a linked list?

• While I've actually never seen "wasted space" defined as a term, it may be useful to contrast to the concepts of implicit and succinct data structures. – Derek Elkins Apr 25 '17 at 6:32

So, in the first definition, a linked list has $O(n)$ wasted space because every entry of the list contains some piece of data but also a pointer, so a constant fraction of the space taken up by the data structure is "wasted". (I think this is a silly definition of "waste": the space taken up by the pointers isn't wasted; it's an overhead.) In the second definition, a half-full hash-table has 50% wasted space (again, $O(n)$).
• I don't understand then why it's also O(n) for a dynamic array, can you please clarify? Dynamic array usually holds only a pointer to the beginning for an array and some boolean indicator whether an array is full or not. – Maxim Koretskyi May 6 '17 at 5:31
• @Maximus Because, when a dynamic array is full, its size is increased by some factor $\alpha$. This means that, immediately after growing, a dynamic array holding $n$ items has size about $n\alpha$, so the amount of wasted space is $n(\alpha-1) = O(n)$. – David Richerby May 6 '17 at 9:57