Contents Up << >>

How can I insert/access/change elements from a linked list/hashtable/etc?

I'll use an "inserting into a linked list" as a prototypical example. It's easy to allow insertion at the head and tail 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.

  1. Empower the "List" with a "current location," and methods 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...").

  2. Remove the above methods from the 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 List, so List can hide its innards from the outside world (else the innards of List would have to be publicized via public methods in List). Note: ListPosition can use operator overloading for things like advance() and backup(), since operator overloading is syntactic sugar for normal methods.

  3. Consider the entire iteration as an atomic event, and create a class template to embodies this event. This enhances performance by allowing the public access methods (which may be virtual fns) to be avoided during the inner loop. Unfortunately you get extra object code in the application, 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 Second Edition," under "Comparator"].