About MappedCollection

J J azreal1977 at hotmail.com
Sat May 26 15:28:50 UTC 2007


>From: "Avi Bryant" <avi at dabbledb.com>
>Reply-To: The general-purpose Squeak developers 
>list<squeak-dev at lists.squeakfoundation.org>
>To: "The general-purpose Squeak developers 
>list"<squeak-dev at lists.squeakfoundation.org>
>Subject: Re: About MappedCollection
>Date: Fri, 25 May 2007 11:21:16 -0700
>
>Either you can have transparency, or you can have O(1)
>insertion/removal, but I don't see how you can have both.  To get
>O(1), you have to have a reference to the link you want to remove or
>insert after, which isn't transparent; if you just had a regular
>object like you would put in an OrderedCollection, you would have to
>do a linear scan through the list to find the right link, and you're
>back to O(n).  No?
>
>Avi

Well you can have O(1) insert at either end with a plain singly linked list 
(so long as the interface object has a link to the head *and* the tail).  It 
is true that removals will have to be O(n) for generic objects, but a 
generic linked list is still valuable for various different algorithms (e.g. 
LIFO, FIFO).

LinkedLists aren't (or at least shouldn't be) expected to be good at what 
e.g. vectors excel at.

_________________________________________________________________
PC Magazine’s 2007 editors’ choice for best Web mail—award-winning Windows 
Live Hotmail. 
http://imagine-windowslive.com/hotmail/?locale=en-us&ocid=TXT_TAGHM_migration_HM_mini_pcmag_0507




More information about the Squeak-dev mailing list