The object of the linear search algorithm is to find a node in the list which has an attribute which matches a given target value. We will use a Boolean variable **searching** which becomes **false** when a matching node is found.

accessfirst(exlist, exav) searching = true while searching and validaccess(exlist, exav) do { if exav^.attr == target then searching = false else accessnext(exlist, exav) } if searching then target not present else exav gives access to matching node

This algorithm works for an empty list. It also works where the list has only one node. We can illustrate the possible results of the search as a table:

If there are N nodes in a list an unsuccessful search will always need N comparisons. For a successful search we would expect an average of N/2 comparisons to be required. However, if the list is **ordered **on the relevant attribute we can reduce the number of comparisons required for an unsuccessful search to N/2 as well. To do this we introduce another Boolean variable, **hoping**, which becomes **false** if a value greater than the target value is encountered:

accessfirst(exlist, exav) searching = true hoping = true while searching and hoping and validaccess(exlist, exav) do { if exav^.attr = target then searching = FALSE else if exav^.attr > target then hoping = FALSE else accessnext(exlist, exav)

**searching** still indicates whether a match has been found, but there are now three possible outcomes for the search:

**Next: Adding Nodes**