Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The union operation for MultisetAsLinkedList class
requires the merging of two ordered, linked lists
as shown in Program 
.
We have assumed that the smallest element contained in a multiset
is found at the head of the linked list and the largest is at the tail.
Program: MultisetAsLinkedList Class Union Operator Definition
The union operator takes two multisets
and computes a third multiset, the result, as follows.
The main loop of the program (lines 9-21) traverses the linked lists
of the two operands,
in each iteration appending the smallest remaining element the result.
Once one of the lists has been exhausted,
the remaining elements in the other list are simply appended to the result
(lines 22-25).
The total running time for the union operation, operator+,
is O(m+n),
where 
and 
and s and t are the two operand multisets.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.