On Sep 18, 2010, at 4:53 PM, Sherm Pendley wrote: > On Sat, Sep 18, 2010 at 7:36 PM, Fritz Anderson <fri...@manoverboard.org> > wrote: >> On 18 Sep 2010, at 6:09 PM, k...@highrolls.net wrote: >> >>> What is the Cocoa equivalent of a doubly linked list? Should I consider >>> NSMutablearray as the analog? >> >> Yes. >> >> The Foundation data types are distinguished by what they _are_ (ordered >> collections, unordered collections, dictionaries, strings, dates, data >> buffers) and not how they are _implemented._ Foundation is free to select >> any of a number of internal implementations for those generic forms. In >> fact, it may _change_ the implementation of your collections behind your >> back, to preserve performance as the collections grow. >> >> There's no "doubly-linked list" because you don't really want a >> doubly-linked list, you want an ordered collection. > > Can't say I agree with that 100%. It's true for simple iteration, but > a linked list also has other performance characteristics that an array > does not - the ability to remove and/or insert items at any position > in constant time, for example.
CFMutableArray does this when there are more than 300,000 elements in the array. In fact, all operations start taking constant time (though some are fairly slow) when you reach 300,000 elements, and it's position-independent at that point (hit 300k, and there are no longer any favored insertion positions, including within the first 300k). Take a look at the graphs here: http://ridiculousfish.com/blog/archives/2005/12/23/array/#fish_made_a_mess -Daniel _______________________________________________ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
