Doubly-Linked Lists

Doubly-Linked Lists

Table 24 – Time and space requirements for doubly linked lists
operation	time cost	space cost
Insert at either 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.