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?
What is `wasted space` parameter and why is it O(n) for a linked list
data structures;arrays;linked lists
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)$).