chap listsstacksand queues array-based lists are faster for random access by position positions can easily be adjusted forwards or backwards by the next and prev methods these operations always take th( time in contrastsingly linked lists have no explicit access to the previous elementand access by position requires that we march down the list from the front (or the current positionto the specified position both of these operations require th(ntime in the average and worst casesif we assume that each position on the list is equally likely to be accessed on any call to prev or movetopos given pointer to suitable location in the listthe insert and remove methods for linked lists require only th( time array-based lists must shift the remainder of the list up or down within the array this requires th(ntime in the average and worst cases for many applicationsthe time to insert and delete elements dominates all other operations for this reasonlinked lists are often preferred to array-based lists when implementing the array-based listan implementor could allow the size of the array to grow and shrink depending on the number of elements that are actually stored this data structure is known as dynamic array for examplethe java vector class implements dynamic array dynamic arrays allow the programmer to get around the limitation on the standard array that its size cannot be changed once the array has been created this also means that space need not be allocated to the dynamic array until it is to be used the disadvantage of this approach is that it takes time to deal with space adjustments on the array each time the array grows in sizeits contents must be copied good implementation of the dynamic array will grow and shrink the array in such way as to keep the overall cost for series of insert/delete operations relatively inexpensiveeven though an occasional insert/delete operation might be expensive to analyze the cost of dynamic array operationswe need to use technique known as amortized analysiswhich is discussed in section element implementations list users must decide whether they wish to store copy of any given element on each list that contains it for small elements such as an integerthis makes sense if the elements are payroll recordsit might be desirable for the list node to store reference to the record rather than store copy of the record itself this change would allow multiple list nodes (or other data structuresto point to the same recordrather than make repeated copies of the record not only might this save spacebut it also means that modification to an element' value is automatically reflected at all locations where it is referenced the disadvantage of storing