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

Remove last C t + p (recovered)
Remove in middle C (assumes that you have an
iterator in position) t + p (recovered)
Container overhead (2p+i) + N(t+p)
Comments Allocation with each insert
Iterators go forward only Grows or shrinks with each item.
Smaller than doubly-linked list
Doubly Linked Lists
operation time cost; space cost
Insert at an end C t + 2p
Insert in middle C (assumes that you have an
iterator in position) t + 2p
Find (average item) n/2 0
Change/replace item C 0
Remove first C t + 2p (recovered)
Remove last C t + 2p (recovered)
Remove in middle C (assumes that you have an
iterator in position) t + 2p (recovered)
Container overhead (2p+i) + N(t+2p)
Comments Allocation with each insert
Iterate in either direction Grows or shrinks with each item
Larger than Slist
Ordered Vectors
operation time cost; space cost
Insert at end C (amortized) t (amortized)
Insert in middle N/2 t (amortized)
Find (average item) N/2 0
Change/replace item C 0
Remove first N 0
Remove last C 0