HP Integrity NonStop J-Series - Manual (Page 305)

Deques
operation time cost; space cost
Insert at end C t (amortized)
Find (average item) N/2 0
Change/replace item C 0
Remove first C t (amortized, recovered)
Remove last C t (amortized, recovered)
Remove in middle N/2 t (amortized, recovered)
Container overhead (Mt + p + i) + 0
Comments Implemented as circular queue in
an array.
Allocation only when collection
grows Expands and shrinks as needed,
caching extra expansion room
with each increase in size
Binary Tree
operation time cost; space cost
Insert logN+C 2p+t
Find (average item) logN 0
Change/replace item 2(logN + C) 0
Remove first logN + C 2p+t (recovered)
Remove last logN + C 2p+t (recovered)
Remove in middle logN + C 2p+t (recovered)
Container overhead (p+i) + N(2p+t)
Comments Insertion happens based on sort
order.
Allocation with each insert
Replace requires remove/add
sequence to maintain order
Does not automatically remain
balanced. Numbers above assume a
balanced tree. Costs same as doubly linked
list per item