Arrays

What is an Arrays is ? : plain old data structure

int[] data = int[9];

3 things about array that you should know

• Can hold anything
• Fixed size / can’t grow
• Random access : O(1)

Example : build an array from scratch

public class DynamicArray<String> {

    private Object[] data;
    private int size;
    private int initialCapacity;

    public DynamicArray(int initialCapacity) {
        this.initialCapacity = initialCapacity;
        data = new Object[initialCapacity];
    }

    public void set(int index, String value) {
        this.insert(index, value);
    }

    public String get(int index) {
        return (String) data[index];
    }

    public void insert(int index, String value) {
        //Check size
        if (size == initialCapacity) {
            this.resize();
        }
        //Copy up
        for (int j = size; j > index; j--) {
            data[j] = data[j - 1];
        }
        // Insert
        data[index] = value;
        size++;
    }

    public void resize() {
        Object[] newData = new Object[initialCapacity * 2];
        for (int i = 0; i < initialCapacity; i++) {
            newData[i] = data[i];
        }
        data = newData;
        initialCapacity = initialCapacity * 2;
    }

    public void delete(int index) {
        //Copy down
        for (int j = index; j < size - 1; j++) {
            data[j] = data[j + 1];
        }
        size--;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(String value) {
        for(int i=0; i <size; i++) {
            if(data[i].equals(value)) {
                return true;
            }
        }
        return false;
    }
}

import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

public class DynamicArrayTest {

    private DynamicArray array;

    @BeforeEach
    void setUp() {
        array = new DynamicArray(2);
    }

    @Test
    void testSetGet() {
        array.set(0, "a");
        Assertions.assertThat("a").isEqualTo(array.get(0));
    }

    @Test
    void testInsert() {
        array.insert(0, "a");
        array.insert(1, "b");
        array.insert(2, "c");
        Assertions.assertThat("a").isEqualTo(array.get(0));
        Assertions.assertThat("b").isEqualTo(array.get(1));
        Assertions.assertThat("c").isEqualTo(array.get(2));
    }
}

Summary:

• Get/Set is O(1)
• Insert O(n)
• Delete O(n)
• Important features : random access, fixed capacity, double when resize

Example java code at here