> For the complete documentation index, see [llms.txt](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/data-structures/array.md).

# Array & List

## Arrays

Arrays are usually fixed size collection of items. An array is a basic data structure that allocates memory that will hold our values.

> To push the arrays to the limits and see that an array really allocates memory, try to create array of huge size, like `int[] hugeArray = new int[2000000000]`. We should get `java.lang.OutOfMemoryError: Java heap space` exception with default JVM memory settings.

```
import java.util.Arrays;

public class ArraysDemo {

    public static void main(String... args) {
        int[] array = new int[5];
        array[0] = 3;
        array[1] = 4;
        array[2] = 6;
        array[3] = 8;
        array[4] = 1;

        int sum = 0;
        for(Integer value : array) {
            sum += value;
        }
        System.out.println(String.format("Sum is %s", sum));

        System.out.println(Arrays.toString(array));

        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
    }
}
```

Here is the output.

```
Sum is 22
[3, 4, 6, 8, 1]
[1, 3, 4, 6, 8]
```

## Lists

Lists are similar to arrays but they are dynamically expanding. Some languages do not distinguish between arrays and lists. A list implementations are using arrays to store values.

Here is a naive implementation of list. This list resizes the array when all the positions in the array are occupied and user requests to insert another item into a list.

```
import java.util.Arrays;

public class NaiveList {
    private String[] values = new String[5];
    private int currentIndex = 0;
    private int size = 0;

    public void add(String value) {
        if(size < values.length) {
            values[currentIndex++] = value;
            size++;
        } else {
            int newLength = values.length * 2;
            values = Arrays.copyOf(values, newLength);
            values[currentIndex++] = value;
            size++;
        }
    }

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

    public int size() {
        return size;
    }
}
```

We can use the naive implementation of list now.

```
import java.util.Arrays;

public class ListsDemo {

    public static void main(String... args) {
        NaiveList list = new NaiveList();
        list.add("John 1");
        list.add("John 2");
        list.add("John 3");
        list.add("John 4");
        list.add("John 5");
        list.add("John 6");
        list.add("John 7");
        list.add("John 8");
        list.add("John 9");
        list.add("John 10");

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}
```

Here is what the code above prints.

```
John 1
John 2
John 3
John 4
John 5
John 6
John 7
John 8
John 9
John 10
```

Here is another example with `add`, `get` and `remove` functions.

```
package datastructures;

class ArrayListTest {
    public static void main(String[] a) {
        ArrayList<Integer> list = new ArrayList<>();

        System.out.println(list);

        list.add(1);
        System.out.println(list);

        list.add(2);
        System.out.println(list);

        list.add(3);
        System.out.println(list);

        System.out.println(list.get(0));

        list.remove(1);
        System.out.println(list);
    }
}

public class ArrayList<E> {
    private E[] values;
    private int initialSize = 10;
    private int count;

    public ArrayList() {
        values = (E[]) new Object[initialSize];
    }

    public void add(E value) {
        if (count >= values.length) {
            resize();
        }
        values[count++] = value;
    }

    public void resize() {
        initialSize *= 2;
        E[] t = (E[]) new Object[initialSize];
        System.arraycopy(values, 0, t, 0, values.length);
        values = t;
    }

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

    public void remove(int index) {
        if (index < 0 || index >= count) throw new IndexOutOfBoundsException();
        values[index] = null;
        if (index < count - 1) {
            System.arraycopy(values, index + 1, values, index, count);
        }
        count--;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < count; i++) {
            sb.append(values[i]);
            if (i != count - 1) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
```