— Если ты думаешь, что на интерфейсе List все закончилось, то ты ошибаешься, все только начинается. Давай я тебе расскажу про коллекции LinkedList и ArrayList.
Начну с коллекции ArrayList.
Вот как эта коллекция выглядит на схеме наследования:
Зеленым отмечены интерфейсы.
Фиолетовым – абстрактные классы.
Красным – обычные классы.
Сплошная линия – наследование, пунктирная – реализация интерфейса.
Это самая простая коллекция. Внутри ArrayList хранит элементы в простом массиве.
Основное преимущество такой коллекции над массивом – это расширяемость – увеличение длины при надобности.
Если в этом массиве заканчивается место, то создаётся второй массив побольше, куда копируются все элементы из первого. Затем второй массив занимает место первого, а первый – выбрасывается (будет уничтожен сборщиком мусора).
— А насколько увеличивается массив?
— Длина нового массива рассчитывается так (3*n)/2+1, где n – это длина старого массива. Т.е. если старый массив был длиной 100 элементов, то новый будет 300/2+1 = 151.
При добавлении элемента в середину ArrayList, все элементы справа от него копируются на 1 позицию вправо, а затем в пустую ячейку добавляется новый элемент.
При удалении элемента из середины, все элементы справа от него копируются на 1 позицию влево.
— Ты говоришь, что ArrayList сам удлиняется, при добавлении элементов в него. А при удалении он сам укорачивается?
— Нет, сам внутренний массив в ArrayList никогда не укорачивается, но можно заставить ArrayList уменьшить свой внутренний массив до минимального уровня, если вызвать метод trimToSize().
Ну, и конечно, расскажу о LinkedList.
Вот как выглядит его схема наследования:
Зеленым отмечены интерфейсы.
Фиолетовым – абстрактные классы.
Красным – обычные классы.
Сплошная линия – наследование, пунктирная – реализация интерфейса.
Как ты уже знаешь, LinkedList хранит элементы в виде связного списка.
— Я постоянно об этом слышу, но не могла бы ты рассказать, что это такое?
— Конечно. Все просто.
Связный список состоит из одинаковых элементов, которые а) хранят данные, б) хранят ссылки на следующий и предыдущий элементы.
Вот так бы выглядел класс такого элемента для хранения строк:
Пример | Описание |
---|---|
|
data хранит строковое значение элемента. next хранит ссылку на следующий элемент в списке. 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;
— Спасибо, Элли, действительно узнал о списках много нового.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ