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?

  • $\begingroup$ 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. $\endgroup$ Apr 25, 2017 at 6:32

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

  • $\begingroup$ thanks, so it's a space complexity, correct? $\endgroup$ Apr 24, 2017 at 8:42
  • $\begingroup$ It's a measure of space usage. I hesitate to use the word "complexity" as that normally refers to the resource requirements to decide a particular language, which isn't quite what we mean, here. $\endgroup$ Apr 24, 2017 at 8:53
  • $\begingroup$ 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. $\endgroup$ May 6, 2017 at 5:31
  • $\begingroup$ @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)$. $\endgroup$ May 6, 2017 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.