head, tail, cons and
isEmpty is the simplest form,
and is attractive because it directly matches lists as found as
a built-in structure in functional and logic languages.
Having a linked list as an inner class seems to be the best way
to implement the simple abstract data type list, but as we saw
there are other ways. A third way, not explained in class, is given
in some further code in /import/teaching/BSc/1st/ItP/banks.
It uses the linked list principle, but not as an inner class.
There are two classes in this implementation, DirectList
and DirectNode, with DirectNode extending
DirectList. An object which is a DirectList
object but not a DirectNode object represents an empty
list. It is necessary to have this special implementation of an empty
list and not just use null, because null
is not itself an object so can't have any methods called on it, whereas
we want to be able to call the methods cons and
isEmpty on objects representing empty lists. The class
BankK uses this implementation of lists, and the class
UseBank11 uses BankK.
There are some further notes available from the
local resources page covering material that won't be covered in class
and won't come up in the exam, but which would be the next step from lists
if there were more time (which there isn't, as the remaining lectures in
this course will be revision only). The notes on
stacks
describe an abstract data structure which is like a list but destructive.
With a list l, the method l.cons(x)
represents a new value and makes no changes to the object referred to
by l. The equivalent in stacks is the operation
push, and with stack s the method call
s.push(x) changes the object s
refers to, but does not return a value (so the call must be used
as a statement on its own). The notes on
trees
(with a further set
here)
describe an abstract data type which is could be thought of as like a list
where nodes have two tails.
Considering what we have covered in relation to the recommended textbooks, we have covered most of the first fifteen chapters of the Barnes book, but not the rest which is on more specialist aspects of Java. Unfortunately, Barnes does not have a chapter on building your own data structures, instead it has a chapter (chapter 10) on Collection Classes. These are classes which are provided as part of the Java library. If "Introduction to Programming" were just a course on how to use Java, you might have just been shown how to use these built-in classes, but as it is a course on programming in general, you were shown how to write your own versions. Note that section 10.4 and 10.9 of Barnes' Chapter 10 do cover things we have covered in the course. The Horstmann, Pohl, Bishop and Deitel books all have a chapter introducing data structures including linked lists, though data structures are generally covered in more detail in separate textbooks. Here is a review of several such textbooks, a little out of date now as more have come onto the market since it was written.
We have covered most of the material in the other textbooks, except we have done nothing on graphics, which has a little coverage in all the textbooks, or on threads which have some coverage in all the textbooks except Horstmann. The Deitel textbook is more advanced than the others, so it has more material on these and other specialist aspects of Java. There is coverage of graphics in Java in the second year course Graphical User Interface Design, and coverage of threads in Java in the course Computer Systems 3.
Here are some web notes on the general idea of abstract data types:
Uday Reddy's First Year Software Workshop at the University of Birmingham has notes and exercises (click on the relevant links) using recursion on a list abstract data type very similar to ours.
Here are some more notes on list abstract data types:
Matthew Huntbach 16th March 2001