O() notation for Arrays operations and why is there no List class

ruby-talk
1

Is there any documentation of the O() notation for Array operations.
How is Array implemented?
Is it a contiguous block of memory?
Or are their chains of large blocks?

Does inserting at the beginning of an array cause all the elements to be shifted?

Does deleting from anywhere other than the end cause all elements to be shifted?

Why is there no List class?

2

Hi,

Is there any documentation of the O() notation for Array operations.

The source. :wink: It answers everything (including bugs), except for
“why” part.

How is Array implemented?

See source.

Is it a contiguous block of memory?
Or are their chains of large blocks?

The former.

Does inserting at the beginning of an array cause all the elements to be shifted?

Yes.

Does deleting from anywhere other than the end cause all elements to be shifted?

Yes, except for the top of an array. Despite its name, “shift” does
not shift elements.

Why is there no List class?

Because it is easily defined by users.

						matz.
···

In message “O() notation for Arrays operations and why is there no List class” on 02/11/21, MetalOne jcb@iteris.com writes:

3

Hi,

···

In message “Re: O() notation for Arrays operations and why is there no List class” on 02/11/21, Yukihiro Matsumoto matz@ruby-lang.org writes:

Does deleting from anywhere other than the end cause all elements to be shifted?

Yes, except for the top of an array. Despite its name, “shift” does
not shift elements.

Oops, I have to mention “on 1.7”.

						matz.