Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |

The array implementation of multisets is really only practical
if the number of items in the universe, *N*=|*U*|,
is not too large.
If *N* is large, then it is impractical,
or at least extremely inefficient,
to use an array of *N* counters to represent the multiset.
This is especially so if the number of elements in the multisets
is significantly less than *N*.

If we use a linked list of elements to represent a multiset *S*,
the space required is proportional to the size of the multiset, |*S*|.
When the size of the multiset is significantly less than
the size of the universe, ,
it is more efficient in terms of both time and space to use a linked list.

Program introduces the
the `MultisetAsLinkedList` class.
The `MultisetAsLinkedList` extends the `AbstractSet`
class defined in Program
and it implements the `Multiset` interface
defined in Program .
In this case a linked list of `int`s
is used to record the contents of the multiset.

How should the elements of the multiset be stored in the list?
Perhaps the simplest way is to store the elements in the list
in no particular order.
Doing so makes the `Insert` operation efficient--it can be done in constant time.
Furthermore, the `IsMember` and `Withdraw` operations
both take *O*(*n*) time,
where *n* is the number of items in the multiset,
*regardless of the order of the items in the linked list*.

Consider now the union, intersection, and difference of two multisets,
say *S* and *T*.
If the linked list is unordered,
the worst case running time for the union operation is *O*(*m*+*n*),
where *m*=|*S*| and *n*=|*T*|.
Unfortunately, intersection, and difference are both *O*(*mn*).

If, on the other hand,
we use an *ordered* linked list,
union, intersection, and difference can all be done in *O*(*m*+*n*) time.
The trade-off is that the insertion becomes an *O*(*n*) operation
rather than a *O*(1).
The `MultisetAsLinkedList` implementation presented in this
section records the elements of the multiset
in an *ordered* linked list.

**Program:** `MultisetAsLinkedList` fields.

Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.