O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Vectors versus lists

Prepending an element to a linked list is very fast. In fact, it is an O(1) operation, meaning the original list is simply pointed at by the new element node. The change happens only at the head of the list. As we don't need to traverse the list at all, this is a fixed cost, that is, O(1) operation.

Accessing an element at some index n is slower, meaning it is proportional to the number of elements in the list. We need to start at the head and keep traversing the nodes and keep counting. We do this until we reach the nth node. If we access the second last node, we will have traversed almost all of the list.

When any operation could make us look at almost all the elements, the complexity would be O(n). This means it would be ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required