CPP : How to get Element by Index in List

Lists are sequence containers that allow for the allocation of non-contiguous memory. List traversal is slower than vector traversal, but once a position is found, insertion and deletion are fast. Normally, when we talk about a List, we mean a doubly linked list. We use a forward list to implement a singly linked list.

Given a list and index, the task is to print the element which is present at given index

Example:

Input:

stringlist ={ "hello" , "this" , "is" , "BTech" , "Geeks" }      index=2

Output:

The value present at index 2 = is

Print element by index in List

Because std::list internally stores elements in a doubly-linked list, the list lacks the random access operator [] for accessing elements by indices. So, to access an element at any kth location, the idea is to iterate from the beginning to the Kth element one by one.

We can access the element by below methods:

1) std::advance() function

To find it in linear time, the STL std::advance() function is used.

Time Complexity : O(n)

Syntax:

advance(InputIterator& it, Distance N)

Parameters:

This function takes two parameters: the iterator to be traversed through the list and the position to which it must be moved. For random access and bidirectional iterators, the position can be negative.

Return:

There is no return type for this function.

Method #1:Using advance() function

Below is the implementation:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // Make a list and initialize it with some elements.
    list<string> stringlist(
        { "hello", "this", "is", "BTech", "Geeks" });
    // given index
    int index = 2;
    // taking a iterator which points to starting element of
    // the list
    list<string>::iterator itr = stringlist.begin();
    // moving the iterator to index position using advance()
    // function
    advance(itr, index);
    // printing the value
    cout << "The value present at index " << index << " = "
         << *itr;
    return 0;
}

Output:

The value present at index 2 = is

Method #2:Using next() function

C++11 introduces std::next(). It accepts an iterator as well as the position to be advanced. It does not change the passed iterator, but instead uses it to create a new iterator pointing to the nth -1 position of the given iterator and returns it.

Below is the implementation:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // Make a list and initialize it with some elements.
    list<string> stringlist(
        { "hello", "this", "is", "BTech", "Geeks" });
    // given index
    int index = 2;
    // taking a iterator which points to the given index
    // using next() function
    auto itr = next(stringlist.begin(), 2);
    // printing the value
    cout << "The value present at index " << index << " = "
         << *itr;
    return 0;
}

Output:

The value present at index 2 = is

Time Complexity: O(n)
Related Programs: