std::list c++ is sequential then how it can take constant time for insert and erase operations anywhere within the sequence

Question

in c++ reference i read "Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions." my doubt is if it is sequential then how it can take constant time to delete and insert a node.Any way we have to traverse sequentially to reach that node . Deleting node depends on its position

Answer 1

O(1) referst to the complexity for inserting/erasing nodes provided you already have a handle (in the form of an iterator) to that node. Obtaining an iterator to the ith element of a list given an iterator to the first one is O(N).

This is quite often overlooked when judging the relative merits of std::list vs. say, std::vector. But note that both inserting and erasing elements return iterators that can be used for further insert/erase operations.

Answer 2

Insertion before a given node(lets call it pos) or as last node or deleting a given node is a constant time operation.

std::list can be implemented as doubly linked list. Sequence containers should not be confused with contiguous memory requirement.