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:
implement a block version of a list ADT, and
implement a linked version of a list ADT.
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.
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.
Write a test program that thoroughly tests each operation of your list ADT to satisfy yourself that your code is working correctly.
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.
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.
Write a test program that thoroughly tests each operation of your list ADT to satisfy yourself that your code is working correctly.
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.
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).
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