Материал: 8

Итераторы в Java

Итератор имеет доступ к элементам некоторой коллекции и может работать с ней в определенном порядке. Методы интерфейса Iterator<E> (над коллекцией или набором элементов типа Е):

коллекции.

Цели изучения интерфейсов

-для того, чтобы ознакомиться с интерфейсом List;

-чтобы понять, как написать массив на основе реализации интерфейса List;

-изучить разницу между одно-, двусвязными, и циклическими связанными структурами данных в виде списков;

-чтобы узнать, как реализовать интерфейс List, используя связанный список;

-для того, чтобы понять, что такое интерфейс итератора.

Интерфейс List и класс ArrayList

Массив является индексируемой структурой: можно выбрать все элементы в произвольном порядке, используя значение индекса. К элементам можно получить последовательный доступ с помощью цикла, который увеличивает индекс.

Вы не можете:

-увеличивать или уменьшать длину;

-добавить элемент в указанную позицию без перемещения других элементов, чтобы освободить место;

ArrayList - самая часто используемая коллекция. ArrayList

инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов. Так как ArrayList

использует массив, то время доступа к элементу по индексу минимально (в отличии от LinkedList).

При удалении произвольного элемента из списка, все элементы, находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity) не изменяется. Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент.

LinkedList - Двусвязный список. Это структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и две ссылки («связки») на следующий и предыдущий узел списка.

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

Класс ArrayList

Довольно-таки простой класс, который реализует интерфейс List. Имеет улучшение по сравнению с массивами. Используется, если программист хочет добавить новые элементы в конец списка, но по-прежнему нуждается в возможности доступа к элементам, сохраненным в списке в произвольном порядке.

ArrayList является несихронизируемым динамически расширяемым массивом с эффективным доступом по индексу.

Пример:

ArrayList<Integer> arr =

new ArrayList<Integer>(10/*initialCapacity*/); arr.add(7);

ArrayList на самом деле не является списком (хотя реализует интерфейс List) Если вам нужен список, то используйте класс LinkedList.

Vector

Vector это и синхронизируемый динамически расширяемый массив массив с эффективным доступом по индексу.

Пример:

Vector<Integer> vec =

new Vector<Integer>(10/*initialCapacity*/); vec.add(7);

Vector является старым контейнером (Java 1.0) и сейчас гораздо реже используется, заменяется в основном ArrayList (Java 1.2), который не синхронизируется.

Generic Collections

Функция языка, представленная в Java 5.0 называется родовыми коллекциями (или дженериками. Дженерики позволяют определить коллекцию, содержащую ссылки на объекты определенного типа:

List<String> myList = new ArrayList<String>();

Где myList является списком объектов String, где строка является параметрическим типом. В myList можно хранить только ссылки на объекты типа String, и все извлекаемые элементы тоже имеют тип String.

Параметрические типы аналогичны параметрам методов. На рисунке 8.5 приведена спецификация класса ArrayList.

Рисунок 8.5 – Спецификация класса ArrayList

Применение ArrayList

ArrayList дает дополнительные возможности сверх того, что обеспечивают обычные массивы. Сочетание Автоупаковки(Autoboxing) с Generic Collection (коллекциями дженериков) дает вам возможность хранить и извлекать примитивные типы данных при работе с ArrayList.

Односвязные списки и двусвязные списки

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

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

Каждый элемент списка (узел) содержит информационные поля и ссылку на следующий узел, и необязательно, ссылку на предыдущий узел.

Узел списка