|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
The implementation of the intersection operator for the
MultisetAsLinkedList class
is similar to that of union.
However, instead of merging of two ordered, linked lists
to construct a third,
we compare the elements of two lists
and append an item to the third only when
it appears in both of the input lists.
The Intersection method is shown in Program 
.
Program: MultisetAsLinkedList class Intersection method.
The main loop of the program traverses the linked lists of both input operands at once using two variables (lines 14-23). If the next element in each list is the same, that element is appended to the result and both variables are advanced. Otherwise, only one of the variables is advanced--the one pointing to the smaller element.
The number of iterations of the main loop actually done
depends on the contents of the respective linked lists.
The best case occurs when both lists are identical.
In this case, the number of iterations is m,
where 
.
In the worst case case, the number of iterations done is m+n.
Therefore, the running time of the Intersection method is O(m+n).
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.