What data structure are Ruby arrays?

Question

I am learning about Arrays and Linked List in my computer science class. My professor says that Arrays cannot have elements added or removed from the end so instead we use linked list.

I know the implementation of Arrays in Python, Ruby, and JavaScript all allow me to modify an arrays length all I want. Do these languages really implement a linked list or some other data structure and call it an array?

What is going on under the hood? And if it is not a true array, why do they call it one?

Answer 1

Fixed-sized arrays cannot have elements added to the end if the array is full, but removing elements is fine. That's how a stack works.

Internally Ruby arrays are allocated as C-style arrays of a fixed size and are automatically resized as elements are added. As an optimization they are often re-sized a bit beyond what you need to avoid re-allocating on every single addition.

A linked-list is a different data structure that allows for more flexible insertion and removal, but is much slower to traverse and doesn't permit easy random access, things very important for an array structure.