Singly-Linked Lists
Table 23 – Time and space requirements for singly linked lists
operation
time cost
space cost
Insert at either 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)
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