Implementing an ArrayList from Scratch

An ArrayList is a resizable array data structure that allows O(1) access, insertion and removal at end. Implementing one from scratch models how it works under the hood.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class MyArrayList {
  private Object[] elementData;
  private int size;

  public MyArrayList(int capacity) {
    elementData = new Object[capacity];
  }

  public void add(Object element) {
    ensureCapacity(size + 1); 
    elementData[size++] = element;
  }

  private void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length) {
      elementData = Arrays.copyOf(elementData, 2 * minCapacity);
    }
  }

  // Other methods like get, remove, etc.
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MyArrayList {
private:
  int capacity;
  int size;
  int* elementData;

public:
  MyArrayList(int capacity) {
    this->capacity = capacity;
    elementData = new int[capacity];
    size = 0;
  }

  void add(int element) {
    if (size == capacity) {
      grow();
    }
    elementData[size++] = element;
  }

  void grow() {
    capacity *= 2;
    auto newData = new int[capacity];
    copy(elementData, elementData + size, newData);
    delete[] elementData;
    elementData = newData;
  }

  // Other methods
};

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class MyArrayList:

  def __init__(self, capacity):
    self.capacity = capacity
    self.size = 0
    self.elements = [None] * capacity

  def add(self, element):
    if self.size == self.capacity:
      self.grow()
    self.elements[self.size] = element
    self.size += 1
  
  def grow(self):
    self.capacity *= 2
    new_elements = [None] * self.capacity
    for i in range(self.size):
      new_elements[i] = self.elements[i]
    self.elements = new_elements

# Other methods  

Implementing core data structures helps better understand how they function and make design choices.

An ArrayList is a dynamic array, which means its size can be changed during runtime. Unlike a traditional array, which has a fixed size, an ArrayList can grow and shrink as needed. Implementing an ArrayList from scratch involves creating a resizable array. This generally involves maintaining an internal array and resizing it when elements are added or removed beyond its current capacity.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class MyArrayList {
    private int[] arr;
    private int size;
    
    public MyArrayList() {
        arr = new int[10];
        size = 0;
    }

    public void add(int value) {
        if (size == arr.length) {
            resize();
        }
        arr[size++] = value;
    }

    private void resize() {
        int[] newArr = new int[arr.length * 2];
        System.arraycopy(arr, 0, newArr, 0, size);
        arr = newArr;
    }

    public int get(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException();
        }
        return arr[index];
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstring>
using namespace std;

class MyArrayList {
    int* arr;
    int size;
    int capacity;

public:
    MyArrayList() : size(0), capacity(10) {
        arr = new int[capacity];
    }

    void add(int value) {
        if (size == capacity) {
            resize();
        }
        arr[size++] = value;
    }

    void resize() {
        capacity *= 2;
        int* newArr = new int[capacity];
        memcpy(newArr, arr, size * sizeof(int));
        delete[] arr;
        arr = newArr;
    }

    int get(int index) {
        if (index >= size || index < 0) {
            throw out_of_range("Index out of range");
        }
        return arr[index];
    }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class MyArrayList:
    def __init__(self):
        self.arr = [None] * 10
        self.size = 0

    def add(self, value):
        if self.size == len(self.arr):
            self.resize()
        self.arr[self.size] = value
        self.size += 1

    def resize(self):
        new_arr = [None] * (2 * len(self.arr))
        for i in range(self.size):
            new_arr[i] = self.arr[i]
        self.arr = new_arr

    def get(self, index):
        if index >= self.size or index < 0:
            raise IndexError("Index out of range")
        return self.arr[index]

This should give you an idea of how to build an ArrayList from scratch. In each language, the data structure includes methods for adding an element, resizing the internal array, and accessing an element by index.