using thoseour last example list can be constructed as makelist( makelist( makelist( makelist( makelist( emptylist))))and it is clearly possible to construct any list in this way this inductive approach to data structure creation is very powerfuland we shall use it many times throughout these notes it starts with the "base case"the emptylistand then builds up increasingly complex lists by repeatedly applying the "induction step"the makelist(elementlistoperator it is obviously also important to be able to get back the elements of listand we no longer have an item index to use like we have with an array the way to proceed is to note that list is always constructed from the first element and the rest of the list soconverselyfrom non-empty list it must always be possible to get the first element and the rest this can be done using the two selectorsalso called accessor methodsfirst(list)and rest(listthe selectors will only work for non-empty lists (and give an error or exception on the empty list)so we need condition which tells us whether given list is emptyisempty(listthis will need to be used to check every list before passing it to selector we call everything list that can be constructed by the constructors emptylist and makelistso that with the selectors first and rest and the condition isemptythe following relationships are automatically satisfied ( true)isempty(emptylistnot isempty(makelist(xl)(for any and lfirst(makelist(xl) rest(makelist(xl) in addition to constructing and getting back the components of listsone may also wish to destructively change lists this would be done by so-called mutators which change either the first element or the rest of non-empty listreplacefirst(xlreplacerest(rlfor instancewith [ ]applying replacefirst( lchanges to [ and then applying replacerest([ ]lchanges it to [ we shall see that the concepts of constructorsselectors and conditions are common to virtually all abstract data types throughout these noteswe will be formulating our data representations and algorithms in terms of appropriate definitions of them