Posts Tagged ‘linked list’

Cocoa devs fail Data Structures & Algorithms?

Saturday, February 9th, 2008

I can’t find a linked-list class in Cocoa. Yes, I do want to do middle-insertions, and I’d have a fine time amortising my sequential access to constant time. Fine; it’s not like they’re hard to implement.

The scary thing is that when searching, I blindly fell into the pool of ignorance displayed in this circa-2004 Cocoa-dev thread. To be fair, the OP was more concerned about iterator functionality than a list implementation, but most of the responses seemed oblivious to:

  • The iterator design pattern
  • The time-complexity advantages of a linked-list implementation over arrays and deques (NSArray) and hashes and trees (NSDictionary and NSSet)

(more…)