chap listsstacksand queues figure illustrates the remove method removing an element requires th( time method next simply moves curr one position toward the tail of the listwhich takes th( time method prev moves curr one position toward the head of the listbut its implementation is more difficult in singly linked listthere is no pointer to the previous node thusthe only alternative is to march down the list from the beginning until we reach the current node (being sure always to remember the node before itbecause that is what we really wantthis takes th(ntime in the average and worst cases implementation of method movetopos is similar in that finding the ith position requires marching down positions from the head of the listtaking th(itime implementations for the remaining operations are straightforwardeach requiring th( time freelists the new operator is relatively expensive to use garbage collection is also expensive section discusses how general-purpose memory manager can be implemented the problem is that free-store routines must be capable of handling requests to and from free store with no particular patternas well as requests of vastly different sizes most runtime environments today provide reasonable implementations for their free-store operators howeverthe requirement that free-store managers be able to handle any pattern of new operationscombined with unpredictable freeing of space by the garbage collectormakes them inefficient compared to what might be implemented for more controlled patterns of memory access the conditions under which list nodes are created and deleted in linked list implementation allow the link class programmer to provide simple but efficient memory management routines in place of the system-level free-store operators instead of making repeated calls to newthe link class can handle its own freelist freelist holds those list nodes that are not currently being used when node is deleted from linked listit is placed at the head of the freelist when new element is to be added to linked listthe freelist is checked to see if list node is available if sothe node is taken from the freelist if the freelist is emptythe standard new operator must then be called freelists are particularly useful for linked lists that periodically grow and then shrink the freelist will never grow larger than the largest size yet reached by the linked list requests for new nodes (after the list has shrunkcan be handled by the freelist