linked lists efficiency of sorted linked lists insertion and deletion of arbitrary items in the sorted linked list require (ncomparisons ( / on the averagebecause the appropriate location must be found by stepping through the list howeverthe minimum value can be foundor deletedin ( time because it' at the beginning of the list if an application frequently accesses the minimum itemand fast insertion isn' criticalthen sorted linked list is an effective choice priority queue might be implemented by sorted linked listfor example list insertion sort sorted list can be used as fairly efficient sorting mechanism suppose you have an array of unsorted data items if you take the items from the array and insert them one by one into the sorted listthey'll be placed in sorted order automatically if you then remove them from the list and put them back in the arraythe array will be sorted this type of sort turns out to be substantially more efficient than the more usual insertion sort within an arraydescribed in "simple sorting,because fewer copies are necessary it' still an ( process because inserting each item into the sorted list involves comparing new item with an average of half the items already in the listand there are items to insertresulting in about / comparisons howevereach item is copied only twiceonce from the array to the list and once from the list to the array * copies compares favorably with the insertion sort within an arraywhere there are about copies listing shows the listinsertionsort java programwhich starts with an array of unsorted items of type linkinserts them into sorted list (using constructor)and then removes them and places them back into the array listing the listinsertionsort java program /listinsertionsort java /demonstrates sorted list used for sorting /to run this programc>java listinsertionsortapp ///////////////////////////////////////////////////////////////class link public long ddata/data item public link next/next link in list /public link(long dd/constructor ddata dd/