Spec-Zone .ru
спецификации, руководства, описания, API
|
|
Spec-Zone .ru
спецификации, руководства, описания, API
|
A List упорядоченный (иногда называемый последовательностью). Списки могут содержать двойные элементы. В дополнение к операциям, наследованным от Collection, List интерфейс включает операции для следующего:
Positional access — управляет элементами, основанными на их числовой позиции в спискеSearch — поиски указанного объекта в списке и возвратах его числовая позицияIteration — расширяется Iterator семантика, чтобы использовать в своих интересах последовательный характер спискаRange-view — выполняет произвольные операции диапазона в списке. List интерфейс следует.
public interface List<E> extends Collection<E> {
// Positional access
E get(int index);
// optional
E set(int index, E element);
// optional
boolean add(E element);
// optional
void add(int index, E element);
// optional
E remove(int index);
// optional
boolean addAll(int index, Collection<? extends E> c);
// Search
int indexOf(Object o);
int lastIndexOf(Object o);
// Iteration
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
// Range-view
List<E> subList(int from, int to);
}
Платформа Java содержит два общего назначения List реализации. , который обычно является лучше выполняющей реализацией, и который предлагает лучшую производительность при определенных обстоятельствах. Кроме того, Vector был retrofitted, чтобы реализовать List.
Если Вы использовали , Вы уже знакомы с общими основами List. (Конечно, List интерфейс, в то время как Vector конкретная реализация.) List исправления несколько незначительных недостатков API в Vector. Обычно используемый Vector операции, такой как elementAt и setElementAt, были даны намного более короткие имена. Когда Вы полагаете, что эти две операции List аналог квадратных скобок для массивов, становится очевидно, что более короткие имена являются очень требуемыми. Рассмотрите следующий оператор присваивания.
a[i] = a[j].times(a[k]);
Vector эквивалентный:
v.setElementAt(v.elementAt(j).times(v.elementAt(k)), i);
List эквивалентный:
v.set(i, v.get(j).times(v.get(k)));
Вы, возможно, уже заметили что set метод, который заменяет Vector метод setElementAt, инвертирует порядок параметров так, чтобы они соответствовали соответствующую операцию над массивом. Рассмотрите следующий оператор присваивания.
gift[5] = "golden rings";
Vector эквивалентный:
gift.setElementAt("golden rings", 5);
List эквивалентный:
gift.set(5, "golden rings");
Для пользы непротиворечивости, метода add(int, E), который заменяет insertElementAt(Object, int), также инвертирует порядок параметров.
Три операции диапазона в Vector (indexOf, lastIndexOf, и setSize) были заменены единственной работой представления диапазона (subList), который является намного более мощным и непротиворечивым.
Операции, наследованные от Collection все делают, о каком Вы ожидали бы, что они сделают, предполагая, что Вы уже знакомы с ними. Если Вы не знакомы с ними от Collection, теперь было бы хорошее время, чтобы считать раздел
list1.addAll(list2);
Вот неразрушающая форма этой идиомы, которая производит одну треть List состоя из второго списка, добавленного к первому.
List<Type> list3 = new ArrayList<Type>(list1); list3.addAll(list2);
Отметьте, что идиома, в ее неразрушающей форме, использует в своих интересах ArrayList's стандартный конструктор преобразования.
Как Set интерфейс, List усиливает требования к equals и hashCode методы так, чтобы два List объекты могут быть сравнены для логического равенства без отношения к их классам реализации. Два List объекты равны, если они содержат те же самые элементы в том же самом порядке.
Основное positional access операции (get, set, add и remove) ведите себя точно так же как их дольше названные дубликаты в Vector (elementAt, setElementAt, insertElementAt, и removeElementAt) с одним примечательным исключением: set и remove операции возвращают старое значение, которое перезаписывается или удаляется; Vector дубликаты (setElementAt и removeElementAt) ничего не возвратите (void). search операции indexOf и lastIndexOf ведите себя точно как тождественно именованные операции в Vector.
addAll работа вставляет все элементы указанного Collection запуск в указанной позиции. Элементы вставляются в порядок, они возвращаются указанным Collection's iterator. Этот вызов является позиционным аналогом доступа Collection's addAll работа.
Вот небольшой метод, чтобы подкачать два индексированных значения в a List. Это должно выглядеть знакомым от Программирования 101.
public static <E> void swap(List<E> a, int i, int j) {
E tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
Конечно, есть одна большая разница. Это - полиморфный алгоритм: Это подкачивает два элемента в любом List, независимо от его типа реализации. Вот другой полиморфный алгоритм, который использует предыдущее swap метод.
public static void shuffle(List<?> list, Random rnd) {
for (int i = list.size(); i > 1; i--)
swap(list, i - 1, rnd.nextInt(i));
}
Этот алгоритм, который включается в платформу Java class, в произвольном порядке переставляет указанный список, используя указанный источник случайности. Это немного тонко: Это выполняет список от нижней части, неоднократно подкачивая в произвольном порядке выбранный элемент в текущую позицию. В отличие от большинства наивных попыток перестановки, это справедливо (все перестановки происходят с равной вероятностью, принимая несмещенный источник случайности) и быстро (требующий точно list.size()-1 подкачки). Следующая программа использует этот алгоритм, чтобы напечатать слова в его списке параметров в произвольном порядке.
import java.util.*;
public class Shuffle {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
for (String a : args)
list.add(a);
Collections.shuffle(list, new Random());
System.out.println(list);
}
}
Фактически, эта программа может быть сделана еще короче и быстрее. У class есть статический вызванный метод фабрики asList, который позволяет массиву просматриваться как a List. Этот метод не копирует массив. Изменения в List запишите через в массив и наоборот. Получающийся Список не является общего назначения List реализация, потому что это не реализует (дополнительный) add и remove операции: Массивы не изменяемого размера. Использование в своих интересах Arrays.asList и вызов версии библиотеки shuffle, который использует источник значения по умолчанию случайности, Вы получаете следующий
import java.util.*;
public class Shuffle {
public static void main(String[] args) {
List<String> list = Arrays.asList(args);
Collections.shuffle(list);
System.out.println(list);
}
}
Поскольку Вы ожидали бы, Iterator возвращенный List's iterator работа возвращает элементы списка в надлежащей последовательности. List также обеспечивает более богатый iterator, названный a ListIterator, который позволяет Вам пересекать список в любом направлении, изменять список во время итерации, и получать текущую позицию iterator. ListIterator интерфейс следует.
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove(); //optional
void set(E e); //optional
void add(E e); //optional
}
Три метода это ListIterator наследовался от Iterator (hasNext, next, и remove) сделайте точно ту же самую вещь в обоих интерфейсах. hasPrevious и previous операции являются точными аналогами hasNext и next. Прежние операции обращаются к элементу перед (неявным) курсором, тогда как последние обращаются к элементу после курсора. previous работа перемещает курсор назад, тогда как next перемещает это вперед.
Вот стандартная идиома для того, чтобы выполнить итерации назад через список.
for (ListIterator<Type> it = list.listIterator(list.size()); it.hasPrevious(); ) {
Type t = it.previous();
...
}
Отметьте параметр listIterator в предыдущей идиоме. List у интерфейса есть две формы listIterator метод. Форма без параметров возвращает a ListIterator расположенный в начале списка; форма с int параметр возвращает a ListIterator расположенный в указанное индексируют. Индексирование обращается к элементу, который был бы возвращен начальным вызовом next. Начальный вызов previous возвратил бы элемент, чей индексируют, был index-1. В списке длины n, есть n+1 допустимые значения для index, от 0 к n, включительно.
Интуитивно говоря, курсор всегда между двумя элементами — тот, который был бы возвращен звонком previous и тот, который был бы возвращен звонком next. n+1 допустимый index значения соответствуют n+1 разрывы между элементами, от разрыва перед первым элементом к разрыву после последнего. Следующие данные показывают пять возможных позиций курсора в списке, содержащем четыре элемента.
Пять возможных позиций курсора.
Звонки next и previous может быть смешан, но необходимо быть немного осторожными. Первый звонок previous возвращает тот же самый элемент как последняя возможность к next. Точно так же первый звонок next после последовательности звонков previous возвращает тот же самый элемент как последняя возможность к previous.
Это не должно удивить что nextIndex метод возвращает индексирование элемента, который был бы возвращен последующим звонком next, и previousIndex возвращает индексирование элемента, который был бы возвращен последующим звонком previous. Эти вызовы обычно используются или чтобы сообщить о позиции, где что-то было найдено или записывать позицию ListIterator так, чтобы другой ListIterator с идентичной позицией может быть создан.
Это не должно также удивить что число, возвращенное nextIndex всегда одно большее чем число, возвращенное previousIndex. Это подразумевает поведение двух граничных случаев: (1) звонок previousIndex когда курсор перед начальными возвратами элемента -1 и (2) звонок nextIndex когда курсор после заключительных возвратов элемента list.size(). Чтобы сделать весь этот бетон, следующее является возможной реализацией List.indexOf.
public int indexOf(E e) {
for (ListIterator<E> it = listIterator(); it.hasNext(); )
if (e == null ? it.next() == null : e.equals(it.next()))
return it.previousIndex();
// Element not found
return -1;
}
Отметьте что indexOf возвраты метода it.previousIndex() даже при том, что это пересекает список в прямом направлении. Причина - это it.nextIndex() возвратил бы индексирование элемента, который мы собираемся исследовать, и мы хотим возвратить индексирование элемента, который мы только исследовали.
Iterator интерфейс обеспечивает remove работа, чтобы удалить последний элемент, возвращенный next от Collection. Для ListIterator, эта работа удаляет последний элемент, возвращенный next или previous. ListIterator интерфейс обеспечивает две дополнительных операции, чтобы изменить список — set и add. set метод перезаписывает последний элемент, возвращенный next или previous с указанным элементом. Следующее полиморфное использование алгоритма set заменять все возникновения одного указанного значения с другим.
public static <E> void replace(List<E> list, E val, E newVal) {
for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
if (val == null ? it.next() == null : val.equals(it.next()))
it.set(newVal);
}
Единственный бит ловкости в этом примере является тестом равенства между val и it.next. Вы нуждаетесь к особому случаю a val значение null предотвратить a NullPointerException.
add метод вставляет новый элемент в список сразу перед текущей позицией курсора. Этот метод иллюстрируется в следующем полиморфном алгоритме, чтобы заменить все возникновения указанного значения с последовательностью значений, содержавшихся в указанном списке.
public static <E>
void replace(List<E> list, E val, List<? extends E> newVals) {
for (ListIterator<E> it = list.listIterator(); it.hasNext(); ){
if (val == null ? it.next() == null : val.equals(it.next())) {
it.remove();
for (E e : newVals)
it.add(e);
}
}
}
range-view работа, subList(int fromIndex, int toIndex), возвраты a List представление части этого списка, индексы которого располагаются от fromIndex, включительно, к toIndex, монопольный. Этот полуоткрытый диапазон зеркально отражает типичное for цикл.
for (int i = fromIndex; i < toIndex; i++) {
...
}
Поскольку термин представление подразумевает, возвращенный List поддерживается List на котором subList был вызван, таким образом, изменения в прежнем отражаются в последнем.
Этот метод избавляет от необходимости явные операции диапазона (вида, которые обычно существуют для массивов). Любая работа, которая ожидает a List может использоваться в качестве работы диапазона, передавая a subList представление вместо целого List. Например, следующая идиома удаляет диапазон элементов от a List.
list.subList(fromIndex, toIndex).clear();
Подобные идиомы могут быть созданы, чтобы искать элемент в диапазоне.
int i = list.subList(fromIndex, toIndex).indexOf(o); int j = list.subList(fromIndex, toIndex).lastIndexOf(o);
Отметьте, что предыдущие идиомы возвращают индексирование найденного элемента в subList, не индексирование в поддержке List.
Любой полиморфный алгоритм, который работает на a List, такой как replace и shuffle примеры, работы с List возвращенный subList.
Вот полиморфный алгоритм, реализация которого использует subList иметь дело рука из деки. Таким образом, это возвращает новое List ("рука") содержащий конкретное количество элементов, взятых от конца указанного List ("дека"). Элементы, возвращенные в руке, удаляются из деки.
public static <E> List<E> dealHand(List<E> deck, int n) {
int deckSize = deck.size();
List<E> handView = deck.subList(deckSize - n, deckSize);
List<E> hand = new ArrayList<E>(handView);
handView.clear();
return hand;
}
Отметьте, что этот алгоритм удаляет руку из конца деки. Для многих распространенных List реализации, такой как ArrayList, производительность удаления элементов от конца списка существенно лучше чем то из удаления элементов с начала.
Следующее a program это использует dealHand метод в комбинации с Collections.shuffle генерировать руки из нормальной деки с 52 картами. Программа берет два параметра командной строки: (1) число рук, чтобы иметь дело и (2) число карт в каждой руке.
import java.util.*;
public class Deal {
public static void main(String[] args) {
if (args.length < 2) {
System.out.println("Usage: Deal hands cards");
return;
}
int numHands = Integer.parseInt(args[0]);
int cardsPerHand = Integer.parseInt(args[1]);
// Make a normal 52-card deck.
String[] suit = new String[] {
"spades", "hearts",
"diamonds", "clubs"
};
String[] rank = new String[] {
"ace", "2", "3", "4",
"5", "6", "7", "8", "9", "10",
"jack", "queen", "king"
};
List<String> deck = new ArrayList<String>();
for (int i = 0; i < suit.length; i++)
for (int j = 0; j < rank.length; j++)
deck.add(rank[j] + " of " + suit[i]);
// Shuffle the deck.
Collections.shuffle(deck);
if (numHands * cardsPerHand > deck.size()) {
System.out.println("Not enough cards.");
return;
}
for (int i = 0; i < numHands; i++)
System.out.println(dealHand(deck, cardsPerHand));
}
public static <E> List<E> dealHand(List<E> deck, int n) {
int deckSize = deck.size();
List<E> handView = deck.subList(deckSize - n, deckSize);
List<E> hand = new ArrayList<E>(handView);
handView.clear();
return hand;
}
}
Выполнение программы производит вывод как следующий.
% java Deal 4 5
[8 of hearts, jack of spades, 3 of spades, 4 of spades,
king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts,
queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds,
9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts,
ace of hearts]
Хотя subList работа чрезвычайно мощна, некоторая забота должна быть осуществлена при использовании ее. Семантика List возвращенный subList станьте неопределенными, если элементы добавляются к или удаляются из поддержки List всегда кроме через возвращенный List. Таким образом это настоятельно рекомендуется это, Вы используете List возвращенный subList только как временный объект — чтобы выполнить один или последовательность операций диапазона на поддержке List. Дольше Вы используете subList экземпляр, большее вероятность, что Вы поставите под угрозу это, изменяя поддержку List непосредственно или через другого subList объект. Отметьте, что законно изменить подсписок подсписка и продолжать использовать исходный подсписок (хотя не одновременно).
Большинство полиморфных алгоритмов в Collections class применяется определенно к List. Наличие всех этих алгоритмов в вашем распоряжении делает очень легким управлять списками. Вот сводка этих алгоритмов, которые описываются более подробно в разделе Алгоритмов.
sort — виды a List использование алгоритма сортировки слиянием, который обеспечивает быстрый, устойчивый вид. (Устойчивый вид является тем, который не переупорядочивает равные элементы.)shuffle — в произвольном порядке переставляет элементы в a List.reverse — инвертирует порядок элементов в a List.rotate — поворачивает все элементы в a List указанным расстоянием.swap — подкачивает элементы в указанных позициях в a List.replaceAll — замены все возникновения одного указанного значения с другим.fill — перезаписывает каждый элемент в a List с указанным значением.copy — копирует источник List в место назначения List.binarySearch — поиски элемента в упорядоченном List использование алгоритма двоичного поиска.indexOfSubList — возвращает индексирование первого подсписка одного List это равно другому.lastIndexOfSubList — возвращает индексирование последнего подсписка одного List это равно другому.
|
