A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit. [1]

Note that singly linked lists, which only support forward traversal, are also sometimes useful. If you do not need backward traversal, then slist may be more efficient than list. Definition Defined in the standard header list, and in the nonstandard backward-compatibility header list.h.