The simple fact is this: C++ is not a safe language.
And that's good. If you're using C++, you want to control when you have safety, how you have it, and where you want to be unsafe.
When you manually delete a pointer, there is absolutely no indication anywhere that the pointer has been deleted. This is why most modern C++ texts will tell you that, unless you have some specific reason otherwise, do not use naked pointers. You should not be manually deleting pointers at all, unless again you have some specific reason to do so.
If you're making a data structure, then it's up to you how safe you want this data structure to be. Note that C++ standard library data structures allow for iterators (generalized pointers) to become invalid under certain conditions. This puts the responsibility on the user to know what they're doing.
The gain for this is fast performance. If you don't want that performance, then you need to use a safer container or data structure. If you want that safety, then you should use a smart pointer for elements in your data structure. The user should get shared_ptr<>
or weak_ptr<>
objects that reference nodes rather than naked pointers. And so forth.
C++ isn't safe. Of course it isn't safe; it's C++. But it's good.