John Carter
Jul 23, 2017 · 1 min read

Just a few quick notes…..

  • Hidden by your choice of language, but still there anyway, is the cost of non-locality, allocation and garbage collection of each list node. In practice, for (surprisingly large) small N, it’s often hard to beat a simple array, realloc’d if need be, memmove’d for inserts and deletes.
  • You can simplify some of your code by “The Elephant in Cairo” pattern.
  • One of the simplest, fastest, most flexible data structures is a doubly linked Elephant at Cairo list. Every time I look at the code for it I’m struck by how elegant it is.
  • An interesting collision resolution strategy for Hashes is Robin Hood. It’s (relatively) new so most textbooks don’t mention it.