List
I.AlferList работает на основе индексов.
Реализации 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() - возвращает и удаляет из коллекции эл-т