end end searchprocedure printlist (wword)begin (*uses global writer *while nil do texts writeint(ww key )texts writeint(ww count )texts writeln( ) : next end end printlistthe linear scan algorithm resembles the search procedure for arraysand reminds us of simple technique used to simplify the loop termination conditionthe use of sentinel sentinel may as well be used in list searchit is represented by dummy element at the end of the list the new procedure is listed below we must assume that global variable sentinel is added and that the initialization of root :nil is replaced by the statements new(sentinel)root :sentinel which generate the element to be used as sentinel procedure search (xintegervar rootword)(adens _list *var wwordbegin :rootsentinel key :xwhile key do : next endif sentinel then (*new entry* :rootnew(root)root key :xroot count : root next : else inc( countend end search obviouslythe power and flexibility of the linked list are ill used in this exampleand the linear scan of the entire list can only be accepted in cases in which the number of elements is limited an easy improvementhoweveris readily at handthe ordered list search if the list is ordered (say by increasing keys)then the search may be terminated at the latest upon encountering the first key that is larger than the new one ordering of the list is achieved by inserting new elements at the appropriate place instead of at the head in effectordering is practically obtained free of charge this is because of the ease by which insertion in linked list is achievedi by making full use of its flexibility it is possibility not provided by the array and sequence structures (notehoweverthat even in ordered lists no equivalent to the binary search of arrays is availableordered list search is typical example of the situationwhere an element must be inserted ahead of given itemhere in front of the first one whose key is too large the technique shown herehoweverdiffers from the one used shown earlier instead of copying valuestwo pointers are carried along in the list traversalw lags one step behind and thus identifies the proper insertion place when has found too large key the general insertion step is shown in fig the pointer to the new element ( is to be assigned to nextexcept when the list is still empty for reasons of simplicity and effectivenesswe prefer to avoid this distinction by using conditional statement the only way to avoid this is to introduce dummy element at the list head the initializing statement root :nil is accordingly replaced by new(root)root next :nil