We introduce data-structural bootstrapping, a technique to design data
structures recursively, and use it to design confluently persistent d
eques. Our data structure requires O(log() k) worst-case time and spa
ce per deletion, where k is the total number of deque operations, and
constant worst-case time and space for other operations. Further, the
data structure allows a purely functional implementation, with no side
effects. This improves a previous result of Driscoll, Sleator, and Ta
jan (in ''Proceedings 2nd Annual ACM-SIAM Symposium on Discrete Algori
thms, 1991,'' pp. 89-99). (C) 1995 Academic Press, Inc.