CodeNewbie Community 🌱

Discussion on: Array vs ArrayList

Collapse
 
djuber profile image
Daniel Uber

In Java, C, and C++ arrays are "primitive" data types like ints and floats. The main characteristics of an array are (1) fixed size, (2) direct element access, in these languages supported using the square bracket index format.

In C++ there's std::vector which is a resizable, direct access collection of some type of thing. In Java they call this same concept ArrayList (it may work a little differently than std::vector but it covers the same use case). Wikipedia covers the general concept. The main change is the vector/array list is resizable or growable, if you push another item to the list and it exceeds the allocated space, it will move its content to another location with more space.

C's array type is all the language defines. Anything more complicated or featureful than that comes from a library or hand-rolled data structure. You could implement an array list yourself using a dynamically allocated array for internal storage, and re-allocating when the storage filled. You wouldn't have to use an array for backend storage if you found something else (you could use a linked list and pretend it was an array list, but random access to the n-th item would be a scan forward from the head of the list and it wouldn't perform as quickly as an array does).

I think this has implications for direct pointer access to the elements of the vector - if you had a pointer to the second location in an array, you could always access the third location by pointer arithmetic (the array's location is fixed in memory when you create it), but an array list could move the storage of the elements at any time without exposing that information to the end user, rendering a pointer invalid after adding or removing an element. In Java, you would always use the ArrayList accessor get(index) but in C++ you could do something dangerous there via pointers to a vector's content.