listsstacksand queues if they are done correctlythe programs that use them will not necessarily need to know which implementation was used the list adt we will deal with general list of the form an- we say that the size of this list is we will call the special list of size an empty list for any list except the empty listwe say that ai follows (or succeedsai- ( nand that ai- precedes ai ( the first element of the list is and the last element is an- we will not define the predecessor of or the successor of an- the position of element ai in list is throughout this discussionwe will assumeto simplify mattersthat the elements in the list are integersbut in generalarbitrarily complex elements are allowed (and easily handled by class templateassociated with these "definitionsis set of operations that we would like to perform on the list adt some popular operations are printlist and makeemptywhich do the obvious thingsfindwhich returns the position of the first occurrence of an iteminsert and removewhich generally insert and remove some element from some position in the listand findkthwhich returns the element in some position (specified as an argumentif the list is then find( might return insert( , might make the list into (if we insert into the position given)and remove( might turn that list into of coursethe interpretation of what is appropriate for function is entirely up to the programmeras is the handling of special cases (for examplewhat does find( return above?we could also add operations such as next and previouswhich would take position as argument and return the position of the successor and predecessorrespectively simple array implementation of lists all these instructions can be implemented just by using an array although arrays are created with fixed capacitythe vector classwhich internally stores an arrayallows the array to grow by doubling its capacity when needed this solves the most serious problem with using an array--namelythat historicallyto use an arrayan estimate of the maximum size of the list was required this estimate is no longer needed an array implementation allows printlist to be carried out in linear timeand the findkth operation takes constant timewhich is as good as can be expected howeverinsertion and deletion are potentially expensivedepending on where the insertions and deletions occur in the worst caseinserting into position (in other wordsat the front of the listrequires pushing the entire array down one spot to make roomand deleting the first element requires shifting all the elements in the list up one spotso the worst case for these operations is (non averagehalf of the list needs to be moved for either operationso linear time is still required on the other handif all the operations occur at the high end of the listthen no elements need to be shiftedand then adding and deleting take ( time