Array vs. List

Posted on | In

An array is a data structure of fixed size. It contains a collection of elements of the same type. They are ordered and each element is identified by an array index. It is easy to access or modify any element in the array through the array index, and the time complexity is O(1).

1
2
3
4
5
6
7
// a one-dimensional array
String[] array = new String[16];
array[14] = "hello";

// a two-dimensional array, aka. matrix
int[][] matrix = new int[200][200];
matrix[10][0] = 123;

But it is a little more complex when an element is removed from the array or a new one is inserted in the array. To maintain the order of elements in the array, the right part of the array needs to be shifted to the left or to the right, and the time complexity is O(n).

1
2
3
4
5
6
int remove(int[] array, int len, int index) {
    for (int i = index; i < len - 1; i++) {
        array[i] = array[i + 1];
    }
    len--;
}

A list is a abstract data structure which consists of ordered elements of the same type. It is resizable. One of the concrete implementations of list is linked list, where elements are connected through pointers or references.

1
2
3
4
5
6
7
8
public class SingleLinkedListNode <T> {
    private T obj;
    private SingleLinkedListNode next;

    public SingleLinkedListNode(T obj) {
        this.obj = obj;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class SingleLinkedList {
    private SingleLinkedListNode head;

    public SingleLinkedList(T[] array) {
        if (array == null || array.length == 0) {
            throw new RuntimeException();
        }
        head = new SingleLinkedListNode(array[0]);
        SingleLinkedListNode pre = head;
        for (int i = 1; i < array.length; i++) {
            SingleLinkedListNode node = new SingleLinkedListNode(array[i]);
            pre.next = node;
            pre = node;
        }
    }
}

It takes O(n) to find the target element in a linked list, but it takes only O(1) to insert or remove an element in a linked list. Compared to array, linked list is more suitable for the senarios where the insertion and deletion operations are more needed than random access.

Implementation in Java

In Java, there is a utility class Arrays which provides various methods for manipulating arrays.

1
2
3
int[] numbers = {2, 5, 7, -5, -10, 9, 0};
Arrays.sort(numbers);
int index = Arrays.binarySearch(numbers, 7);

There are two mostly used implementations of List: ArrayList and LinkedList.
ArrayList is implemented by wrapping an fixed-size array, but it is resizable, its capacity grows automatically as elements are added to an ArrayList.
LinkedList is a doubly-linked list. Note that it provides the method get(int index), but the time complexity of the implementation is O(n) because it doesn’t maintain an index for each element.

Be aware that the utility class Arrays provides a method asList() for converting an array to an ArrayList, but this ArrayList is not the same as the one mentioned above. This ArrayList implements the List interface, but it is an inner class and its size is fixed.