0
$\begingroup$

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?

$\endgroup$
  • $\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$ – Derek Elkins Apr 25 '17 at 6:32
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thanks, so it's a space complexity, correct? $\endgroup$ – Maxim Koretskyi Apr 24 '17 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$ – David Richerby Apr 24 '17 at 8:53
  • $\begingroup$ Got it, thank you $\endgroup$ – Maxim Koretskyi Apr 24 '17 at 9:09
  • $\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$ – Maxim Koretskyi May 6 '17 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$ – David Richerby May 6 '17 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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