Exercise Sheet 8: Don't be Listless

1. The Notes discusses a block implementation of the List ADT. Implementations are provided for ListBlock, isFull (added to the specification only for the block representation), beforeFirst, next and insertBefore.

   Complete the ADT by adding methods for the other list operations given in the specification and write a simple program to test the ADT's operations. (Note that you will also need to implement the WindowBlock class described in the Notes.)

2. The Notes discusses a singly-linked implementation of a List ADT. Example code for some of the methods (ListLinked, isEmpty, beforeFirst, next, previous and insertBefore) is given in the Notes.

   Provide a complete class ListLinked that implements the interface DAT.List. Make sure that you have implemented all of the remaining operations as constant time operations. You should use the WindowLinked class found in the DAT Package.

   Write a test program to ensure that your code works correctly. (Note that the reports from datlab in the remaining labs list less information for each method call in the report. Just as in an employment situation, it is up to you to test the code to find any bugs. It is suggested you do this using diagrams as in the lectures. Pay particular attention to "small" things, such as what happens to various pointers at the boundaries.)

   DAT Spot Check

   You should submit your ListLinked class for checking.

   [3 lab marks]

3. Topic 9 in the Notes discusses the problem of implementing insertBefore in the singly linked list representation of List. One solution for insertBefore is shown, in which a cell is inserted after the window and the elements swapped around. This is contrary to one of the aims of using references (or pointers) which is to avoid moving data around.

   An alternative suggested in the lectures (see also Wood, Problem 3.14), is to point the link in the window class to the cell immediately before the cell which contains the item that is under the (abstract) window position.

   Adapt the class ListLinked from above to a new class ListLinkedBefore which uses this approach.

   Hint: You may find it useful to "circularise" the list by assigning the before cell to the successor of the after cell (in a similar manner to the cyclically linked queue implemented previously).