Singly-Linked Lists

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