ArrayList и LinkedList. Свойства, различия, методы работы.

Сегодня поговорим о ArrayList  и LinkedList. Что общего, чем различаются, скорость работы, методы и свойства.

ArrayList  и LinkedList реализуют интерфейс List и  наследует свою функциональность от класса AbstractList.

В Java массивы имеют фиксированную длину, и после того как массив создан, он не может увеличиваться  или уменьшаться. ArrayList может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта (по умолчанию будет создан массив из 10-ти элементов) . ArrayList это список, реализованный на основе массива.

Основное о ArrayList :

Создание :

ArrayList list = new ArrayList();

Если вызывается конструктор без параметров, то по умолчанию будет создан массив из 10-ти элементов типа Object (с приведением к типу, разумеется ).  Можно использовать конструктор ArrayList(capacity) и указать свою начальную емкость списка. Например :
ArrayList list = new ArrayList(5);

Добавление элементов :

list.add("a");

Добавление элемента происходит в несколько этапов :

1. Проверяется достаточно ли места в массиве для добавления нового элемента;
2. Добавляется элемент в конец массива (в данном примере);
3. Если места в массиве недостаточно то рассчитывается новый размер массива, в него копируется старый массив и уже после этого происходит добавление нового элемента.

Добавление элемента "внутрь" списка :

list.add(4, "a");

Такое добавление происходит с помощью вышеописанных этапов.

В случае, когда в исходный список необходимо добавить другую коллекцию, еще и «внутрь», стоит использовать метод addAll(index, Collection). Такой способ будет значительно быстрее поэлементного добавления.

Удаление по индексу :

list.remove(2);

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

Удаление по значению :

list.remove("a"); 

При удалении по значению, в цикле просматриваются все элементы списка, до тех пор пока не будет найдено соответствие. Удален будет лишь первый найденный элемент. Поэтому если нужно удалить все элементы по значению нужно самому в цыкле просматривать все элементы. Например :

ArrayList list1 = new ArrayList(10);

list1.add("d");
list1.add("d"); 

ListIterator it = list1.listIterator();
while (it.hasNext())
{
    if (it.next().equals("d"))
        it.remove();
}

Основное о LinkedList:

Является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы.

Создание :

List list = new LinkedList();

Добавление элементов :

в конец списка : add(value) addLast(value);

в начало списка с помощью addFirst(value);

внутрь списка : add(index, value);

 

Удаление  :

из начала или конца списка с помощью removeFirst(), removeLast();
по индексу remove(index) и по значению remove(value);

При удалении по значению будут просмотрены все значения и будет удален первый найденный элемент.

Перебор значений :

для перебора значений можно воспользоваться итераторами. Пример :

ListIterator iterator = list.listIterator();
while (iterator.hasNext())
{
    String a = iterator.next();
    System.out.println(a);
}

 Сравнение времени работы разных методов :