PPT Slide

Vectors versus Linked Lists

For ordered Linked Lists:

• cost of traversal to locate target: O(N)

• cost of insert/delete: O(1)

• total cost: O(N)

For ordered Vector:

• cost of traversal to locate target: O(N) (if accessible via direct access, then O(1) )

• insertion or deletion of element implies (average case), moving

O(N) elements

• total cost: O(N)

Thus, at first glance, equivalent…

But what does Big Oh hide here?

• Linked Lists: search thru N/2, plus insert/delete

• Vectors: search thru N/2, plus moving N/2

Thus, Vectors

imply twice

the work

Previous slide

Next slide

Back to first slide

View graphic version