A way of organizing data that enables efficient storage, retrieval, and use. An array is just a sequence of elements stored linearly.

See Contiguous allocation.

Languages such as C# and Java have fixed-length arrays, not Python though.

Arrays vs Lists?

An array is useful when you know the data is fixed length, or unlikely to grow much. It is better when you will be doing lots of indexing into it, i.e. you know you will often want the third element, or the fifth, or whatever.

On the other hand, if you don’t know how many elements you’ll have, use List. Also, definitely use a List any time you want to add/remove data, since resizing arrays is expensive.

Memory footprint
Array elements are stored contiguously in the memory, elements of a list are not. Data next to each other can be read sequentially very fast. Much faster than data scattered all over the place.

Resizable array (aka List, ArrayList)

A list is basically an array without a fixed length.
We want to use that when we don’t know the capacity upfront, to grow as necessary.

Resizable array in C#: List (ArrayList belongs to the days that C# didn’t have generics. It’s deprecated in favor of List.)
Resizable array in Java: ArrayList

Implementation with Array

Watch for the ArrayIndexOutOfBoundsException when implementing a list backed by an array.

List<T>/ArrayList is basically backed by an Array which is usually bigger than the current number of items. The elements are put in an array, and a new array is created when the old one runs out of space. The resizing factor is 2 in Java. The new array is twice the size of the old one. The vast majority of the time, there will be space in the array when you add something to it.

This is fast for access by index but slow at removing or inserting elements within the list or at the start. Adding/removing entries at the end of the list is reasonably cheap.

Time Complexities

Add / Append
When Appending an item, only on rare occasions, the array will hit its capacity and you will recreate a new one (of double size) and copy all the elements over. This happens so rarely, that on average, we still have this constant time (O(1)).
Even though we have this periodic time when adding is actually linear time (O(N)).

Append vs Insert
Appending elements is efficient because we are using the free slots at the end, but inserting elements can be slow because all elements in the List after the insertion point have to be shifted to make a free slot

Search
In case of searching, it is efficient if the BinarySearch method is used on a list that has been sorted, if you use any other search algorithms is inefficient because each item must be individually checked.

Example

package com.sandbox;

import java.util.Arrays;

public class ArrayListEmpty {

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

        System.out.println("Removing...");

        list.removeAt(0);
        list.removeAt(0);
        list.removeAt(0);
        list.removeAt(0);
        list.removeAt(0);
        list.removeAt(0);
        list.removeAt(0);
        list.removeAt(0);
        list.removeAt(0);
        list.removeAt(0);
    }

    public static class MyArrayList {

        private final static int DEFAULT_SIZE = 2;
        private final static int RESIZING_FACTOR = 2;

        private int[] items;
        private int count = 0;

        public MyArrayList() {
            items = new int[DEFAULT_SIZE];
        }

        public void add(final int value){
            if (count >= items.length) {
                expandArray();
            }
            items[count] = value;
            count++;
            System.out.println(this.toString());
        }

        public void removeAt(final int index){
            for (int i = index; i < items.length && (i+1) < items.length; i++) {
                if (i == index) {
                    count--;
                }
                items[i] = items[i+1];
            }
            System.out.println(String.format("Removed at %s, items = %s", index, this.toString()));
        }

        public int get(final int i){
            return items[i];
        }

        private void expandArray() {
            int[] tmp = new int[items.length * RESIZING_FACTOR];
            for (int i = 0; i < items.length; i++) {
                tmp[i] = items[i];
            }
            items = tmp;
        }

        @Override
        public String toString() {
            return String.format("count = %s, items: %s", count, Arrays.toString(items));
        }
    }
}

Recommended resources

Arrays:

https://www.hackerrank.com/topics/arrays
https://www.tutorialspoint.com/java/java_arrays.htm
https://www.dotnetperls.com/array

Resizable array:

https://www.hackerrank.com/topics/arraylist

http://csharp.net-informations.com/collection/list.htm