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

Java

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
}

C++

Dynamic arrays are implemented in C++ as vectors

#include <vector>

Here are some methods available for vectors:

void push_back(const TYPE&) //adds an element to back of vector
void pop_back() //removes an element from back of vector
TYPE& front() //returns first element in vector
TYPE& back() //returns last element in vector
int capacity() //returns number of elements for which space is currently allocated
int size() //returns number of elements in the vector
bool empty() //returns true if there are 0 elements

This example puts 5 elements on a vector and takes them back off (acting like a stack)

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> v; //vector that holds integers
 
int main()
{
 
//this loop pushes 5 elements on the vector and tells you
//the size after each push
//the output is "1 2 3 4 5 "
for(int i=0; i<5; i++) {
    v.push_back(i);
    cout << v.size() << " ";
}
 
cout << endl;
 
//this loop pops elements off the vector until it is empty and tells you
//which one it is taking off
//the output is "4 3 2 1 0 "
while(!v.empty()) {
    cout << v.back() << " ";
    v.pop_back();
}
 
cout << endl;
 
return 0;
}