Data Structures and Algorithms
with Object-Oriented Design Patterns in Java 
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 method.
The union method computes its result as follows:
The main loop of the program (lines 17-30) traverses the linked lists
of the two operands,
in each iteration appending the smallest remaining element to the result.
Once one of the lists has been exhausted,
the remaining elements in the other list are simply appended to the result
(lines 31-34).
The total running time for the union method is O(m+n),
where 
and 
.
Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.