Preface xi logical properties of data types and their operations have proved to satisfy the application. In Part I,abstract data types are classified with respect to the single relation 'predecessor/successor'which may or may not exist among the individual elements of a data type.Those data types for which this relation does not hold are primarily sets.Those with this relation defined on them are further classified into linear and non-linear data types.Non-linear data types are finally classified into trees and graphs.Only when the specification of an abstract data type is completely given do we begin to consider implementation issues.In this phase, the major emphasis rests on 'efficient'implementations of a data type and its operations.Therefore,a chapter is devoted to discussing the notion of 'effic- iency'of an algorithm so that later in the book the efficiency of the implemen- tations of abstract data types and algorithms may be quantified.Furthermore, this enables us to compare different implementations of the same abstract data type or the same task in a given programming language and a computer system. Declarative languages,in particular functional languages such as HOPE (Burstall et al.,1980)and ML (Milner,1978)allow for more succinct specifica- tion of ADTs and their implementations.(See for example,specification of lists in the Bibliographic notes,at the end of chapter 3). However,to date,these languages do not yield the same level of efficiency on conventional computers. Prerequisites The reader is assumed to have practical experience of a Pascal-like language. Although Pascal is used to express all the algorithms,they could easily be trans- formed into other similar languages.The efficiency of the algorithms is a major concern of the book and therefore it is advantageous if the reader has some knowledge about how various constructs of a Pascal-like language are imple- mented-with a view to comparing their relative speeds.However,this is not essential since the brief explanations given in the book should be sufficient to grasp these ideas. Structure of the Book The book is in two parts.Part I begins by examining the time and space require- ments of computer algorithms and develops a notation which is used in the remainder of the book to compare various implementations of abstract data types.Chapter 2 introduces the concept of abstraction in program design and shows how data types can be abstracted from their detailed implementation issues.Section 2.3 briefly describes a method of formally specifying the data type stack and proving that its implementation conforms to that specification