Re: Linked List
Re: Linked List
- Subject: Re: Linked List
- From: Daniel DeCovnick <email@hidden>
- Date: Sun, 19 Sep 2010 12:57:59 -0700
On Sep 18, 2010, at 4:53 PM, Sherm Pendley wrote:
> On Sat, Sep 18, 2010 at 7:36 PM, Fritz Anderson <email@hidden> wrote:
>> On 18 Sep 2010, at 6:09 PM, email@hidden 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 (email@hidden)
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:
This email sent to email@hidden