Добавление элемента в позицию 2
ArrayList()
ArrayList(Collection <? extends E> c)
ArrayList(int capacity)
Практически все методы класса являются реализацией абстрактных методов из суперклассов и интерфейсов. Методы интерфейса List<E> позволяют вставлять и удалять элементы из позиций, указываемых через отсчитываемый от нуля индекс:
void add(int index, E element) – вставляет elementв позицию, указанную в index;
void addAll(int index, Collection<? extends E> c) – вставляет в вызывающий список все элементы коллекции с,начиная с позиции index;
E get(int index) – возвращает элемент в виде объекта из позиции
index;
int indexOf(Object ob) – возвращает индекс указанного объекта;
E remove(int index) – удаляет объект из позиции index;
E set(int index, E element) – заменяет объект в позиции index, возвращает при этом удаляемый элемент;
List<E> subList(int fromIndex, int toIndex) – извлекает часть коллекции в указанных границах.
Удаление и добавление элементов для такой коллекции представляет собой ресурсоемкую задачу, поэтому объект ArrayList<E> лучше всего подходит для хранения неизменяемых списков.
/* # 1 : создание параметризованной коллекции : DemoGeneric.java */
package by.bsu.chapt10;
import java.util.*;
public class DemoGeneric {
public static void main(String args[]) {
ArrayList<String> list = new ArrayList<String>();
// ArrayList<int> b = new ArrayList<int>(); // ошибка компиляции
list.add("Java");/* компилятор “знает”
допустимый тип передаваемого значения */
list.add("Fortress");
String res = list.get(0);/* компилятор “знает”
допустимый тип возвращаемого значения */
// list.add(new StringBuilder("C#")); // ошибка компиляции
// компилятор не позволит добавить “посторонний” тип
System.out.print(list);
}
}
В результате будет выведено:
[Java, Fortress]
В данной ситуации не создается новый класс для каждого конкретного типа и сама коллекция не меняется, просто компилятор снабжается информацией о типе элементов, которые могут храниться в list. При этом параметром коллекции может быть только объектный тип.
Следует отметить, что указывать тип следует при создании ссылки, иначе будет позволено добавлять объекты всех типов.
/* # 2 : некорректная коллекция (raw) : UncheckCheck.java */
package by.bsu.chapt10;
import java.util.*;
public class UncheckCheck {
public static void main(String args[]) {
ArrayList list = new ArrayList();// «сырой» тип
list.add(71);
list.add(new Boolean("TruE"));
list.add("Java 1.6.0");
// требуется приведение типов
int i = (Integer)list.get(0);
boolean b = (Boolean)list.get(1);
String str = (String)list.get(2);
for (Object ob : list) {
System.out.println("list " + ob);
}
ArrayList<Integer> s = new ArrayList<Integer>();
s.add(71);
s.add(92);
// s.add("101");// ошибка компиляции: s параметризован
for (Integer ob : s) {
System.out.println("int " + ob);
}
}
}
В результате будет выведено:
List 71
List true
List Java 1.6.0
Int 71
Int 92
Чтобы параметризация коллекции была полной, необходимо указывать параметр и при объявлении ссылки, и при создании объекта.
Объект типа Iterator может использоваться для последовательного перебора элементов коллекции. Ниже приведен пример заполнения списка псевдослучайными числами, подсчет с помощью итератора количества положительных и удаление из списка неположительных значений.
/* # 3 : работа со списком : DemoIterator.java */
package by.bsu.chapt10;
import java.util.*;
public class DemoIterator {
public static void main(String[] args) {
ArrayList<Double> c =
new ArrayList<Double>(7);
System.out.println("Коллекция пуста: "
+ a.isEmpty());
for(int i = 0 ;i < 10; i++) {
double z = new Random().nextGaussian();
c.add(z);//заполнение списка
}
//вывод списка на консоль
for(Double d: c) {
System.out.printf("%.2f ",d);
}
int positiveNum = 0;
int size = c.size();//определение размера коллекции
//извлечение итератора
Iterator<Double> it = c.iterator();
//проверка существования следующего элемента
while(it.hasNext()) {
//извлечение текущего элемента и переход к следующему
if (it.next() > 0) {
positiveNum++;
}else {
it.remove();//удаление неположительного элемента
}
}
System.out.printf("%nКоличество положительных: %d ",
positiveNum);
System.out.printf("%nКоличество неположительных: %d ",
size - positiveNum);
System.out.println("\nПоложительная коллекция");
for(Double d : c) {
System.out.printf("%.2f ",d);
}
}
}
В результате на консоль будет выведено:
Коллекция пуста: true
0,69 0,33 0,51 -1,24 0,07 0,46 0,56 1,26 -0,84 -0,53
Количество положительных: 7
Количество отрицательных: 3
Положительная коллекция
0,69 0,33 0,51 0,07 0,46 0,56 1,26
Для доступа к элементам списка может также использоваться интерфейс
ListIterator<E>, который позволяет получить доступ сразу в необходимую программисту позицию списка. Такой способ доступа возможен только для списков.
/* # 4 : замена, удаление и поиск элементов : DemoListMethods.java */
package by.bsu.chapt10;
import java.util.*;
public class DemoListMethods {
public static void main(String[] args) {
ArrayList<Character> a =
new ArrayList<Character>(5);
for (char c = 'a'; c < 'h'; ++c) {
a.add(c);
}
char ch = 'a';
a.add(6, ch); // заменить 6 на >=8 – ошибка выполнения
System.out.println(a);
ListIterator<Character> it;// параметризация обязательна
it= a.listIterator(2);// извлечение итератора списка в позицию
System.out.println("добавление элемента в позицию "
+ it.nextIndex());
it.add('X');// добавление элемента без замены в позицию итератора
System.out.println(a);
// сравнить методы
int index = a.lastIndexOf(ch); // a.indexOf(ch);
a.set(index, 'W'); // замена элемента без итератора
System.out.println(a + "после замены элемента");
if (a.contains(ch)) {
a.remove(a.indexOf(ch));
}
System.out.println(a + "удален элемент " + ch);
}
}
В результате будет выведено:
[a, b, c, d, e, f, a, g]
добавление элемента в позицию 2
[a, b, X, c, d, e, f, a, g]
[a, b, X, c, d, e, f, W, g]после замены элемента
[b, X, c, d, e, f, W, g]удален элемент a
Коллекция LinkedList<E> реализует связанный список. В отличие от массива, который хранит объекты в последовательных ячейках памяти, связанный список хранит объекты отдельно, но вместе со ссылками на следующее и предыдущее звенья последовательности.
В добавление ко всем имеющимся методам в LinkedList<E> реализованы методы void addFirst(E ob), void addLast(E ob), E getFirst(),
E getLast(), E removeFirst(), E removeLast()добавляющие, извлекающие, удаляющие и извлекающие первый и последний элементы списка соответственно.
Класс LinkedList<E>реализует интерфейс Queue<E>, что позволяет предположить, что такому списку легко придать свойства очереди. К тому же специализированные методы интерфейса Queue<E> по манипуляции первым и последним элементами такого списка E element(), boolean offer(E o), E peek(), E poll(),E remove() работают немного быстрее, чем соответствующие методы класса LinkedList<E>.
Методы интерфейса Queue<E>:boolean offer(E o) – вставляет элемент в очередь, если возможно;E element() – возвращает, но не удаляет головной элемент очереди;E peek() – возвращает, но не удаляет головной элемент очереди, возвращает null, если очередь пуста;E poll() – возвращает и удаляет головной элемент очереди, возвращает null, если очередь пуста;E remove() – возвращает и удаляет головной элемент очереди.Методы element() и remove() отличаются от методов peek() и poll() тем, что генерируют исключение, если очередь пуста.
/* # 5 : добавление и удаление элементов : DemoLinkedList.java */
package by.bsu.chapt10;
import java.util.*;
public class DemoLinkedList {
public static void main(String[] args){
LinkedList<Number> a = new LinkedList<Number>();
for(int i = 10; i <= 15; i++) {
a.add(i);
}
for(int i = 16; i <= 20; i++) {
a.add(new Float(i));
}
ListIterator<Number> list = a.listIterator(10);
System.out.println("\n"+ list.nextIndex()
+ "-й индекс");
list.next(); // важно!
System.out.println(list.nextIndex()
+ "-й индекс");
list.remove(); // удаление элемента с текущим индексом
while(list.hasPrevious()) {
System.out.print(list.previous()+" "); /*вывод
в обратном порядке*/
}
// демонстрация работы методов
a.removeFirst();
a.offer(71); // добавление элемента в конец списка
a.poll(); // удаление нулевого элемента из списка
a.remove(); // удаление нулевого элемента из списка
a.remove(1); // удаление первого элемента из списка
System.out.println("\n" + a);
Queue<Number> q = a; // список в очередь
for (Number i : q) {// вывод элементов
System.out.print(i + " ");
}
System.out.println(" :size= " + q.size());
// удаление пяти элементов
for (int i = 0; i < 5; i++) {
Number res = q.poll();
}
System.out.print("size= " + q.size());
}
}
В результате будет выведено:
Й индекс
Й индекс
19.0 18.0 17.0 16.0 15 14 13 12 11 10
[13, 15, 16.0, 17.0, 18.0, 19.0, 71]
13 15 16.0 17.0 18.0 19.0 71 :size= 7
size= 2
При реализации интерфейса Comparator<T> существует возможность сортировки списка объектов конкретного типа по правилам, определенным для этого типа. Для этого необходимо реализовать метод int compare(T ob1,
T ob2), принимающий в качестве параметров два объекта для которых должно быть определено возвращаемое целое значение, знак которого и определяет правило сортировки. Этот метод автоматически вызывается методом public static <T> void sort(List<T> list, Comparator<? super T> c)класса Collections, в качестве первого параметра принимающий коллекцию, в качестве второго – объект-comparator, из которого извлекается правило сортировки.
/* # 6 : авторская сортировка списка: UniqSortMark.java */
package by.bsu.chapt10;
importjava.util.Comparator;
public classStudent implementsComparator<Student> {
private intidStudent;
private floatmeanMark;
publicStudent(floatm, int id) {
meanMark = m;
idStudent = id;
}
publicStudent() {
}
public floatgetMark() {
returnmeanMark;
}
public intgetIdStudent() {
returnidStudent;
}
// правило сортировки
public intcompare(Student one, Student two) {
Return
(int)(Math.ceil(two.getMark() - one.getMark()));
}
public boolean equals(Object ob){/*реализация*/}
}
package by.bsu.chapt10;
importjava.util.*;
public classUniqSortMark {
public static voidmain(String[] args) {
ArrayList<Student> p =newArrayList<Student>();
p.add(new Student(3.9f, 52201));
p.add(new Student(3.65f, 52214));
p.add(new Student(3.71f, 52251));
p.add(new Student(3.02f, 52277));
p.add(new Student(3.81f, 52292));
p.add(new Student(9.55f, 52271));
// сортировка списка объектов
try {
Collections.sort(p, Student.class.newInstance());
} catch (InstantiationException e1) {
//невозможно создать объект класса
e1.printStackTrace();
} catch (IllegalAccessException e2) {
e2.printStackTrace();
}
for(Student ob : p) {
System.out.printf("%.2f ", ob.getMark());
}
}
}
В результате будет выведено:
9,55 3,90 3,81 3,71 3,65 3,02
Метод boolean equals(Object obj) интерфейса Comparator<T>, который обязан выполнять свой контракт, возвращает trueтолько в случае если соответствующий метод compare()возвращает 0.
Для создания возможности сортировки по любому полю класса Student следует модернизировать класс Student, добавив ему в качестве поля ссылку на перечисление StudentEnum:
public enum StudentEnum {
IDSTUDENT, MEANMARK
}
А именно:
public class Student{//отсутствует реализация интерфейса Comparator
private intidStudent;
private floatmeanMark;
/*значение по умолчанию для sortEnum задано во избежание бессмысленных
ошибок. Оно может быть изменено с помощью метода setSortEnum() */
public static StudentEnum sortEnum =
StudentEnum.MEANMARK;
//...
}
И отдельный класс, реализующий интерфейс Comparator.
/* # 7 : другое правило сортировки: StudentId.java */
packageby.bsu.chapt10;
import java.util.Comparator;
public class StudentComparator
implements Comparator<Student> {
public int compare(Student one, Student two) {
switch (Student.sortEnum) {
case IDSTUDENT:
Return
(one.getIdStudent() - two.getIdStudent());
case MEANMARK:
Return
(int)(Math.ceil(two.getMark() - one.getMark()));
default: throw
new EnumConstantNotPresentException(
StudentEnum.class, Student.sortEnum.name());
}
}
public boolean equals(Object ob){/*реализация*/}
}
При необходимости сортировки по полю id следует изменить значение статической переменной sortEnumи в качестве второго параметра методу sort() передать объект класса StudentComparator:
Collections.sort(p, new StudentComparator());
Интерфейс Comparatorрекомендует также реализовать метод equals() для обеспечения корректности, то есть если метод compare() возвращает 0, то метод equals() должен возвращать true. Кроме того, наличие метода equals() обеспечивает корректную работу метода семантического поиска и проверки на идентичность contains(Object o), определённого в интерфейсе java.util.Collection, а следовательно, реализованного в любой коллекции.
Deque
Интерфейс Deque определяет «двунаправленную» очередь и, соответственно, методы доступа к первому и последнему элементам двусторонней очереди. Методы обеспечивают удаление, вставку и обработку элементов. Каждый из этих методов существует в двух формах. Одни методы создают исключительную ситуацию в случае неудачного завершения, другие возвращают какое-либо из значений (null или false в зависимости от типа операции). Вторая форма добавления элементов в очередь сделана специально для реализаций Deque, имеющих ограничение по размеру. В большинстве реализаций операции добавления заканчиваются успешно.
В следующим примере реализована работа с интерфейсом Deque. Методы addFirst(), addLast() вставляют элементы в начало и в конец очереди соответственно. Метод add() унаследован от интерфейса Queue и абсолютно аналогичен методу addLast() интерфейса Deque.
/* # 8 : демонстрация Deque : DequeRunner.java */
package by.bsu.chapt10;
import java.util.*;
public class DequeRunner {
public static void printDeque(Deque<?> d){
for (Object de : d) {
System.out.println(de + "; ");
}
}
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<String>();
deque.add(new String("5"));
deque.addFirst("A");
//deque.addLast(new Integer(5));//ошибка компиляции
System.out.println(deque.peek());
System.out.println("Before:");
printDeque(deque);
deque.pollFirst();
System.out.println(deque.remove(5));
System.out.println("After:");
printDeque(deque);
}
}
В результате на консоль будет выведено:
A
Before:
A;
5;
False
After:
5;
Множества
Интерфейс Set<E>объявляет поведение коллекции, не допускающей дублирования элементов. Интерфейс SortedSet<E> наследует Set<E> и объявляет поведение набора, отсортированного в возрастающем порядке, заранее определенном для класса. Интерфейс NavigableSet существенно облегчает поиск элементов.
Рис. 2. Иерархия наследования множеств
Класс HashSet<E> наследуется от абстрактного суперкласса
AbstractSet<E> и реализует интерфейс Set<E>, используя хэш-таблицу для хранения коллекции. Ключ (хэш-код) используется вместо индекса для доступа к данным, что значительно ускоряет поиск определенного элемента. Скорость поиска существенна для коллекций с большим количеством элементов. Все элементы такого множества упорядочены посредством хэш-таблицы, в которой хранятся хэш-коды элементов.
Конструкторы класса:
HashSet()
HashSet(Collection <? extends E> c)
HashSet(int capacity)
HashSet(int capacity, float loadFactor),где capacity–число ячеек для хранения хэш-кодов.
/* # 9 : использование множества для вывода всех уникальных слов из файла : DemoHashSet.java */
package by.bsu.chapt10;
import java.io.*;
import java.util.*;
public class DemoHashSet {
public static void main(String[] args) {
HashSet<String> words =
new HashSet<String>(100);
long callTime = System.nanoTime();
Scanner scan;
try {
scan = new Scanner(
new File("c://pushkin.txt"));
scan.useDelimiter("[^А-Яа-я]+");
while (scan.hasNext()) {
String word = scan.next();
words.add(word.toLowerCase());
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
Iterator<String> it = words.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
TreeSet<String> ts =
new TreeSet<String>(words);
System.out.println(ts);
long totalTime = System.nanoTime() - callTime;
System.out.println("различных слов: "
+ words.size() + ", "
+ totalTime + " наносекунд");
}
}
Класс TreeSet<E> для хранения объектов использует бинарное дерево. При добавлении объекта в дерево он сразу же размещается в необходимую позицию с учетом сортировки. Сортировка происходит благодаря тому, что все добавляемые элементы реализуют интерфейсы Comparator и Comparable. Обработка операций удаления и вставки объектов происходит медленнее, чем в хэш-множествах, но быстрее, чем в списках.
Конструкторы класса:
TreeSet()
TreeSet(Collection <? extends E> c)
TreeSet(Comparator <? super E> c)
TreeSet(SortedSet <E> s)
Класс TreeSet<E> содержит методы по извлечению первого и последнего (наименьшего и наибольшего) элементов E first() и E last(). Методы SortedSet<E> subSet(E from, E to),
SortedSet<E> tailSet(E from)
иSortedSet<E> headSet(E to)
предназначены для извлечения определенной части множества. Метод
Comparator <? super E> comparator() возвращает объект
Comparator, используемый для сортировки объектов множества или null, если выполняется обычная сортировка.
/* # 10: создание множества из списка и его методы: DemoTreeSet.java */
packageby.bsu.chapt10;
import java.util.*;
public class DemoTreeSet {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
boolean b;
for (int i = 0; i < 6; i++) {
list.add((int) (Math.random() * 71) + "Y ");
}
System.out.println(list + "список");
TreeSet<String> set = new TreeSet<String>(list);
System.out.println(set + "множество");
b = set.add("5 Element"); // добавление(b=true)
b = set.add("5 Element"); // добавление(b=false)
// после добавления
System.out.println(set + "add");
System.out.println(set.comparator()); //null !!!
// извлечение наибольшего и наименьшего элементов
System.out.println(set.last() + " "
+ set.first());
}
}
В результате может быть выведено:
[44Y , 56Y , 49Y , 26Y , 49Y , 2Y ]список
[2Y , 26Y , 44Y , 49Y , 56Y ]множество
[2Y , 26Y , 44Y , 49Y , 5 Element, 56Y ]add
Null
Y 2Y
Множество инициализируется списком и сортируется сразу же в процессе создания. После добавления нового элемента производится неудачная попытка добавить его повторно. С помощью итератора элемент может быть найден и удален из множества. Для множества, состоящего из обычных строк, используется по умолчанию правило обычной лексикографической сортировки, поэтому метод comparator() возвращает null.
Если попытаться заменить тип String на StringBuilderили
StringBuffer, то создать множество TreeSet так просто не удастся. Решением такой задачи будет создание нового класса с полем типа StringBuilder и реализацией интерфейса Comparable<T> вида:
/* # 11 :пользовательский класс, объект которого может быть добавлен в множество TreeSet : Message.java */
packageby.bsu.chapt10;
import java.util.*;
public class Message implements Comparable<Message> {
private StringBuilder str;
private int idSender;
public Message(StringBuilder s, int id) {
this.str = s;
idSender = id;
}
public String getStr() {
return str.toString();
}
public int getIdSender() {
return idSender;
}
public int compareTo(Message a0) {
return (idSender - a0.getIdSender());
}
public boolean equals(Object ob){/*реализация*/}
}
Предлагаемое решение универсально для любых пользовательских типов.
Абстрактный класс EnumSet<E extends Enum<E>> наследуется от абстрактного класса AbstractSet. Специально реализован для работы с типами enum. Все элементы такой коллекции должны принадлежать единственному типу enum, определенному явно или неявно. Внутренне множество представимо в виде вектора битов, обычно единственного long. Множества нумераторов поддерживают перебор по диапазону из нумераторов. Скорость выполнения операций над таким множеством очень высока, даже если в ней участвует большое количество элементов.
Создать объект этого класса можно только с помощью статических методов. Метод EnumSet<E> noneOf(Class<E> elemType)cоздает пустое множество нумерованных констант с указанным типом элемента, метод
allOf(Class<E> elementType)создает множество нумерованных констант, содержащее все элементы указанного типа. Метод of(E first, E... rest)создает множество, первоначально содержащее указанные элементы.
С помощью метода complementOf(EnumSet<E> s)создается множество, содержащее все элементы, которые отсутствуют в указанном множестве. Метод range(E from, E to)создает множество из элементов, содержащихся в диапазоне, определенном двумя элементами. При передаче вышеуказанным методам в качестве параметра null будет сгенерирована исключительная ситуация NullPointerException.
/* # 12 : иcпользование множества enum-типов : UseEnumSet.java */
package by.bsu.chapt10;
import java.util.EnumSet;
enum Faculty{ FFSM, MMF, FPMI, RFE, GEO }
public class UseEnumSet {
public static void main(String[] args) {
/*множество set1 содержит элементы типа enum из интервала,
определенного двумя элементами*/
EnumSet <Faculty> set1 =
EnumSet.range(Faculty.MMF, Faculty.RFE);
/*множество set2 будет содержать все элементы, не содержащиеся
в множестве set1*/
EnumSet <Faculty> set2 =
EnumSet.complementOf(set1);
System.out.println(set1);
System.out.println(set2);
}
}
В результате будет выведено:
[MMF, FPMI, RFE]
[FFSM, GEO]
Интерфейс NavigableSet
Интерфейс NavigableSet<E>, появившийся в Java SE 6, расширяет интерфейс SortedSet и добавляют возможность перемещения по отсортированной коллекции. Класс TreeSet<E> был модернизирован для поддержки этого интерфейса.
Методы интерфейса NavigableSet<E>:
Следующие методы возвращают итераторы коллекции в порядке возрастания и убывания элементов соответственно.
Iterator iterator() –возвращает итератор в порядке возрастания значений элементов коллекции;
Iterator descendingIterator() –возвращает итератор в порядке убывания значений элементов коллекции;
NavigableSet descendingSet() –возвращает множество в порядке убывания значений элементов коллекции;
E lower(E e) –возвращает меньший по значению элемент для вызывающего элемента;
E floor(E e) –возвращает меньший или равный по значению элемент для вызывающего элемента;
E higher(E e) –возвращает больший по значению элемент для вызывающего элемента;
E ceiling(E e) –возвращает больший или равный по значению элемент для вызывающего элемента;
E pollFirst() –возвращает и удаляет первый элемент коллекции;
E pollLast() –возвращает и удаляет последний элемент коллекции;
SortedSet<E> subSet(E fromElement, E toElement) –возвращает список элементов, находящихся между fromElement и toElement, причем последний не включается;
NavigableSet subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)– ;
И, наконец, методы, позволяющие получить подмножество элементов. Параметры fromElement и toElement ограничивают подмножество снизу и сверху, а флаги fromInclusive и toInclusive показывают, нужно ли в результирующий набор включать граничные элементы. headSet возвращает элементы с начала набора до указанного элемента, а tailSet - от указанного элемента до конца набора. Перегруженные методы без логических параметров включают в выходной набор первый элемент интервала, но исключают последний.