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 (
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.