Perhaps I'm being dumb, but doesn't std::list<T> already do exactly this?
From SGI's STL docs:
"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"
As others have said - yes, as long as you keep the iterator not the object itself. e.g. from T itself you cannot find where it was stored, so with std::list<something>, and then only from something you can't find where it is (you can have to look for it in the list).
The idiomatic way to access and manipulate STL data structures is through iterators. In this case, an iterator for a std::list is basically a pointer/reference to the person container in the article, so if you're referring to the list objects via their iterators there's no need for O(n) list traversal.
It's also not a problem in C++ if you don't care. Just because C++ gives you the means to enforce encapsulation doesn't mean you have to. And, as I said below, when your goal is performance and you need to break abstractions, it makes sense not to enforce encapsulation.
