The List ADT

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 ...

Let's take a look at the List ADT specification now before proceeding with the discussion.

construct(newElement:Object, oldList:List) : List
pre: none
post: if l = construct(newElement, oldList) then:

1.     l is a reference to a newly created object

2.     l != nil

3.     first(l) = newElement

4.     rest(l) = oldList

first(aList:List) : Object
pre: aList != nil

rest(aList:List) : List
pre: aList != nil

var nil : List
explanation: A constant denoting the empty list.

As stated earlier, the List ADT is rather simple. There is a construct constructor method that will create a new list for us by appending an element to the front of another list. The first accessor method allows us to see what is at the front of the list. Note that first does not modify the list - it only returns the value of what is at the front. The rest accessor method will let us see everything after the first of the list. Again, rest does not modify the list at all, it simply returns another List. Finally, there is a constant associated with the List ADT. The nil constant is what is used to signify an empty list and will prove to be quite handy, as you will see.

Now that we have the ADT defined, we can start using it. Remember that ADT's are implementation independent. We have an list interface available now that acts like a contract. Any class the implements the list interfacing needs to "sign" the contract by implementing all of the methods that the interface requires. This allows for better code portability and simultaneous development, as discussed earlier.

A quick example: If my buddy Jesse tells me that he's making a list class and gives me an interface for it, I can use that interface in my project without having his implementation details available. His implementation might not be stable yet, but I know that the final version will implement all of the methods defined in the interface. That is the point of the contract - he is promising me that he will deliver a certain set of methods, and because of that promise I can use those methods in my project even before he has completed his implementation. This is how interfaces are implentation independent. If Jesse can't complete his implementation in time, I can use Peter's implementation, provided the interface is the same. Make sense?