Коллекции (Collections) в Java. List. Академия современного программирования
What is ArrayList in Java?
ArrayList is a data structure that can be stretched to accommodate additional elements within itself and shrink back to a smaller size when elements are removed. It is a very important data structure useful in handling the dynamic behavior of elements.
Wondering how ArrayList java could be useful, see the below conversation -
See the following picture of a man stretching an elastic rubber band.
The actual length of the rubber band is much smaller, but when stretched it can extend a lot more than its actual length and can be used to hold/bind much larger objects with it.
Now, consider the next picture, that of a simple rope, it cannot stretch and will have a fixed length.
It can grow as, and when required to accommodate the elements it needs to store and when elements are removed, it can shrink back to a smaller size.
So as our friend has an issue with the array he is using cannot be expanded or made to shrink, we will be using ArrayList.
Arrays are like the rope shown in the above picture; they will have a fixed length, cannot be expanded nor reduced from the original length.
So our stretchable rubber-band is much like the Array List whereas the rope can be considered as the array.
Technically speaking, java Array List is like a dynamic array or a variable-length array.
Let us see and understand the following code snippet that will help you work around with Array List.
ArrayList
ArrayList Methods
ArrayList add : This is used to add elements to the Array List. If an ArrayList already contains elements, the new element gets added after the last element unless the index is specified.
Add(Object o);
ArrayList remove : The specified element is removed from the list and the size is reduced accordingly. Alternately, you can also specify the index of the element to be removed.
Remove(Object o);
Java array size : This will give you the number of elements in the Array List. Just like arrays, here too the first element starts with index 0.
Int size();
ArrayList contains : This method will return true if the list contains the specified element.
Boolean contains(Object o);
Java ArrayList Example
import java.util.ArrayList; class Test_ArrayList { public static void main(String args) { //Creating a generic ArrayList ArrayList arlTest = new ArrayList(); //Size of arrayList System.out.println("Size of ArrayList at creation: " + arlTest.size()); //Lets add some elements to it arlTest.add("D"); arlTest.add("U"); arlTest.add("K"); arlTest.add("E"); //Recheck the size after adding elements System.out.println("Size of ArrayList after adding elements: " + arlTest.size()); //Display all contents of ArrayList System.out.println("List of all elements: " + arlTest); //Remove some elements from the list arlTest.remove("D"); System.out.println("See contents after removing one element: " + arlTest); //Remove element by index arlTest.remove(2); System.out.println("See contents after removing element by index: " + arlTest); //Check size after removing elements System.out.println("Size of arrayList after removing elements: " + arlTest.size()); System.out.println("List of all elements after removing elements: " + arlTest); //Check if the list contains "K" System.out.println(arlTest.contains("K")); } }Size of ArrayList at creation: 0 Size of ArrayList after adding elements: 4 List of all elements: See contents after removing one element: See contents after removing element by index: Size of arrayList after removing elements: 2 List of all elements after removing elements: true
Note: For simplicity, the elements shown in above code are single character elements. We can add Strings, integers, etc. too.
При создании таких игр как "Змейка" или "Морской бой" было удобно использовать двумерный массив для хранения данных игрового поля. Но использование только массивов будет не очень удобным при создании игры "Пасьянс-Косынка". В играх "Змейка", "Морской бой" размеры игровых полей были фиксированного размера и не изменялись во время игры. Массив удобен для хранения, изменения и использования фиксированного набора значений. В игре "Пасьянс-Косынка" нам понадобится хранить наборы значений,количество которых можно увеличивать или уменьшать. В этом нам поможет список значений,который в языке Javaможно реализовать с помощью классаArrayList:
//Подключаем класс ArrayList
import java.util.ArrayList;
Рассмотрим примеры работы со списком на примере списка целых чисел.
Прежде всего, создадим пустой список значений целых чисел:
// Подключаем классArrayList
import java.util.ArrayList;
public class kosinka {
public static void main(String args) {
//Создаем пустой список значений целых чисел
ArrayList
Внутри угловых скобок указывается тип элементов списка
ArrayList
Но сейчас мы будем рассматривать список целых чисел. Работа со списками разных типов значений происходит по одинаковой схеме.
Изначально список пустой:
ArrayList
Добавим в него три новых элемента с помощью метода add():
// Создаем пустой список значений целых чисел
ArrayList
//Добавим первый элемент в список
//Добавим второй элемент в список
//Добавим третий элемент в список
Добавление элементов происходит в конец списка (см. рис. 10).
Теперь рассмотрим основные приемы работы со списком:
// Получаем количество элементов в списке
// В данном случае – три (см. рис. 10)
int kol = lst.size();
// Получение значения элемента по номеру
// В данном случае – 100 (см. рис. 10)
int val = lst.get(0);
// Удаление элемента из списка по номеру
// В данном случае – самый верхний (см. рис. 10)
// Удаление всех элементов из списка
С помощью метода size()можно определить количество элементов в списке.
Метод get()позволяет получить значение любого элемента по номеру, нумерация начинается с нуля. Метод remove()удаляет элемент из списка по его номеру, нумерация начинается с нуля.После удаления элемента список автоматически сжимается. Метод clear() позволяет удалить сразу все элементы из списка. Также как и в массиве, каждый элемент списка имеет свой номер. Самый первый элемент списка имеет номер нуль 0, а самый последний элемент имеет номер size()-1. Этих методов работы со списком будет достаточно при создании игры "Пасьянс-Косынка". На игровом поле будут находиться карты,разложенные в несколько стопок.Пользователь будет переносить карты из одной стопки в другую. Карты будут добавляться в конец стопки карт. Поэтому всех перечисленных выше методов будет достаточно.
В этой статье речь пойдет о, пожалуй, наиболее часто используемых коллекциях List, а именно о таких классах как AbstractList, ArrayList, LinkedList.
List - упорядоченная коллекция иногда называемая списком или последовательностью. Список может содержать повторяющиеся элементы. Разработчик имеет абсолютный контроль над тем, в каком месте списка будет вставлен каждый элемент. Также пользователь может получить доступ к элементам списка по индексу. В дополнение к стандартным операциям интерфейса Collection, List содержит следующие:
- Доступ по позиции ;
- Поиск ;
- Диапазон элементов (sublist) .
Доступ по позиции - манипулирует элементами на основе их индексной позиции в списке.
Не взирая на то, что в интерфейсе List присутствуют методы для доступа к элементу по позиции (индексу), делать это не рекоммендуется. В некоторых реализациях списка (например, LinkedList), эти операции могут выполнятся за время, пропорциональное значению индекса.
Поиск - находит указанный элемент и возвращает его позицию в списке. Для этого служит два метода: indexOf() и lastIndexOf().
Специальный итератор ListIterator - содержит усовершенствованный итератор ListIterator для обработки последовательных свойств списка.
ListIterator позволяет вставлять и заменять элементы и производить перебор элементов в двух направлениях. Ниже приведено объявление интерфейса ListIterator:
Public interface ListIterator
Описание Iterator:
Public interface Iterator
Как видно из вышеприведенного кода, в ListIterator появились методы для управления итератором в обратном порядке: hasPrevious(), previous(), previousIndex().
Диапазон элементов (sublist) - позволяет манипулировать произвольным диапазоном в списке. Это выполняется с помощью метода subList(). Например так:
List
Метод subList() принимает два значения: стартовый индекс и конечный индекс подсписка. Обратите внимание, что диапазон элементов (список) не создается дублированием элементов из родительского списка. Этот список является частью родительского списка из-за чего все манипуляции над ним отражаются на родительском списке. Вышеприведенный пример это хорошо демонстрирует.
Также обратите внимание, что элемент с конечным индексом не включается в список.
На Рис.1 приведена иерархия классов List.
Интерфейсу List также принадлежит два устаревших класса: Vector и Stack, о которых упоминалось в предыдущей статье.
В отличие от Set, List может содержать повторяющиеся элементы. Также может содержать null-элементы.
Некоторые реализации списков имеют ограничения на элементы, которые они могут содержать. Например, в некоторых реализациях запрещено использовать null в качестве элемента для вставки (на ArrayList и LinkedList это правило не распространяется).
Два объекта типа List одинаковы (т.е., метод equals() возвращает true) только в том случае, когда они содержат одинаковые элементы в одном и том же порядке.
ArrayList - наиболее широко используемая реализация List. ArrayList обладает наибольшей производительностью в плане доступа к случайному элементу в массиве.
В предыдущей лекции была затронута одна из реализаций массива переменной длины —
реализация с помощью списка LinkedList
Для использования ArrayList
Import Java.util.ArrayList;
ArrayList
Пример.
ArrayListЭтой строкой мы создали объект класса ArrayList
После применения "list.add(5);" получим следующую картинку:
В случае, если мы проделаем добавление элемента десять раз подряд и захотим сделать
это одиннадцатый раз, то у нас возникнет проблема. Проблема состоит в том, что наш массив
в list закончился и нам больше некуда записывать данные. Поэтому нам необходимо расширить
массив. Это происходит автоматически. Для этого создаётся новый массив большей длины,
и в него копируются значения из прежнего массива. Это довольно дорогостоящая операция,
она выполняется примерно O(N) итераций. В классе ArrayList
Заметим также, что выполнение операции "list.remove(index);" не уменьшит реальную длину массива в list.
Таблица времени работы в среднем операций для ArrayList.
Рассмотрим теперь асимптотическое время выполнения операций над ArrayList
Заметим, что для add(value) и add(index, value) время выполнения составляет O(1) и O(size - index) соответственно, хотя в худшем случае эти операции работают O(size). Покажем, почему же среднее время работы для операции add(value) получается O(1).
Оценка времени работы операции add(value).
Давайте, для начала, рассмотрим вариант, в котором увеличение массива происходит всего на один элемент. В таком случае при добавлении нового элемента нам каждый раз пришлось бы создавать новый массив и копировать в него все элементы старого. Таким образом время работы add(value) всегда (в том числе и в среднем) равнялось бы O(N). Даже в случае расширения \ нашего массива каждый раз на k элементов время работы в среднем всё равно составило бы O(N). Действительно. Каждый k-ый раз операция выполняется за O(N), а в остальных случаях за O(1). Если взять среднее арифметическое, то получим C * N, то есть O(N).
Рассмотрим теперь реальный случай, в котором удлиннение массива каждый раз происходит в
полтора раза. Пускай мы заполняем объект типа LinkedList
size + (2/3) * size + (2/3) 2 * size + (2/3) 3 * size + ... = size / (1 - 2/3) = 3 * size
То есть мы получили, что выполнение операции add(value) size раз происходит C * size времени, а это и означает, что время выполнения add(value) равно O(1).
Дополнительные методы в ArrayList.
В дополнение к уже изученным методам для ArrayList
Также длину массива можно задавать при конструировании объекта класса
ArrayList
ArrayList
Заключение.
Обзор класса ArrayList
В ArrayList
В силу того, что Java — объектно-ориентированный язык программирования,
значительных перевесов в борьбе за экономию памяти ни тот ни другой класс не получают.
Хотя формально в этом плане выигрывает ArrayList
LinkedList
Основной же недостаток ArrayList