Какая сложность доступа к последнему элементу ArrayList?

Сложность доступа к последнему элементу ArrayList

Доступ к последнему элементу в ArrayList имеет алгоритмическую сложность O(1) - константное время. Это один из главных преимуществ ArrayList перед LinkedList.

Почему O(1)?

ArrayList внутренне использует массив и хранит индекс размера:

public class ArrayList<E> {
    private Object[] elementData;  // Внутренний массив
    private int size;              // Количество элементов
    
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return elementData[index];  // O(1) - прямой доступ
    }
    
    public E getLast() {  // Java 21+
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return get(size - 1);  // O(1)!
    }
}

Доступ к последнему элементу это просто:

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.add("E");

// list.size = 5
// list.elementData = [A, B, C, D, E, null, null, ...]
//                     0  1  2  3  4

String last = list.get(list.size() - 1);  // list.get(4) - O(1)
// или
String last = list.get(4);  // Прямой доступ к индексу 4 - O(1)

На самом деле это просто доступ в массив по индексу, который работает за O(1).

Визуально

Memory address:  0x1000  0x1001  0x1002  0x1003  0x1004  ...
                  ↓       ↓       ↓       ↓       ↓
ElementData:    ["A"]   ["B"]   ["C"]   ["D"]   ["E"]   ...
                  0       1       2       3       4
                                                   ↑
                                   Последний элемент
                                   list.size() - 1 = 4
                                   Доступ: O(1)

Практический пример

public class ArrayListAccessDemo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        
        // Добавляем 100 млн элементов
        System.out.println("Adding 100M elements...");
        for (int i = 0; i < 100_000_000; i++) {
            list.add(i);
        }
        
        // Доступ к последнему элементу - всё ещё O(1)!
        System.out.println("Accessing last element...");
        long start = System.currentTimeMillis();
        
        for (int i = 0; i < 1_000_000; i++) {
            int last = list.get(list.size() - 1);  // O(1) каждый раз
        }
        
        long duration = System.currentTimeMillis() - start;
        System.out.println("1M accesses to last element took: " + duration + "ms");
        
        // Вывод: примерно 5-10ms (очень быстро)
        // Если бы было O(n), то заняло бы миллиарды операций!
    }
}

Сравнение с LinkedList

ArrayList:

ArrayList<String> list = new ArrayList<>();
// ...
String last = list.get(list.size() - 1);  // O(1) ✅

LinkedList:

LinkedList<String> list = new LinkedList<>();
// ...
String last = list.getLast();              // O(1) ✅
// или
String last = list.get(list.size() - 1);  // O(n) ❌ - нужно пройти все элементы

Да, LinkedList имеет метод getLast() с O(1), потому что хранит ссылку на последний узел. Но get() по индексу - это O(n).

Таблица сложностей

Важный момент: Caching/CPU optimization

Даже на низком уровне доступ к последнему элементу очень быстрый благодаря работе CPU:

ArrayList<Long> list = new ArrayList<>();
for (int i = 0; i < 10_000_000; i++) {
    list.add((long) i);
}

// Измеряем время доступа к разным позициям

long start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    list.get(0);  // Начало - O(1)
}
long firstTime = System.nanoTime() - start;

start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    list.get(5_000_000);  // Середина - O(1), но медленнее из-за cache miss
}
long middleTime = System.nanoTime() - start;

start = System.nanoTime();
for (int i = 0; i < 1_000_000; i++) {
    list.get(9_999_999);  // Конец - O(1)
}
long lastTime = System.nanoTime() - start;

System.out.println("First: " + firstTime);
System.out.println("Middle: " + middleTime);  // Может быть медленнее из-за cache
System.out.println("Last: " + lastTime);

// Но все остаются O(1) на algorithmic level!

Практическое применение

// Проверить пуст ли список и получить последний элемент
public <T> T getLastOrNull(ArrayList<T> list) {
    return list.isEmpty() ? null : list.get(list.size() - 1);  // O(1)
}

// Удалить последний элемент
public <T> T removeLast(ArrayList<T> list) {
    if (list.isEmpty()) {
        throw new EmptyStackException();
    }
    return list.remove(list.size() - 1);  // O(1)
}

// Stack на основе ArrayList
public class Stack<T> {
    private ArrayList<T> data = new ArrayList<>();
    
    public void push(T element) {
        data.add(element);  // O(1) аморт
    }
    
    public T pop() {
        return data.remove(data.size() - 1);  // O(1)
    }
    
    public T peek() {
        return data.get(data.size() - 1);  // O(1) ← Вот это!
    }
}

Важное уточнение для Java 21+

// Java 21 добавил специальный метод для последнего элемента
ArrayList<String> list = new ArrayList<>();
list.add("First");
list.add("Last");

String last = list.getLast();  // O(1) - удобнее чем get(size()-1)
String first = list.getFirst(); // O(1)

// Вместо:
String oldWay = list.get(list.size() - 1);  // Тоже O(1), просто менее удобно

Заключение

Доступ к последнему элементу ArrayList - это всегда O(1), потому что:

1. ArrayList использует внутренний массив
2. Доступ к элементу по индексу в массиве - это O(1)
3. Индекс последнего элемента всегда = size - 1
4. Вычисление size - 1 это O(1)
5. Поэтому list.get(list.size() - 1) = O(1) + O(1) + O(1) = O(1)

Это один из основных плюсов ArrayList - очень быстрый доступ к любому элементу по индексу, включая последний.