Lists

A list is an abstract data type representing an ordered sequence of values.

Common operations

Linked lists vs array-based lists

Lists are usually implemented with either a linked list or an array (usually a dynamic array ), with benefits and tradeoffs for each strategy.

In short, array-based lists allow $\mathcal{O}(1)$-time direct access , while adding or deleting elements takes $\mathcal{O}(n)$-time, in the worst case.

Linked lists allow $\mathcal{O}(1)$-time insertion or deletion, given references to the nodes preceding/succeeding the new or deleted element (such as at the start or end of the list). However, accessing an element by its position in the list requires traversing the list sequentially .

Wikipedia has a more detailed comparison of arrays and linked lists.

Array-based implementation

This class implements the ListADT interface with a dynamic array – when insertion would result in the underlying array exceeding its capacity, the data is copied to a larger one:

 1public class DynamicArrayList<E> implements ListADT<E> {
 2    private static final int DEFAULT_CAPACITY = 16;
 3
 4    private E[] data;
 5    private int size = 0;
 6
 7    public DynamicArrayList() { this(DEFAULT_CAPACITY); }
 8
 9    public DynamicArrayList(int capacity) { data = (E[]) new Object[capacity]; }
10
11    public int size() { return size; }
12
13    public boolean isEmpty() { return size == 0; }
14
15    public E get(int i) {
16        if (i < 0 || i >= size) throw new IndexOutOfBoundsException();
17        return data[i];
18    }
19
20    public void set(int i, E e) {
21        if (i < 0 || i >= size) throw new IndexOutOfBoundsException();
22        data[i] = e;
23    }
24
25    public void add(int i, E e) {
26        if (i < 0 || i > size) throw new IndexOutOfBoundsException();
27        if (size == data.length) resize(data.length * 2);
28        for (int j = size - 1; j >= i; j--) data[j + 1] = data[j];
29        data[i] = e;
30        size++;
31    }
32
33    public void remove(int i) {
34        if (i < 0 || i>= size) throw new IndexOutOfBoundsException();
35        for (int j = i; j < size - 1; j++) data[j] = data[j + 1];
36        data[--size] = null;
37    }
38
39    private void resize(int capacity) {
40        var resized = (E[]) new Object[capacity];
41        for (int i = 0; i < size; i++) resized[i] = data[i];
42        data = resized;
43    }
44}