sec lists determined size whenever the list contains only few elementsa substantial amount of space might be tied up in largely empty array linked lists have the advantage that they only need space for the objects actually on the list there is no limit to the number of elements on linked listas long as there is free-store memory available the amount of space required by linked list is th( )while the space required by the array-based list implementation is ohm( )but can be greater array-based lists have the advantage that there is no wasted space for an individual element linked lists require that pointer be added to every list node if the element size is smallthen the overhead for links can be significant fraction of the total storage when the array for the array-based list is completely filledthere is no storage overhead the array-based list will then be more space efficientby constant factorthan the linked implementation simple formula can be used to determine whether the array-based list or linked list implementation will be more space efficient in particular situation call the number of elements currently in the listp the size of pointer in storage units (typically four bytes) the size of data element in storage units (this could be anythingfrom one bit for boolean variable on up to thousands of bytes or more for complex records)and the maximum number of list elements that can be stored in the array the amount of space required for the array-based list is deregardless of the number of elements actually stored in the list at any given time the amount of space required for the linked list is ( ethe smaller of these expressions for given value determines the more space-efficient implementation for elements in generalthe linked implementation requires less space than the array-based implementation when relatively few elements are in the list converselythe array-based implementation becomes more space efficient when the array is close to full using the equationwe can solve for to determine the break-even point beyond which the array-based implementation is more space efficient in any particular situation this occurs when de/( eif ethen the break-even point is at / this would happen if the element field is either four-byte int value or pointerand the next field is typical fourbyte pointer that isthe array-based implementation would be more efficient (if the link field and the element field are the same sizewhenever the array is more than half full as rule of thumblinked lists are better when implementing lists whose number of elements varies widely or is unknown array-based lists are generally more space efficient when the user knows in advance approximately how large the list will become