The Process of Designing a Custom Data Structure

When developing our apps, we may find ourselves in situations where no data structures we have at our disposal really fit into what we’re trying to accomplish. I recently ran into such a situation, working on a piece of functionality that called for the use of a collection of event listeners. Today, I thought I’d take the opportunity to share the thought process behind designing a custom data structure and ask a few questions we may want to answer before implementing it.

Step 1: Requirements

The first step of every design process is to actually decide on what you want your new structure to be able to do. This includes writing down what it absolutely must be able to do, and in what areas we may be able to get away with “suboptimal” performance. Let’s do this for our list of listeners.

• Listeners may or may not get deallocated during the lifetime of our list. We don’t want our list to be the reason that an object is kept in memory (and risk that it manipulates our program in unexpected ways), so we are going to need something that keeps weak references to the objects.
• Since listener objects may be deallocated, we are going to need a way of cleaning out those objects. The cleaning of the structure must take at most O(n) time, and it should be possible to perform clean up as…