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

Question

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?

Answer 1

Different people seem to define "wasted space" in different ways. Some authors define it as any space in a data structure that's not used to store actual data; others define it as space that could be used to store data but isn't being so used at the moment.

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)$).