List

I.Alfer

List работает на основе индексов.

Реализации List:

ArrayList
Vector
LinkedList

Vector

Vector - это такой же ArrayList, только все его методы синхронизированны

ArrayList

По сути это обертка обычного массива, которая предоставляет возможность увеличивать его capacity.

ArrayList работает на основе массива, а у любого массива должен быть объём. У него вместимость по умолчанию

private static final int DEFAULT_CAPACITY = 10;

Все элементы хроняться в массиве Object

transient Object[] elementData; // non-private to simplify nested class access

2 основных конструктора

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

При добавлении в ArrayList используется метод add()

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

Мы передаём эл-т, нам нужно увеличить сайз ArrayList на один. Но сначало нужно проверить если место в нашей коллекции для добавления эл-та

ensureCapacityInternal(size + 1);

Т.е. сначало вычисляется вместимость

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

И затем, в зависимости от объёма нашей новой коллекции эл-т или добавляется или же, если для него нет места вызывается метод grow() для увеличения нашей коллекции

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

метод grow в свою очередь

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Вычисляет старый capacity

int oldCapacity = elementData.length;

Вычисляет новый capacity для нашего ArrayList -> берётся старый capacity и складывается с старый капасити сдвинутый вправо на 1бит (При каждом сдвиге вправо выполняется деление на два с отбрасыванием любого остатка. Данная операция намного эффективнее, чем обычное деление на два, поэтому часто используется в сложных вычислениях. При этом нужно быть уверенным, что никакие биты не будут сдвинуты за пределы правой границы.)

int newCapacity = oldCapacity + (oldCapacity >> 1);

далее идут проверки. И как результат все наши эл-ты копируются в новый(увеличенный) массив

LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Он имплементирует очереди, но сейчас о нем, как о листе

LinkedList - двунаправленный связный список. Добавляет эл-ты в начало и в конец. У него есть первый и последний эл-т

transient Node<E> first;
transient Node<E> last;

Когда добавляется в начало или в конец новый эл-т сохраняется ссылка на эл-т который был первым/последний до этого

Хранит информацию в объекте Node(inner static class)

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Он хранит ссылки на текущий эл-т, следующий и предыдущий. Если это 1ый или последний эл-т, то сылка на следующий/предыдущий будет null.

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

 System.arraycopy(elementData, index, elementData, index + 1,
                 size - index);

В LinkedList это сделано проще. Он меняет ссылки на объект у следующего и предыдущего эл-та. Но при добавлении/удалении в/из середины, до этого эл-та нужно добраться(перебирается коллекция до нужного эл-та) и потом эл-т добавляется/удаляется. В ArrayList такой проблемы нет. Доступ к эл-там происходит очень быстро(по индексу)

Почти в 100% ArrayList будет работать быстрее. LinkedList выигрывает если мы будем получать/добавлять/удалять эл-ты только с начала или конца

Так как LinkedList имплементит Deque, у него есть и методы очередей

peek() - получить эл-т

poll() - возвращает и удаляет из коллекции эл-т

List

Report Page