In this article we will discuss how to get element by index in std::list.

std::list doesn’t have operator []

std::list does not have random access operator [] because std::list internally store elements in doubly linked list. So, to access an element at nth location we need to iterate one by one from beginning to nth element. So, its complexity will be O(n).

Suppose we have a list of strings i.e.

Now lets see how to access element at 3rd position from list using 2 different techniques.

Accessing nth element in std::list using std::advance

STL provides and algorithm std::advance() i.e.

It advances the given iterator by n positions. Now lets access element at 3rd position using std::advance.

As iterator it was already pointing to first element, therefore we need to advance it by 2 to point it to 3rd position.

Complexity of std::advance for std::list is O(n) because it needs to iterate one by one from beginning to nth position.

In C++11 another algorithm has been introduced i.e std::next()

Accessing nth element in std::list using std::next()

std::next() is introduced in C++11. It accepts an iterator and position to be advanced. It does not modify the passed iterator, but uses it to create a new iterator pointing to nth  -1 position from given iterator and returns it.

Lets see how to access element at 3rd position by std::next()

Complete example is as follows,

Output:

As the above example uses std::next(), which is a c++11 feature. So, use following command to compile the example in linux i.e.

g++ –std=c++11 example.cpp

Complexity of std::next() & std::advance() for std::list()

As std::list is internally implemented as doubly linked list. So, in linked list to access the nth element we need to go one by one from start to nth element.

Therefore, for both the APIs i.e. std::next() & std::advance() complexity to fetch nth element will be O(n).

Thanks.

Click Here to Subscribe for more Articles / Tutorials like this.