ArrayLists

An ArrayList is an array that resizes itself while still providing O(1) access.

When the array is full, the array doubles in size.

• Each doubling takes O(n) time, but amortized insertion time still O(1)
• Actual resizing value may vary between languages

Implementation

#include <iostream>

using namespace std;

template <class T>
class ArrayList {
public:
    ArrayList() {
        maxsize = 2;
        list = new T[maxsize];
        numitems = 0;
    }

    void insert(T item);
    int indexOf(T item);
    void remove(int index);
    T getAtIndex(int index);

private:
    T *list;
    int numitems;
    int maxsize;
    void expand();
};

template <class T>
void ArrayList<T>::insert(T item) {
    if (numitems >= maxsize) {
        expand();
    }
    list[numitems] = item;
    numitems++;
}

template <class T>
int ArrayList<T>::indexOf(T item) {
    for (int i = 0; i < numitems; i++) {
        if (list[i] == item) return i;
    }

    return -1;
}

template <class T>
void ArrayList<T>::remove(int index) {
    if (index >= numitems) {
        cout << "Remove error: index out of bounds." << endl;
        return;
    }

    for (int i = index; i < numitems - 1; i++) {
        list[i] = list[i + 1];
    }
    numitems--;
}

template <class T>
T ArrayList<T>::getAtIndex(int index) {
    return list[index]
}

template <class T>
void ArrayList<T>::expand() {
    int newsize = maxsize * 2;
    T *temp = new T[newsize];
    for (int i = 0; i < numitems; i++) {
        temp[i] = list[i];
    }
    maxsize = newsize;
    list = temp;
}