[34.5] How can I insert/access/change elements from a linked list/hashtable/etc?
The most important thing to remember is this: don't roll your own from scratch
unless there is a compelling reason to do so. In other words, instead of
creating your own list or hashtable, use one of the standard class templates
such as std::vector<T> or std::list<T> or whatever.
Assuming you have a compelling reason to build your own container, here's how
to handle inserting (or accessing, changing, etc.) the elements.
To make the discussion concrete, I'll discuss how to insert an element into a
linked list. This example is just complex enough that it generalizes pretty
well to things like vectors, hash tables, binary trees, etc.
A linked list makes it easy to insert an element before the first or after the
last element of the list, but limiting ourselves to these would produce a
library that is too weak (a weak library is almost worse than no library).
This answer will be a lot to swallow for novice C++'ers, so I'll give a couple
of options. The first option is easiest; the second and third are better.
- Empower the List with a "current location," and member functions
such as advance(), backup(), atEnd(), atBegin(), getCurrElem(),
setCurrElem(Elem), insertElem(Elem), and removeElem(). Although this
works in small examples, the notion of a current position makes it
difficult to access elements at two or more positions within the list (e.g.,
"for all pairs x,y do the following...").
- Remove the above member functions from List itself, and move them
to a separate class, ListPosition. ListPosition would act as a "current
position" within a list. This allows multiple positions within the same list.
ListPosition would be a friend of class List, so
List can hide its innards from the outside world (else the innards of List
would have to be publicized via public member functions in List). Note:
ListPosition can use operator overloading for things like advance() and
backup(), since operator overloading is syntactic sugar for normal member
- Consider the entire iteration as an atomic event, and create a class
template that embodies this event. This enhances performance by allowing the
public access member functions (which may be virtual functions) to be avoided during the access, and this access
often occurs within an inner loop. Unfortunately the class template will
increase the size of your object code, since templates gain speed by
duplicating code. For more, see [Koenig, "Templates as interfaces," JOOP, 4, 5
(Sept 91)], and [Stroustrup, "The C++ Programming Language Third Edition,"