nil fig insertion in ordered list referring to fig we determine the condition under which the scan continues to proceed to the next elementit consists of two factorsnamely( nil( key xthe resulting search procedure isprocedure search (xintegervar rootword)(adens _list *var wordbegin (* nil* :rootw : nextwhile ( nil( key xdo : : next end(( nilor ( key > *if ( nilor ( key xthen (*new entry*new( ) next : key :xw count : next : else inc( countend end search in order to speed up the searchthe continuation condition of the while statement can once again be simplified by using sentinel this requires the initial presence of dummy header as well as sentinel at the tail it is now high time to ask what gain can be expected from ordered list search remembering that the additional complexity incurred is smallone should not expect an overwhelming improvement assume that all words in the text occur with equal frequency in this case the gain through lexicographical ordering is indeed also nilonce all words are listedbecause the position of word does not matter if only the total of all access steps is significant and if all words have the same frequency of occurrence howevera gain is obtained whenever new word is to be inserted instead of first scanning the entire liston the average only half the list is scanned henceordered list insertion pays off only if concordance is to be generated with many distinct words compared to their frequency of occurrence the preceding examples are therefore suitable primarily as programming exercises rather than for practical applications the arrangement of data in linked list is recommended when the number of elements is relatively small