Dynamic Array

A dynamic array is simply an array with variable length. The array begins with a certain size and when that size is exceeded more memory is allocated and the size is increased accordingly. This means that while adding to the end of the array is $O(1)$ most of the time, when the maximum size is reached adding a new element is $O(n)$.

Operation Complexity Description
push back $O(1)$ puts an element on the end of the array
pop back $O(1)$ removes an element from the end of the array
push $O(n)$ adds an element to an arbitrary location within the array
pop $O(n)$ removes an element from an arbitrary location within the array
access $O(1)$ elements are adjacent in memory so access is done in constant time

In java, dynamic arrays are implemented by ArrayList. In this example, we shall make an ArrayList, add some strings, and finally empty it.

import java.util.*;
public static void main(String[] args){
    ArrayList al = new java.util.ArrayList();
    // Let's add an item
    // Add an item in the first position.
    // Now the order is b a
    // Removing an item in position 1
    // Now ll is just: a
    // 1
    // 0
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License