case studymaintaining access frequencies the positional list adt is useful in number of settings for examplea program that simulates game of cards could model each person' hand as positional list (exercise - since most people keep cards of the same suit togetherinserting and removing cards from person' hand could be implemented using the methods of the positional list adtwith the positions being determined by natural order of the suits likewisea simple text editor embeds the notion of positional insertion and deletionsince such editors typically perform all updates relative to cursorwhich represents the current position in the list of characters of text being edited in this sectionwe consider maintaining collection of elements while keeping track of the number of times each element is accessed keeping such access counts allows us to know which elements are among the most popular examples of such scenarios include web browser that keeps track of user' most accessed urlsor music collection that maintains list of the most frequently played songs for user we model this with new favorites list adt that supports the len and is empty methods as well as the followingaccess( )access the element eincrementing its access countand adding it to the favorites list if it is not already present remove( )remove element from the favorites listif present top( )return an iteration of the most accessed elements using sorted list our first approach for managing list of favorites is to store elements in linked listkeeping them in nonincreasing order of access counts we access or remove an element by searching the list from the most frequently accessed to the least frequently accessed reporting the top most accessed elements is easyas they are the first entries of the list to maintain the invariant that elements are stored in nonincreasing order of access countswe must consider how single access operation may affect the order the accessed element' count increases by oneand so it may become larger than one or more of its preceding neighbors in the listthereby violating the invariant fortunatelywe can reestablish the sorted invariant using technique similar to single pass of the insertion-sort algorithmintroduced in the previous section we can perform backward traversal of the liststarting at the position of the element whose access count has increaseduntil we locate valid position after which the element can be relocated