My notes on Dynamic array with an implementation in Java.
You can find the complete code for this and other data structures here: data structures and algorithms
A dynamic array is a data structure that uses a normal array but allows to increase the size (and in some cases decrease it) to hold more elements.
Common Operations for an array list includes:
| Operation | Complexity |
|---|---|
| get(indexOfElement) | O(1) |
| add(value) | O(1) |
| insert(index, value) | O(n) |
| delete(value) | O(n) |
This is the add operation
/** * adds a value at the end of the array * - puts a value at size and then increases size by 1 * - if size is equals to the inner array size we need to grow the inner * array, we achieve this by instanciating a new array doubling the size * of the previous array and we copy the elements to the array. * O(1) amortised (because we dont enlarge at every insertion) **/ public void add(T value) { if (size == innerArray.length) { T newArray[] = (T[]) new Object[innerArray.length * 2]; System.arraycopy(innerArray, 0, newArray, 0, innerArray.length); innerArray = newArray; } innerArray[size] = value; size++; } And the remove operation
/** * removes a value at any valid index and moves other values one position * O(n) **/ public void remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(); } for(int i = index + 1; i < size; i++) { innerArray[i - 1] = innerArray[i]; } size--; } Other operations are very similar to a normal array.
Download the complete code for this and other data structures here: data structures and algorithms
Top comments (0)