Intersection

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 17-27). 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 © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.