Реализации интерфейса List

— Если ты думаешь, что на интерфейсе List все закончилось, то ты ошибаешься, все только начинается. Давай я тебе расскажу про коллекции LinkedList и ArrayList.

Начну с коллекции ArrayList.

Вот как эта коллекция выглядит на схеме наследования:

Зеленым отмечены интерфейсы.

Фиолетовым – абстрактные классы.

Красным – обычные классы.

Сплошная линия – наследование, пунктирная – реализация интерфейса.

Это самая простая коллекция. Внутри ArrayList хранит элементы в простом массиве.

Основное преимущество такой коллекции над массивом – это расширяемость – увеличение длины при надобности.

Если в этом массиве заканчивается место, то создаётся второй массив побольше, куда копируются все элементы из первого. Затем второй массив занимает место первого, а первый – выбрасывается (будет уничтожен сборщиком мусора).

— А насколько увеличивается массив?

— Длина нового массива рассчитывается так (3*n)/2+1, где n – это длина старого массива. Т.е. если старый массив был длиной 100 элементов, то новый будет 300/2+1 = 151.

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

При удалении элемента из середины, все элементы справа от него копируются на 1 позицию влево.

— Ты говоришь, что ArrayList сам удлиняется, при добавлении элементов в него. А при удалении он сам укорачивается?

— Нет, сам внутренний массив в ArrayList никогда не укорачивается, но можно заставить ArrayList уменьшить свой внутренний массив до минимального уровня, если вызвать метод trimToSize().

Ну, и конечно, расскажу о LinkedList.

Вот как выглядит его схема наследования:

Зеленым отмечены интерфейсы.

Фиолетовым – абстрактные классы.

Красным – обычные классы.

Сплошная линия – наследование, пунктирная – реализация интерфейса.

Как ты уже знаешь, LinkedList хранит элементы в виде связного списка.

— Я постоянно об этом слышу, но не могла бы ты рассказать, что это такое?

— Конечно. Все просто.

Связный список состоит из одинаковых элементов, которые а) хранят данные, б) хранят ссылки на следующий и предыдущий элементы.

Вот так бы выглядел класс такого элемента для хранения строк:

class LinkedListElement
{
String data;
LinkedListElement next;
LinkedListElement previous;
}

А если использовать generics для типа данных, то будет что-то типа такого:

class LinkedListElement<T>
{
 T data;
 LinkedListElement<T> next;
 LinkedListElement<T> previous;
}

— Ясненько.

— Давай, для лучшего понимания, напишем код, где добавим в двусвязный список 10 элементов:

public static void main(String[] args)
{ 
 LinkedListElement<Integer> tail; //хвост (самый последний элемент) списка

 for(int i=0;i<10;i++)
 {
  LinkedListElement<Integer> element = new LinkedListElement<Integer>();
  element.data = i;

  if (tail == null) //если в хвосте нет элементов, сделать наш элемент последним
  {
   tail = element;
  }
  else //если хвост есть, добавить элемент
  {
   tail.next = element; //добавляем хвосту ссылку на следующий элемент
 element.previous = tail; //добавляем новому элементу ссылку на хвост
   tail = element; //объявляем новый элемент хвостом.
  }
 }
}

Допустим у нас в списке 10 элементов, вот как вставить элемент в середину:

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

Ярко-фиолетовым выделены новые ссылки – ссылки нового элемента на его соседей.

А теперь – кодом:

//тут содержится элемент – голова списка
LinkedListElement<Integer> head = … 

//получаем 4-й элемент (нумерация с нуля)
LinkedListElement<Integer> element4 = head.next.next.next.next; 
//получаем 5-й элемент
LinkedListElement<Integer> element5 = element4.next;

//Создаем новый элемент, который будем вставлять
LinkedListElement<Integer> newElement = new LinkedListElement<Integer>();
newElement.data = -18;

//обмениваемся ссылками с элементом слева
newElement.previous = element4;
element4.next = newElement;

//обмениваемся ссылками с элементом справа
newElement.next = element5;
element5.previous = newElement;

— Спасибо, Элли, действительно узнал о списках много нового.