Dynamic Arrays

Intro

DynamicArrays are Arrays that aren’t static and don’t have fixed sizes, meaning they can grow and shrink based on the number of elements within. They’re technically an AbstractDataType that looks and functions like a regular array.

Implementation

Instead of storing a pointer to the array’s actual address, we store a pointer to dynamically allocated array that gets replaced by a newly-allocated array when needed. So when more elements are added to the array than it can actually handle, a new one is allocated, the elements are copied, and the dynamic pointer is updated.

Necessary Operations

• get(i): access and return element at index i.
• set(i, v): set value of element at i to equal v.
• pushBack(val): add val to the end.
• remove(i): removes element at i.
• size(): returns the size of the array.

Stored info:

• arr: the dynamically allocated array.
• capacity: the size of the dynamically allocated array
• size: the number of elements currently in the array.

When more elements are added and size == capacity , we initialize a new dynamically allocated array that’s double the size of the previous one. Update the arr pointer and size and capacity values.

Common examples

Some languages provide dynamic arrays right out of the box. C++ has Vectors, Java has ArrayList, and Python’s List (which is the only type of array.

Time Complexity

A properly implemented dynamic array should have the same time complexity for its operations

---

References

• Dynamic Arrays