General Considerations
Time efficiency:
operations should be constant time (except MAP, DELETE, DESTROY).
Space efficiency:
no limit on list size (dynamic allocation). Pointers consume memory:
keep overhead down.
Should we use a header?
- Simplest approach: list is pointer to first node, each
node has pointer to next node.
- Alternative: list is header containing pointer to first
node. May also contain other information: additional pointers,
info about list contents, etc.
Headers make it possible to implement certain operations in constant
time:
- size
- pointer to last node for JOIN.
But: header must be kept up-to-date.