The List ADT
The List ADT is one of
the most basic data structures in computer science. It is the basic foundation
for more complex data types (such as Trees, Stacks, Queues, etc). Even an
entire programming language, Lisp, has been built around the list as the only
data structure. Lisp stands for "list processing" and is a commonly
used language in Artificial Intelligence.
The List ADT is known as
a recursive ADT. An ADT is recursive if it has access methods that return the same
class as the ADT itself. In this case, the List ADT will return a List with
it's access function "rest," as you will see shortly.
An interesting fact
about the List ADT is that is has no manipulator (mutator) methods available.
Remember that there are 4 types of operations on an ADT - constructors,
interrogators (accessors), manipulators (mutators), and destructors. We can
take advantage of the recursive definition and simply create access methods to
make the List ADT surprisingly simple.
Read on ...
