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 (NSDictionaryandNSSet)
Take Nicko van Someren’s insertion:
Building a doubly-linked list requires the object to gain forward and backward pointers and the only way to do this in Objective-C is to subclass the things you want to list. The problem is that the type system in Objective C is much more dynamic than in C++ and people are therefore far more inclined to write code that neither knows nor cares about the type of object that gets passed in. An initial reaction might be to build a linked list of some sort of node class and have each object in the list hang off a pointer in the node, but this does not really do what you need since it’s hard to work out which node refers to a particular object. So, all in all building code in Objective C to make generic lists of all subclasses of NSObject is a bit of a pain.
WTF? First of all, of course adding iterator functionality to member types is silly. He seems to dismiss the second approach (list of nodes, with pointers to members) for an even sillier reason. What does “it’s hard to work out which node refers to a particular object” mean? He’s still hung up on members having inverse awareness of their container. That’s what the iterator is for, damnit!
I think Pandaa said it well:
I strongly suggest everyone who contributed to this confusion read up on basic computer science.
So I guess not all Cocoa developers are oblivious to DSA.
It’s true, not all Cocoa devs are oblivious, but too many are. This is one reason why a lot of programs use horribly inefficient data structures to solve simple problems. I wish that were easier to fix. I’m trying, at least.
I inherited an Objective-C framework that originally started as a Java port, and have added a number of fairly solid implementations. You can find it here: http://cocoaheads.byu.edu/code/CHDataStructures
I also found Pandaa’s comments enlightened in the face of gross ignorance. In fact, my singly- and doubly-linked lists (simple as they are) could really benefit from some expert memory optimizations like he mentioned. I’ve noticed that enumeration is quite slow, but hadn’t considered optimizing to cache lines. Something for the future…