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 al.add("a"); // Add an item in the first position. al.add(0,"b"); // Now the order is b a // Removing an item in position 1 al.remove(1); // Now ll is just: a al.size(); // 1 al.clear(); al.size(); // 0 }
page revision: 8, last edited: 27 Apr 2008 03:40