From: Simon Strandgaard <neoneye@...>
Date: 2004-05-20T21:45:12+09:00
Subject: Re: Ruby's builtin Datastructures

Brian Schroeder wrote:
> Thanks for your answer. I should have looked in the raa by myself. Just a
> question regarding array as deque. How efficient is it? Is all the data
> shifted through the array every time I push something at the front and
> remove it from the back, or is it organized more efficiently?
 
I don't know how Array is implemented.. I think matz (Ruby's author) has
chosen a datastructure with constant-time head/tail insert/removal.
Not sure though.


It would be nice with an O(x) chart of the most common operations:


my guess .. please correct me if im wrong

-------------------------------
push element         O(1)
pop element          O(1)
shift element        O(?)     I hope O(1)
unshift element      O(?)     I hope O(1)
insert element       O(n)
remove element       O(n)
...


--
Simon Strandgaard