Array List
homogeneous data structure: all elements are of the same type (int, string, etc)
the cells are adjacent in memory -> it is possible to quickly calculate the address of any array cell, given the address of the first cell -> This property allows O(1) access
Question: In Java and C++, how is dynamic array implemented? Is it built based on an array?
Ans:
they allocate some default "large" amount of memory initially,
insert elements into this initial array, and once the array is full,
they create a new larger array (typically twice as large as the old array),
copy all elements from the old array into the new array,
and then replace any references to the old array with references to the new array.
In C++, the "dynamic array" is the vector data structure.
In Java, the "dynamic array" is ArrayList collection framework
Question: Array structures (e.g. the array, or the Java ArrayList, or the C++ vector , etc.) require that all elements be the same size. However, array structures can contain strings, which can be different lengths (and thus different sizes in memory). How is this possible?
Insertion: The best time complexity is O(1), while the worst is O(n)
find: The best time complexity is O(1), while the worst is O(n). In a sorted array, it can be O(logn)