Singly linked lists – HP Integrity NonStop J-Series User Manual
Page 302
differ radically among various implementations. However, it is generally true that a heap
allocation (or deallocation) that translates to a system call is more expensive than most of the
other constant costs. "Amortized" cost is averaged over the life of the collection. Any individual
action may have a higher or lower cost than the amortized value.
Key to the comparison tables
N
M
t
i
p
C
count of items count of space for
items
sizeof (item) sizeof (int) sizeof (void*) a constant
RWGVector, RWGBitVec, RWBitVec
RWTValVector
operation
time cost
space cost
Insert at an end
C
0
Insert in middle
C
0
Find (average item)
N/2
0
Change/replace item C
0
Remove first
C
0
Remove last
C
0
Remove in middle
C
0
Container overhead
Mt + 0
Comments
Simple wrapper around an array of T (except
bitvec: array of byte)
Resize only if told to.
Singly Linked Lists
operation
time cost;
space cost
Insert at an end
C
t + p
Insert in middle
C (assumes that you have an
iterator in position)
t + p
Find (average item)
N/2
0
Change/replace item C
0
Remove first
C
t + p (recovered)