I'm curious if you can explain why, in the listed answer for insertAfter on Page 39, you decide to traverse the list, using curPos, rather than just trust that the elem provided is actually in the list, and merely insert a new Element with the value data after it?

By traversing, you produce O(n) code. If you trust that elem is in the list, you produce O(1) code. I'm as paranoid as the next coder, but it seems a bit, er - cynical - to not trust that elem is in the list referenced by head and tail.

I realize that this is just a difference in how exhaustively the coder does error checking; but considering the emphasis in the book on efficiency, it seems an odd choice.

Regards,
-Matt

It may be useful to provide the client programmer two versions of insertAfter (named differently from each other, then, probably): one that assumes that elem is present in the list, and one that does not. Each of these versions has a different contract with its client. The first requires of the client that elem really is present in the list and promises no reliable behavior if this requirement is not met. The second relaxes this requirement and reliably reports the failure if elem is not present in the list. The first can be made to run in constant time; the second must run in at least linear time. A well-behaved client (one that knows for sure that elem is in the list), then, can choose to call the faster of these two operations.

Because different contracts are possible, it can be useful to express the contract, to write it down as part of the comments describing the operation.

Of course, one wouldn't have to provide two versions. Providing one version is okay if you express its contract, even if that one version is the fast one that assumes that elem is in the list.

Thank you for your contribution, Matt.

Regards,

Wayne