## Description

This is assignment involves the implementation in Java of the set abstraction using linked

lists.

1. Proceed as follows.

• Download the file a4.tgz which contains some material you will need.

• Make sure you study the ADT description carefully before attempting to touch

the code.

• You will only need to write LinkedSet.java by fleshing out the stub provided.

• Your implementation must be based on the doubly-linked list concept. So the set

{2, 3, 5} would be represented as follows.

• Keep your work within the a4 directory. Submit all your work (as a4.tgz) using

Moodle on or before the deadline stated above.

ADT Set

2. Recall that the mathematical concept of a set is a collection of distinct elements, e.g.

α, β, γ. ADT Set will allow sets to be represented and manipulated by a variety of

operations (outlined below).

3. The basic operations supported by ADT Set are as follows. Notice that some of these

operations take arguments of type Set, others return results of type Set. The place

holder E is used to designate the type of element that the set contains 1

. Make sure

you understand these descriptions thoroughly before attempting to write any code. In

particular note that the specification of a set precludes duplicate elements.

• isEmpty(): Return true if this set contains no elements. Input: None; Output:

boolean.

• size(): Return the number of elements in this set (i.e. its cardinality). Input:

None; Output: int.

1While the mathematical notion of a set does not preclude sets that contains elements of differing types,

our formulation of ADT Set is restricted to homogeneous sets in which all the elements have the same type.

Nor does ADT Set permit sets to be infinite, for obvious reasons.

1

• add(newElement): Add the specified element to this set if it is not already

present. If this set already contains the specified element, the call leaves this set

unchanged Input: E; Output: None.

• contains(checkElement): Return true if this set contains the specified element i.e. if checkElement is a member of this set. Input: E; Output: boolean.

• remove(remElement): Remove the specified element from this set if it is

present. Input: E; Output: None.

4. The ADT also supports the following iterator method.

• elements(): Return an iterator of the elements in this set. The elements are

returned in no particular order. Input: None; Output: Iterator

5. In addition the ADT supports a number of additional methods that operate on pairs of

sets.

• addAll(addSet): Add all of the elements in the set addSet to this set if the

are not already present. The addAll operation effectively modifies this set so that

its new value is the union of the two sets. Input: Set

• containsAll(checkSet): Return true if this set contains all of the elements

of the specified set i.e. returns true if checkSet is a subset of this set. Input:

Set

• removeAll(remSet): Remove from this set all of its elements that are contained in the specified set. This operation effectively modifies this set so that its

new value is the (asymmetric) set difference of the two sets. Input: Set

Output: None.

• retainAll(retSet): Retain only the elements in this set that are contained in

the specified set. This operation effectively modifies this set so that its new value

is the intersection of the two sets. Input: Set

Implementation Notes

6. As linked structures can often be frustrating to work with at first, it is important to

tackle this assignment in good time that you approach it methodically.

7. Tackle the ”easy bits” first. Implement the zero-argument constructor (i.e. the one

that does not take a comparator) and the methods add, contains and remove.

8. When implementing the iterator, review the material in Lecture 11 that deals with

iterator implementation (albeit in the context of ADT List). The same “snapshot”

technique employed there using ArrayBasedIterator will work here.

9. The ∗All methods are easy to implement if you go about it sensibly.

2