link-based vs array-based sequences we close this by reflecting on the relative pros and cons of array-based and link-based data structures that have been introduced thus far the dichotomy between these approaches presents common design decision when choosing an appropriate implementation of data structure there is not one-size-fits-all solutionas each offers distinct advantages and disadvantages advantages of array-based sequences arrays provide ( )-time access to an element based on an integer index the ability to access the kth element for any in ( time is hallmark advantage of arrays (see section in contrastlocating the kth element in linked list requires (ktime to traverse the list from the beginningor possibly ( ktimeif traversing backward from the end of doubly linked list operations with equivalent asymptotic bounds typically run constant factor more efficiently with an array-based structure versus linked structure as an exampleconsider the typical enqueue operation for queue ignoring the issue of resizing an arraythis operation for the arrayqueue class (see code fragment involves an arithmetic calculation of the new indexan increment of an integerand storing reference to the element in the array in contrastthe process for linkedqueue (see code fragment requires the instantiation of nodeappropriate linking of nodesand an increment of an integer while this operation completes in ( time in either modelthe actual number of cpu operations will be more in the linked versionespecially given the instantiation of the new node array-based representations typically use proportionally less memory than linked structures this advantage may seem counterintuitiveespecially given that the length of dynamic array may be longer than the number of elements that it stores both array-based lists and linked lists are referential structuresso the primary memory for storing the actual objects that are elements is the same for either structure what differs is the auxiliary amounts of memory that are used by the two structures for an array-based container of elementsa typical worst case may be that recently resized dynamic array has allocated memory for object references with linked listsmemory must be devoted not only to store reference to each contained objectbut also explicit references that link the nodes so singly linked list of length already requires references (an element reference and next reference for each nodewith doubly linked listthere are references