An NSMutableArray category to provide an NSMutableArray instance which uses a skip list variant for it's underlying data structure.

While a skip list is typically sorted and represents a dictionary. the indexed skip list is sorted by index and maintains deltas to represent the distance between linked nodes.

The underlying data structure looks much like the figure below:

index ->  HEAD   1    2    3    4    5    6    TAIL
           5| ---------------------> # ------>  #
           3| -----------> 2 ------> # ------>  #
           1| -> 1 -> 1 -> 1 -> 1 -> 1 -> # ->  #
  

Where the numbers represent how many indexes it is to the next node of the appropriate level. The bottom level always points to the next node.

Finding a specific index starts at the top level, until the current depth + the next nodes delta is larger than wanted index, then it goes down 1 level, and repeats until it finds the wanted index.

Addition and removal of indexes requires an update of the deltas of nodes which begin before, and end after the wanted index, these are the places where it goes down a level.

The rationale behind it was where a linked list based mutable array will quickly add and remove elements, it may perform poorly at accessing any random index (because it must traverse the entire list to get to the index).

While a C array based mutable array will perform good at random index access it may perform poorly at adding and removing indexes (because it must move all items after the altered index).

While a GSSkipMutableArray may not outperform a linked list or a C array based mutable array at their specific strengths, it attempts to not suffer from either of their weaknesses, at the cost of additional memory overhead.