end it follows from the definitions of the while statement and of the linking structure that is applied to all elements of the list and to no other ones very frequent operation performed is list searching for an element with given key unlike for arraysthe search must here be purely sequential the search terminates either if an element is found or if the end of the list is reached this is reflected by logical conjunction consisting of two terms againwe assume that the head of the list is designated by pointer while ( nil( key xdo : next end nil implies that pdoes not existand hence that the expression key is undefined the order of the two terms is therefore essential ordered lists and reorganizing lists the given linear list search strongly resembles the search routines for scanning an array or sequence in facta sequence is precisely linear list for which the technique of linkage to the successor is left unspecified or implicit since the primitive sequence operators do not allow insertion of new elements (except at the endor deletion (except removal of all elements)the choice of representation is left wide open to the implementorand he may well use sequential allocationleaving successive components in contiguous storage areas linear lists with explicit pointers provide more flexibilityand therefore they should be used whenever this additional flexibility is needed to exemplifywe will now consider problem that will occur throughout this in order to illustate alternative solutions and techniques it is the problem of reading textcollecting all its wordsand counting the frequency of their occurrence it is called the construction of concordance or the generation of cross-reference list an obvious solution is to construct list of words found in the text the list is scanned for each word if the word is foundits frequency count is incrementedotherwise the word is added to the list we shall simply call this process searchalthough it may actually also include an insertion in order to be able to concentrate our attention on the essential part of list handlingwe assume that the words have already been extracted from the text under investigationhave been encoded as integersand are available in the from of an input sequence the formulation of the procedure called search follows in straightforward manner the variable root refers to the head of the list in which new words are inserted accordingly the complete algorithm is listed belowit includes routine for tabulating the constructed cross-reference list the tabulation process is an example in which an action is executed once for each element of the list type word pointer to (adens _list *record keycountintegernextword endprocedure search (xintegervar rootword)var wwordbegin :rootwhile ( nil( key xdo : next end(( nilor ( key *if nil then (*novyi element* :rootnew(root)root key :xroot count : root next : else inc( count