From: Charles Comstock <cc1@...>
Date: 2004-05-21T07:23:47+09:00
Subject: Re: Ruby's builtin Datastructures

How much does it cost for an array access in the middle?  Why does it cost 
order(n) to remove the tail?  Why doesn't it float backwards until it needs 
memory ahead of it for instance?  I'd be curious to now a bit more of about 
this, as well as how the other datastructures are implemented.

Charlie

On Thu, 20 May 2004, Mauricio Fern�ndez wrote:

> On Thu, May 20, 2004 at 09:45:12PM +0900, Simon Strandgaard wrote:
> > my guess .. please correct me if im wrong
> > 
> > -------------------------------
> > push element         O(1)
> amortized O(1), I think
> > pop element          O(1)
> > shift element        O(?)     I hope O(1) 
> O(1)
> > unshift element      O(?)     I hope O(1)
> O(n)
> > insert element       O(n)
> > remove element       O(n)
> > ...
> 
>