Exercise 2a of this labsheet is worth 2.5% of your final mark in this unit. The final date for submission is: 11:59pm Friday, April 7, 2023.

The aims of this labsheet are to:

1. implement a block version of a list ADT, and

2. implement a linked version of a list ADT.

Exercises

1. Block Implementation of a List

   The lecture notes discusses a block implementation of the list ADT. Code was provided for the ListBlock, isFull (added to the specification only for the block representation of the list ADT), beforeFirst, next and insertBefore methods.

   1. Complete the ADT by writing code for the other methods given in the specification of the list ADT.

      Note that you will also need to implement the WindowBlock class introduced in the lecture notes to complete this task.

   2. Write a test program that thoroughly tests each operation of your list ADT to satisfy yourself that your code is working correctly.

2. Linked Implementation of a List

   Topic 5 of the lecture notes discusses a singly-linked implementation of the list ADT. Code was provided for the ListLinked, isEmpty, beforeFirst, next, previous, and insertBefore methods.

   1. Write a class called ListLinked that completes the ADT, writing constant time methods for all operations given in the specification of the list ADT except the previous method (recall, you can't complete the previous method to run in constant time!).

      Use the WindowLinked class found in the DAT package to complete this task.

      Your list ADT must implement the CITS2200.List interface (that is, the List interface in the CITS2200 package). Fully document your code using javadoc comments.

      Submit your ListLinked implementation to the correct Moodle folder.

      If submitted before the due date, the system will compile and run your code, estimate your mark, and provide you with feedback. Final marking will occur after the posted due date and is subject to further examination, testing, and plagiarism checks of your code. Note that for security reasons, your code cannot contain any I/O commands, including printing statements. Although the auto-marking program provides you with some feedback, it should not be used as a substitute for your own testing.

   2. Write a test program that thoroughly tests each operation of your list ADT to satisfy yourself that your code is working correctly.

3. An Alternative Linked Implementation of a List

   Topic 5 of the lecture notes discusses the problem of writing the insertBefore method for the singly linked implementation of the list ADT. The solution discussed in the lecture notes involved inserting the item after the window and then swapping the elements around. This is contrary to one of the aims of using references (or pointers); that of avoiding the need to move data around.

   An alternative suggested in the lecture notes (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.

   1. Adapt the ListLinked class above to produce a new class called 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).

   2. Write a test program that thoroughly tests each operation of your list ADT to satisfy yourself that your code is working correctly.

Sample solution for Lab 4