The Algorithm Design Manual Second Edition

Searching a List

Searching for item x in a linked list can be done iteratively or recursively. We opt

for recursively in the implementation below. If x is in the list, it is either the first

element or located in the smaller rest of the list. Eventually, we reduce the problem

to searching in an empty list, which clearly cannot contain x.

2

C permits direct manipulation of memory addresses in ways which may horrify Java programmers, but we

will avoid doing any such tricks.

give the address in memory where a particular chunk of data is located

.

2

Pointers

in C have types declared at compile time, denoting the data type of the items they

can point to. We use *p to denote the item that is pointed to by pointer p, and &x

to denote the address of (i.e., pointer to) of a particular variable x. A special NULL

pointer value is used to denote structure-terminating or unassigned pointers.

---

3 . 1

C O N T I G U O U S V S . L I N K E D D A T A S T R U C T U R E S

69

list *search_list(list *l, item_type x)

{

if (l == NULL) return(NULL);

if (l->item == x)

return(l);

else

return( search_list(l->next, x) );

}