3 ms·
A more elegant (IMHO) implementation of the q-list has the second pointer point not at the tail, but rather at either the last next pointer or at the head point
by barrkel 17y ago
A more elegant (IMHO) implementation of the q-list has the second pointer point not at the tail, but rather at either the last next pointer or at the head pointer. This makes your appending logic simpler by not having to deal with the special case of an empty list.
A similar trick can be used with hash tables where the buckets are s-lists. You still get O(1) deletion within a bucket if your hash table returns the address of the pointer that refers to the element, rather than the element itself; and you save one whole pointer per element by doing so.