there are many situations where the list is built up by insertions at the high endand then only array accesses ( findkth operationsoccur in such casethe array is suitable implementation howeverif insertions and deletions occur throughout the list andin particularat the front of the listthen the array is not good option the next section deals with the alternativethe linked list simple linked lists in order to avoid the linear cost of insertion and deletionwe need to ensure that the list is not stored contiguouslysince otherwise entire parts of the list will need to be moved figure shows the general idea of linked list the linked list consists of series of nodeswhich are not necessarily adjacent in memory each node contains the element and link to node containing its successor we call this the next link the last cell' next link points to nullptr to execute printlist(or find( )we merely start at the first node in the list and then traverse the list by following the next links this operation is clearly linear-timeas in the array implementationalthoughthe constant is likely to be larger than if an array implementation were used the findkth operation is no longer quite as efficient as an array implementationfindkth(itakes (itime and works by traversing down the list in the obvious manner in practicethis bound is pessimisticbecause frequently the calls to findkth are in sorted order (by ias an examplefindkth( )findkth( )findkth( )and findkth( can all be executed in one scan down the list the remove method can be executed in one next pointer change figure shows the result of deleting the third element in the original list the insert method requires obtaining new node from the system by using new call and then executing two next pointer maneuvers the general idea is shown in figure the dashed line represents the old pointer as we can seein principleif we know where change is to be madeinserting or removing an item from linked list does not require moving lots of itemsand instead involves only constant number of changes to node links the special case of adding to the front or removing the first item is thus constanttime operationpresuming of course that link to the front of the linked list is maintained figure linked list figure deletion from linked list