Добавление элемента в позицию 2 1 страница
[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>.
Методы element() и remove() отличаются от методов peek() и poll() тем, что генерируют исключение, если очередь пуста.
/* пример # 5 : добавление и удаление элементов : DemoLinkedList.java */
packagechapt10;
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 */
packagechapt10;
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()));
}
}
packagechapt10;
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.
Для создания возможности сортировки по другому полю id класса Student следует создать новый класс, реализующий Comparator по новым правилам.
/* пример # 7 : другое правило сортировки: StudentId.java */
packagechapt10;
public classStudentIdimplementsComparator<Student> {
public intcompare(Student one, Student two) {
returntwo.getIdStudent() - one.getIdStudent();
}
}
При необходимости сортировки по полю id в качестве второго параметра следует объект класса StudentId:
Collections.sort(p, StudentId.class.newInstance());
Параметризация коллекций позволяет разрабатывать безопасные алгоритмы, создание которых потребовало бы несколько больших затрат в предыдущих версиях языка.
Deque
Интерфейс Deque определяет «двунаправленную» очередь и, соответственно, методы доступа к первому и последнему элементам двусторонней очереди. Методы обеспечивают удаление, вставку и обработку элементов. Каждый из этих методов существует в двух формах. Одни методы создают исключительную ситуацию в случае неудачного завершения, другие возвращают какое-либо из значений (null или false в зависимости от типа операции). Вторая форма добавления элементов в очередь сделана специально для реализаций Deque, имеющих ограничение по размеру. В большинстве реализаций операции добавления заканчиваются успешно.
В следующим примере реализована работа с интерфейсом Deque. Методы addFirst(), addLast() вставляют элементы в начало и в конец очереди соответственно. Метод add() унаследован от интерфейса Queue и абсолютно аналогичен методу addLast() интерфейса Deque.
/* пример # 8 : демонстрация Deque : DequeRunner.java */
package 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 существенно облегчает поиск элементов.
Рис. 10.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 */
packagechapt10;
import java.util.*;
import java.io.*;
public class DemoHashSet {
public static void main(String[] args) {
HashSet<String> words = new HashSet<String>(100);
// использовать коллекции LinkedHashSet или TreeSet
long callTime = System.nanoTime();
try {
BufferedReader in =
new BufferedReader(
new FileReader("c://pushkin.txt"));
String line = "";
while ((line = in.readLine()) != null) {
StringTokenizer tokenizer =
new StringTokenizer(line ,
" (){}[]<>#*!?.,:;-\'\"/");
while (tokenizer.hasMoreTokens()) {
String word = tokenizer.nextToken();
words.add(word.toLowerCase());
}
}
} catch (IOException e) {
System.err.println(e);
}
Iterator<String> it = words.iterator();
while (it.hasNext())
System.out.println(it.next());
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 */
packagechapt10;
import java.util.*;
public class DemoTreeSet {
public static void main(String[] args) {
ArrayList<String> c = new ArrayList<String>();
boolean b;
for (int i = 0; i < 6; i++)
c.add((int) (Math.random() * 71) + "Y ");
System.out.println(c + "список");
TreeSet<String> set = new TreeSet<String>(c);
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 */
packagechapt10;
import java.util.*;
public class Message implements Comparable<Message> {
private StringBuilder str;
private int idSender;
public Message(StringBuilder s, int id) {
super();
this.str = s;
idSender = id;
}
public String getStr() {
return str.toString();
}
public int getId() {
return idSender;
}
public int compareTo(Message a0) {
return (idSender - a0.getId());
}
}
Предлагаемое решение универсально для любых пользовательских типов.
Абстрактный класс 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 chapt10;
import java.util.EnumSet;
enum Faculty{ FFSM, MMF, FPMI, FMO, GEO }
public class UseEnumSet {
public static void main(String[] args) {
/*множество set1 содержит элементы типа enum из интервала,
определенного двумя элементами*/
EnumSet <Faculty> set1 =
EnumSet.range(Faculty.MMF, Faculty.FMO);
/*множество set2 будет содержать все элементы, не содержащиеся
в множестве set1*/
EnumSet <Faculty> set2 =
EnumSet.complementOf(set1);
System.out.println(set1);
System.out.println(set2);
}
}
В результате будет выведено:
[MMF, FPMI, FMO]
[FFSM, GEO]
В следующем примере показано использование интерфейса NavigableSet. Метод first() возвращает первый элемент из множества. Метод subSet(E fromElement, E toElement) возвращает список элементов, находящихся между fromElement и toElement, причем последний не включается. Методы headSet(E element) и tailSet(E element, boolean inclusive) возвращают то множество элементов, которое меньше либо больше element соответственно. Если inclusive равно true, то элемент включается в найденное множество и не включается в противном случае.
/* пример # 13 : иcпользование множества NavigableSet: NavigableSetTest.java */
package chapt10;
import java.util.*;
public class NavigableSetTest {
public static void main(String[] args) {
HashSet<String> city = new HashSet<String>();
city.add("Minsk");
city.add("Mosсow");
city.add("Polotsk");
city.add("Brest");
NavigableSet<String> ns = new TreeSet<String>(city);
System.out.println("All: " + ns);
System.out.println("First: " + ns.first());
System.out.println("Between Minsk and Polotsk: "
+ ns.subSet("Minsk","Polotsk"));
System.out.println("Before Minsk: "
+ ns.headSet("Minsk"));
System.out.println("After Minsk: "
+ ns.tailSet("Minsk",false));
}
}
В результате на консоль будет выведено:
All: [Brest, Minsk, Mosсow, Polotsk]
First: Brest
Between Minsk and Polotsk: [Minsk, Mosсow]
Before Minsk: [Brest]
After Minsk: [Mosсow, Polotsk]
Карты отображений
Карта отображений – это объект, который хранит пару “ключ-значение”. Поиск объекта (значения) облегчается по сравнению с множествами за счет того, что его можно найти по его уникальному ключу. Уникальность объектов-ключей должна обеспечиваться переопределением методов hashCode() и equals() пользовательским классом. Если элемент с указанным ключом отсутствует в карте, то возвращается значение null.
Классы карт отображений:
AbstractMap<K,V> – реализует интерфейс Map<K,V>;
HashMap<K,V> – расширяет AbstractMap<K,V>, используя хэш-таблицу, в которой ключи отсортированы относительно значений их хэш-кодов;
TreeMap<K,V> – расширяет AbstractMap<K,V>, используя дерево, где ключи расположены в виде дерева поиска в строгом порядке.
WeakHashMap<K,V> позволяет механизму сборки мусора удалять из карты значения по ключу, ссылка на который вышла из области видимости приложения.
LinkedHashMap<K,V> запоминает порядок добавления объектов в карту и образует при этом дважды связанный список ключей. Этот механизм эффективен, только если превышен коэффициент загруженности карты при работе с кэш-памятью и др.
Рис. 10.3. Иерархия наследования карт
Для класса IdentityHashMap<K,V> хэш-коды объектов-ключей вычисляются методом System.identityHashCode() по адресу объекта в памяти, в отличие от обычного значения hashCode(), вычисляемого сугубо по содержимому самого объекта.
Интерфейсы карт:
Map<K,V> – отображает уникальные ключи и значения;
Map.Entry<K,V> – описывает пару “ключ-значение”;
SortedMap<K,V> – содержит отсортированные ключи и значения;
NavigableMap<K,V> – добавляет новые возможности поиска по ключу.
Интерфейс Map<K,V> содержит следующие методы:
void clear()– удаляет все пары из вызываемой карты;
boolean containsKey(Object key) – возвращает true, если вызывающая карта содержит key как ключ;
boolean containsValue(Object value) – возвращает true, если вызывающая карта содержит value как значение;
Set<Map.Entry<K,V>> entrySet() – возвращает множество, содержащее значения карты;
Set<K> keySet() – возвращает множество ключей;
V get(Object obj) – возвращает значение, связанное с ключом obj;
V put(K key, V value) – помещает ключ key и значение value в вызывающую карту. При добавлении в карту элемента с существующим ключом произойдет замена текущего элемента новым. При этом метод возвратит заменяемый элемент;
void putAll(Map <? extends K, ? extends V> t) – помещает коллекцию t в вызывающую карту;
V remove(Object key) – удаляет пару “ключ-значение” по ключу key;
Collection<V> values() – возвращает коллекцию, содержащую значения карты.
Интерфейс Map.Entry<K,V> содержит следующие методы:
K getKey() – возвращает ключ текущего входа;
V getValue() – возвращает значение текущего входа;
V setValue(V obj) – устанавливает значение объекта obj в текущем входе.
В примере показаны способы создания хэш-карты и доступа к ее
элементам.
/* пример # 14 : создание хэш-карты и замена элемента по ключу:
DemoHashMap.java */
packagechapt10;
import java.util.*;
public class DemoHashMap {
public static void main(String[] args){
HashMap<Integer, String> hm =
new HashMap<Integer, String>(5);
for (int i = 11; i < 15; i++)
hm.put(i, i + "EL");
System.out.println(hm);
hm.put(12, "14EL");
System.out.println(hm + "с заменой элемента");
String a = hm.get(12);
System.out.println(a + " - найден по ключу '12'");
/* вывод хэш-таблицы с помощью методов интерфейса
Map.Entry<K,V> */
Set<Map.Entry<Integer, String>> setvalue =
hm.entrySet();
System.out.println(setvalue);
Iterator<Map.Entry<Integer, String>> i =
setvalue.iterator();
while (i.hasNext()) {
Map.Entry<Integer, String> me = i.next();
System.out.print(me.getKey()+" : ");
System.out.println(me.getValue());
}
}
}
{13=13EL, 14=14EL, 12=12EL, 11=11EL}
{13=13EL, 14=14EL, 12=14EL, 11=11EL}с заменой элемента
14EL - найден по ключу '12'
[13=13EL, 14=14EL, 12=14EL, 11=11EL]
EL
EL
EL