1 /* 2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 import java.util.function.UnaryOperator; 29 30 // Android-removed: removed link to collections framework docs 31 /** 32 * An ordered collection (also known as a <i>sequence</i>). The user of this 33 * interface has precise control over where in the list each element is 34 * inserted. The user can access elements by their integer index (position in 35 * the list), and search for elements in the list.<p> 36 * 37 * Unlike sets, lists typically allow duplicate elements. More formally, 38 * lists typically allow pairs of elements {@code e1} and {@code e2} 39 * such that {@code e1.equals(e2)}, and they typically allow multiple 40 * null elements if they allow null elements at all. It is not inconceivable 41 * that someone might wish to implement a list that prohibits duplicates, by 42 * throwing runtime exceptions when the user attempts to insert them, but we 43 * expect this usage to be rare.<p> 44 * 45 * The {@code List} interface places additional stipulations, beyond those 46 * specified in the {@code Collection} interface, on the contracts of the 47 * {@code iterator}, {@code add}, {@code remove}, {@code equals}, and 48 * {@code hashCode} methods. Declarations for other inherited methods are 49 * also included here for convenience.<p> 50 * 51 * The {@code List} interface provides four methods for positional (indexed) 52 * access to list elements. Lists (like Java arrays) are zero based. Note 53 * that these operations may execute in time proportional to the index value 54 * for some implementations (the {@code LinkedList} class, for 55 * example). Thus, iterating over the elements in a list is typically 56 * preferable to indexing through it if the caller does not know the 57 * implementation.<p> 58 * 59 * The {@code List} interface provides a special iterator, called a 60 * {@code ListIterator}, that allows element insertion and replacement, and 61 * bidirectional access in addition to the normal operations that the 62 * {@code Iterator} interface provides. A method is provided to obtain a 63 * list iterator that starts at a specified position in the list.<p> 64 * 65 * The {@code List} interface provides two methods to search for a specified 66 * object. From a performance standpoint, these methods should be used with 67 * caution. In many implementations they will perform costly linear 68 * searches.<p> 69 * 70 * The {@code List} interface provides two methods to efficiently insert and 71 * remove multiple elements at an arbitrary point in the list.<p> 72 * 73 * Note: While it is permissible for lists to contain themselves as elements, 74 * extreme caution is advised: the {@code equals} and {@code hashCode} 75 * methods are no longer well defined on such a list. 76 * 77 * <p>Some list implementations have restrictions on the elements that 78 * they may contain. For example, some implementations prohibit null elements, 79 * and some have restrictions on the types of their elements. Attempting to 80 * add an ineligible element throws an unchecked exception, typically 81 * {@code NullPointerException} or {@code ClassCastException}. Attempting 82 * to query the presence of an ineligible element may throw an exception, 83 * or it may simply return false; some implementations will exhibit the former 84 * behavior and some will exhibit the latter. More generally, attempting an 85 * operation on an ineligible element whose completion would not result in 86 * the insertion of an ineligible element into the list may throw an 87 * exception or it may succeed, at the option of the implementation. 88 * Such exceptions are marked as "optional" in the specification for this 89 * interface. 90 * 91 * <h2><a id="unmodifiable">Unmodifiable Lists</a></h2> 92 * <p>The {@link List#of(Object...) List.of} and 93 * {@link List#copyOf List.copyOf} static factory methods 94 * provide a convenient way to create unmodifiable lists. The {@code List} 95 * instances created by these methods have the following characteristics: 96 * 97 * <ul> 98 * <li>They are <a href="Collection.html#unmodifiable"><i>unmodifiable</i></a>. Elements cannot 99 * be added, removed, or replaced. Calling any mutator method on the List 100 * will always cause {@code UnsupportedOperationException} to be thrown. 101 * However, if the contained elements are themselves mutable, 102 * this may cause the List's contents to appear to change. 103 * <li>They disallow {@code null} elements. Attempts to create them with 104 * {@code null} elements result in {@code NullPointerException}. 105 * <li>They are serializable if all elements are serializable. 106 * <li>The order of elements in the list is the same as the order of the 107 * provided arguments, or of the elements in the provided array. 108 * <li>They are <a href="../lang/doc-files/ValueBased.html">value-based</a>. 109 * Callers should make no assumptions about the identity of the returned instances. 110 * Factories are free to create new instances or reuse existing ones. Therefore, 111 * identity-sensitive operations on these instances (reference equality ({@code ==}), 112 * identity hash code, and synchronization) are unreliable and should be avoided. 113 * <li>They are serialized as specified on the 114 * <a href="{@docRoot}/serialized-form.html#java.util.CollSer">Serialized Form</a> 115 * page. 116 * </ul> 117 * 118 * @param <E> the type of elements in this list 119 * 120 * @author Josh Bloch 121 * @author Neal Gafter 122 * @see Collection 123 * @see Set 124 * @see ArrayList 125 * @see LinkedList 126 * @see Vector 127 * @see Arrays#asList(Object[]) 128 * @see Collections#nCopies(int, Object) 129 * @see Collections#EMPTY_LIST 130 * @see AbstractList 131 * @see AbstractSequentialList 132 * @since 1.2 133 */ 134 135 public interface List<E> extends Collection<E> { 136 // Query Operations 137 138 /** 139 * Returns the number of elements in this list. If this list contains 140 * more than {@code Integer.MAX_VALUE} elements, returns 141 * {@code Integer.MAX_VALUE}. 142 * 143 * @return the number of elements in this list 144 */ size()145 int size(); 146 147 /** 148 * Returns {@code true} if this list contains no elements. 149 * 150 * @return {@code true} if this list contains no elements 151 */ isEmpty()152 boolean isEmpty(); 153 154 /** 155 * Returns {@code true} if this list contains the specified element. 156 * More formally, returns {@code true} if and only if this list contains 157 * at least one element {@code e} such that 158 * {@code Objects.equals(o, e)}. 159 * 160 * @param o element whose presence in this list is to be tested 161 * @return {@code true} if this list contains the specified element 162 * @throws ClassCastException if the type of the specified element 163 * is incompatible with this list 164 * (<a href="Collection.html#optional-restrictions">optional</a>) 165 * @throws NullPointerException if the specified element is null and this 166 * list does not permit null elements 167 * (<a href="Collection.html#optional-restrictions">optional</a>) 168 */ contains(Object o)169 boolean contains(Object o); 170 171 /** 172 * Returns an iterator over the elements in this list in proper sequence. 173 * 174 * @return an iterator over the elements in this list in proper sequence 175 */ iterator()176 Iterator<E> iterator(); 177 178 /** 179 * Returns an array containing all of the elements in this list in proper 180 * sequence (from first to last element). 181 * 182 * <p>The returned array will be "safe" in that no references to it are 183 * maintained by this list. (In other words, this method must 184 * allocate a new array even if this list is backed by an array). 185 * The caller is thus free to modify the returned array. 186 * 187 * <p>This method acts as bridge between array-based and collection-based 188 * APIs. 189 * 190 * @return an array containing all of the elements in this list in proper 191 * sequence 192 * @see Arrays#asList(Object[]) 193 */ toArray()194 Object[] toArray(); 195 196 /** 197 * Returns an array containing all of the elements in this list in 198 * proper sequence (from first to last element); the runtime type of 199 * the returned array is that of the specified array. If the list fits 200 * in the specified array, it is returned therein. Otherwise, a new 201 * array is allocated with the runtime type of the specified array and 202 * the size of this list. 203 * 204 * <p>If the list fits in the specified array with room to spare (i.e., 205 * the array has more elements than the list), the element in the array 206 * immediately following the end of the list is set to {@code null}. 207 * (This is useful in determining the length of the list <i>only</i> if 208 * the caller knows that the list does not contain any null elements.) 209 * 210 * <p>Like the {@link #toArray()} method, this method acts as bridge between 211 * array-based and collection-based APIs. Further, this method allows 212 * precise control over the runtime type of the output array, and may, 213 * under certain circumstances, be used to save allocation costs. 214 * 215 * <p>Suppose {@code x} is a list known to contain only strings. 216 * The following code can be used to dump the list into a newly 217 * allocated array of {@code String}: 218 * 219 * <pre>{@code 220 * String[] y = x.toArray(new String[0]); 221 * }</pre> 222 * 223 * Note that {@code toArray(new Object[0])} is identical in function to 224 * {@code toArray()}. 225 * 226 * @param a the array into which the elements of this list are to 227 * be stored, if it is big enough; otherwise, a new array of the 228 * same runtime type is allocated for this purpose. 229 * @return an array containing the elements of this list 230 * @throws ArrayStoreException if the runtime type of the specified array 231 * is not a supertype of the runtime type of every element in 232 * this list 233 * @throws NullPointerException if the specified array is null 234 */ toArray(T[] a)235 <T> T[] toArray(T[] a); 236 237 238 // Modification Operations 239 240 /** 241 * Appends the specified element to the end of this list (optional 242 * operation). 243 * 244 * <p>Lists that support this operation may place limitations on what 245 * elements may be added to this list. In particular, some 246 * lists will refuse to add null elements, and others will impose 247 * restrictions on the type of elements that may be added. List 248 * classes should clearly specify in their documentation any restrictions 249 * on what elements may be added. 250 * 251 * @param e element to be appended to this list 252 * @return {@code true} (as specified by {@link Collection#add}) 253 * @throws UnsupportedOperationException if the {@code add} operation 254 * is not supported by this list 255 * @throws ClassCastException if the class of the specified element 256 * prevents it from being added to this list 257 * @throws NullPointerException if the specified element is null and this 258 * list does not permit null elements 259 * @throws IllegalArgumentException if some property of this element 260 * prevents it from being added to this list 261 */ add(E e)262 boolean add(E e); 263 264 /** 265 * Removes the first occurrence of the specified element from this list, 266 * if it is present (optional operation). If this list does not contain 267 * the element, it is unchanged. More formally, removes the element with 268 * the lowest index {@code i} such that 269 * {@code Objects.equals(o, get(i))} 270 * (if such an element exists). Returns {@code true} if this list 271 * contained the specified element (or equivalently, if this list changed 272 * as a result of the call). 273 * 274 * @param o element to be removed from this list, if present 275 * @return {@code true} if this list contained the specified element 276 * @throws ClassCastException if the type of the specified element 277 * is incompatible with this list 278 * (<a href="Collection.html#optional-restrictions">optional</a>) 279 * @throws NullPointerException if the specified element is null and this 280 * list does not permit null elements 281 * (<a href="Collection.html#optional-restrictions">optional</a>) 282 * @throws UnsupportedOperationException if the {@code remove} operation 283 * is not supported by this list 284 */ remove(Object o)285 boolean remove(Object o); 286 287 288 // Bulk Modification Operations 289 290 /** 291 * Returns {@code true} if this list contains all of the elements of the 292 * specified collection. 293 * 294 * @param c collection to be checked for containment in this list 295 * @return {@code true} if this list contains all of the elements of the 296 * specified collection 297 * @throws ClassCastException if the types of one or more elements 298 * in the specified collection are incompatible with this 299 * list 300 * (<a href="Collection.html#optional-restrictions">optional</a>) 301 * @throws NullPointerException if the specified collection contains one 302 * or more null elements and this list does not permit null 303 * elements 304 * (<a href="Collection.html#optional-restrictions">optional</a>), 305 * or if the specified collection is null 306 * @see #contains(Object) 307 */ containsAll(Collection<?> c)308 boolean containsAll(Collection<?> c); 309 310 /** 311 * Appends all of the elements in the specified collection to the end of 312 * this list, in the order that they are returned by the specified 313 * collection's iterator (optional operation). The behavior of this 314 * operation is undefined if the specified collection is modified while 315 * the operation is in progress. (Note that this will occur if the 316 * specified collection is this list, and it's nonempty.) 317 * 318 * @param c collection containing elements to be added to this list 319 * @return {@code true} if this list changed as a result of the call 320 * @throws UnsupportedOperationException if the {@code addAll} operation 321 * is not supported by this list 322 * @throws ClassCastException if the class of an element of the specified 323 * collection prevents it from being added to this list 324 * @throws NullPointerException if the specified collection contains one 325 * or more null elements and this list does not permit null 326 * elements, or if the specified collection is null 327 * @throws IllegalArgumentException if some property of an element of the 328 * specified collection prevents it from being added to this list 329 * @see #add(Object) 330 */ addAll(Collection<? extends E> c)331 boolean addAll(Collection<? extends E> c); 332 333 /** 334 * Inserts all of the elements in the specified collection into this 335 * list at the specified position (optional operation). Shifts the 336 * element currently at that position (if any) and any subsequent 337 * elements to the right (increases their indices). The new elements 338 * will appear in this list in the order that they are returned by the 339 * specified collection's iterator. The behavior of this operation is 340 * undefined if the specified collection is modified while the 341 * operation is in progress. (Note that this will occur if the specified 342 * collection is this list, and it's nonempty.) 343 * 344 * @param index index at which to insert the first element from the 345 * specified collection 346 * @param c collection containing elements to be added to this list 347 * @return {@code true} if this list changed as a result of the call 348 * @throws UnsupportedOperationException if the {@code addAll} operation 349 * is not supported by this list 350 * @throws ClassCastException if the class of an element of the specified 351 * collection prevents it from being added to this list 352 * @throws NullPointerException if the specified collection contains one 353 * or more null elements and this list does not permit null 354 * elements, or if the specified collection is null 355 * @throws IllegalArgumentException if some property of an element of the 356 * specified collection prevents it from being added to this list 357 * @throws IndexOutOfBoundsException if the index is out of range 358 * ({@code index < 0 || index > size()}) 359 */ addAll(int index, Collection<? extends E> c)360 boolean addAll(int index, Collection<? extends E> c); 361 362 /** 363 * Removes from this list all of its elements that are contained in the 364 * specified collection (optional operation). 365 * 366 * @param c collection containing elements to be removed from this list 367 * @return {@code true} if this list changed as a result of the call 368 * @throws UnsupportedOperationException if the {@code removeAll} operation 369 * is not supported by this list 370 * @throws ClassCastException if the class of an element of this list 371 * is incompatible with the specified collection 372 * (<a href="Collection.html#optional-restrictions">optional</a>) 373 * @throws NullPointerException if this list contains a null element and the 374 * specified collection does not permit null elements 375 * (<a href="Collection.html#optional-restrictions">optional</a>), 376 * or if the specified collection is null 377 * @see #remove(Object) 378 * @see #contains(Object) 379 */ removeAll(Collection<?> c)380 boolean removeAll(Collection<?> c); 381 382 /** 383 * Retains only the elements in this list that are contained in the 384 * specified collection (optional operation). In other words, removes 385 * from this list all of its elements that are not contained in the 386 * specified collection. 387 * 388 * @param c collection containing elements to be retained in this list 389 * @return {@code true} if this list changed as a result of the call 390 * @throws UnsupportedOperationException if the {@code retainAll} operation 391 * is not supported by this list 392 * @throws ClassCastException if the class of an element of this list 393 * is incompatible with the specified collection 394 * (<a href="Collection.html#optional-restrictions">optional</a>) 395 * @throws NullPointerException if this list contains a null element and the 396 * specified collection does not permit null elements 397 * (<a href="Collection.html#optional-restrictions">optional</a>), 398 * or if the specified collection is null 399 * @see #remove(Object) 400 * @see #contains(Object) 401 */ retainAll(Collection<?> c)402 boolean retainAll(Collection<?> c); 403 404 /** 405 * Replaces each element of this list with the result of applying the 406 * operator to that element. Errors or runtime exceptions thrown by 407 * the operator are relayed to the caller. 408 * 409 * @implSpec 410 * The default implementation is equivalent to, for this {@code list}: 411 * <pre>{@code 412 * final ListIterator<E> li = list.listIterator(); 413 * while (li.hasNext()) { 414 * li.set(operator.apply(li.next())); 415 * } 416 * }</pre> 417 * 418 * If the list's list-iterator does not support the {@code set} operation 419 * then an {@code UnsupportedOperationException} will be thrown when 420 * replacing the first element. 421 * 422 * @param operator the operator to apply to each element 423 * @throws UnsupportedOperationException if this list is unmodifiable. 424 * Implementations may throw this exception if an element 425 * cannot be replaced or if, in general, modification is not 426 * supported 427 * @throws NullPointerException if the specified operator is null or 428 * if the operator result is a null value and this list does 429 * not permit null elements 430 * (<a href="Collection.html#optional-restrictions">optional</a>) 431 * @since 1.8 432 */ replaceAll(UnaryOperator<E> operator)433 default void replaceAll(UnaryOperator<E> operator) { 434 Objects.requireNonNull(operator); 435 final ListIterator<E> li = this.listIterator(); 436 while (li.hasNext()) { 437 li.set(operator.apply(li.next())); 438 } 439 } 440 441 // Android-added: List.sort() vs. Collections.sort() app compat. 442 // Added a warning in the documentation. 443 // Collections.sort() calls List.sort() for apps targeting API version >= 26 444 // (Android Oreo) but the other way around for app targeting <= 25 (Nougat). 445 /** 446 * Sorts this list according to the order induced by the specified 447 * {@link Comparator}. 448 * 449 * <p>All elements in this list must be <i>mutually comparable</i> using the 450 * specified comparator (that is, {@code c.compare(e1, e2)} must not throw 451 * a {@code ClassCastException} for any elements {@code e1} and {@code e2} 452 * in the list). 453 * 454 * <p>If the specified comparator is {@code null} then all elements in this 455 * list must implement the {@link Comparable} interface and the elements' 456 * {@linkplain Comparable natural ordering} should be used. 457 * 458 * <p>This list must be modifiable, but need not be resizable. 459 * 460 * <p>For apps running on and targeting Android versions greater than 461 * Nougat (API level {@code > 25}), {@link Collections#sort(List)} 462 * delegates to this method. Such apps must not call 463 * {@link Collections#sort(List)} from this method. Instead, prefer 464 * not overriding this method at all. If you must override it, consider 465 * this implementation: 466 * <pre> 467 * @Override 468 * public void sort(Comparator<? super E> c) { 469 * Object[] elements = toArray(); 470 * Arrays.sort(elements, c); 471 * ListIterator<E> iterator = (ListIterator<Object>) listIterator(); 472 * for (Object element : elements) { 473 * iterator.next(); 474 * iterator.set((E) element); 475 * } 476 * } 477 * </pre> 478 * 479 * @implSpec 480 * The default implementation obtains an array containing all elements in 481 * this list, sorts the array, and iterates over this list resetting each 482 * element from the corresponding position in the array. (This avoids the 483 * n<sup>2</sup> log(n) performance that would result from attempting 484 * to sort a linked list in place.) 485 * 486 * @implNote 487 * This implementation is a stable, adaptive, iterative mergesort that 488 * requires far fewer than n lg(n) comparisons when the input array is 489 * partially sorted, while offering the performance of a traditional 490 * mergesort when the input array is randomly ordered. If the input array 491 * is nearly sorted, the implementation requires approximately n 492 * comparisons. Temporary storage requirements vary from a small constant 493 * for nearly sorted input arrays to n/2 object references for randomly 494 * ordered input arrays. 495 * 496 * <p>The implementation takes equal advantage of ascending and 497 * descending order in its input array, and can take advantage of 498 * ascending and descending order in different parts of the same 499 * input array. It is well-suited to merging two or more sorted arrays: 500 * simply concatenate the arrays and sort the resulting array. 501 * 502 * <p>The implementation was adapted from Tim Peters's list sort for Python 503 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 504 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic 505 * Sorting and Information Theoretic Complexity", in Proceedings of the 506 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 507 * January 1993. 508 * 509 * @param c the {@code Comparator} used to compare list elements. 510 * A {@code null} value indicates that the elements' 511 * {@linkplain Comparable natural ordering} should be used 512 * @throws ClassCastException if the list contains elements that are not 513 * <i>mutually comparable</i> using the specified comparator 514 * @throws UnsupportedOperationException if the list's list-iterator does 515 * not support the {@code set} operation 516 * @throws IllegalArgumentException 517 * (<a href="Collection.html#optional-restrictions">optional</a>) 518 * if the comparator is found to violate the {@link Comparator} 519 * contract 520 * @since 1.8 521 */ 522 @SuppressWarnings({"unchecked", "rawtypes"}) sort(Comparator<? super E> c)523 default void sort(Comparator<? super E> c) { 524 Object[] a = this.toArray(); 525 Arrays.sort(a, (Comparator) c); 526 ListIterator<E> i = this.listIterator(); 527 for (Object e : a) { 528 i.next(); 529 i.set((E) e); 530 } 531 } 532 533 /** 534 * Removes all of the elements from this list (optional operation). 535 * The list will be empty after this call returns. 536 * 537 * @throws UnsupportedOperationException if the {@code clear} operation 538 * is not supported by this list 539 */ clear()540 void clear(); 541 542 543 // Comparison and hashing 544 545 /** 546 * Compares the specified object with this list for equality. Returns 547 * {@code true} if and only if the specified object is also a list, both 548 * lists have the same size, and all corresponding pairs of elements in 549 * the two lists are <i>equal</i>. (Two elements {@code e1} and 550 * {@code e2} are <i>equal</i> if {@code Objects.equals(e1, e2)}.) 551 * In other words, two lists are defined to be 552 * equal if they contain the same elements in the same order. This 553 * definition ensures that the equals method works properly across 554 * different implementations of the {@code List} interface. 555 * 556 * @param o the object to be compared for equality with this list 557 * @return {@code true} if the specified object is equal to this list 558 */ equals(Object o)559 boolean equals(Object o); 560 561 /** 562 * Returns the hash code value for this list. The hash code of a list 563 * is defined to be the result of the following calculation: 564 * <pre>{@code 565 * int hashCode = 1; 566 * for (E e : list) 567 * hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); 568 * }</pre> 569 * This ensures that {@code list1.equals(list2)} implies that 570 * {@code list1.hashCode()==list2.hashCode()} for any two lists, 571 * {@code list1} and {@code list2}, as required by the general 572 * contract of {@link Object#hashCode}. 573 * 574 * @return the hash code value for this list 575 * @see Object#equals(Object) 576 * @see #equals(Object) 577 */ hashCode()578 int hashCode(); 579 580 581 // Positional Access Operations 582 583 /** 584 * Returns the element at the specified position in this list. 585 * 586 * @param index index of the element to return 587 * @return the element at the specified position in this list 588 * @throws IndexOutOfBoundsException if the index is out of range 589 * ({@code index < 0 || index >= size()}) 590 */ get(int index)591 E get(int index); 592 593 /** 594 * Replaces the element at the specified position in this list with the 595 * specified element (optional operation). 596 * 597 * @param index index of the element to replace 598 * @param element element to be stored at the specified position 599 * @return the element previously at the specified position 600 * @throws UnsupportedOperationException if the {@code set} operation 601 * is not supported by this list 602 * @throws ClassCastException if the class of the specified element 603 * prevents it from being added to this list 604 * @throws NullPointerException if the specified element is null and 605 * this list does not permit null elements 606 * @throws IllegalArgumentException if some property of the specified 607 * element prevents it from being added to this list 608 * @throws IndexOutOfBoundsException if the index is out of range 609 * ({@code index < 0 || index >= size()}) 610 */ set(int index, E element)611 E set(int index, E element); 612 613 /** 614 * Inserts the specified element at the specified position in this list 615 * (optional operation). Shifts the element currently at that position 616 * (if any) and any subsequent elements to the right (adds one to their 617 * indices). 618 * 619 * @param index index at which the specified element is to be inserted 620 * @param element element to be inserted 621 * @throws UnsupportedOperationException if the {@code add} operation 622 * is not supported by this list 623 * @throws ClassCastException if the class of the specified element 624 * prevents it from being added to this list 625 * @throws NullPointerException if the specified element is null and 626 * this list does not permit null elements 627 * @throws IllegalArgumentException if some property of the specified 628 * element prevents it from being added to this list 629 * @throws IndexOutOfBoundsException if the index is out of range 630 * ({@code index < 0 || index > size()}) 631 */ add(int index, E element)632 void add(int index, E element); 633 634 /** 635 * Removes the element at the specified position in this list (optional 636 * operation). Shifts any subsequent elements to the left (subtracts one 637 * from their indices). Returns the element that was removed from the 638 * list. 639 * 640 * @param index the index of the element to be removed 641 * @return the element previously at the specified position 642 * @throws UnsupportedOperationException if the {@code remove} operation 643 * is not supported by this list 644 * @throws IndexOutOfBoundsException if the index is out of range 645 * ({@code index < 0 || index >= size()}) 646 */ remove(int index)647 E remove(int index); 648 649 650 // Search Operations 651 652 /** 653 * Returns the index of the first occurrence of the specified element 654 * in this list, or -1 if this list does not contain the element. 655 * More formally, returns the lowest index {@code i} such that 656 * {@code Objects.equals(o, get(i))}, 657 * or -1 if there is no such index. 658 * 659 * @param o element to search for 660 * @return the index of the first occurrence of the specified element in 661 * this list, or -1 if this list does not contain the element 662 * @throws ClassCastException if the type of the specified element 663 * is incompatible with this list 664 * (<a href="Collection.html#optional-restrictions">optional</a>) 665 * @throws NullPointerException if the specified element is null and this 666 * list does not permit null elements 667 * (<a href="Collection.html#optional-restrictions">optional</a>) 668 */ indexOf(Object o)669 int indexOf(Object o); 670 671 /** 672 * Returns the index of the last occurrence of the specified element 673 * in this list, or -1 if this list does not contain the element. 674 * More formally, returns the highest index {@code i} such that 675 * {@code Objects.equals(o, get(i))}, 676 * or -1 if there is no such index. 677 * 678 * @param o element to search for 679 * @return the index of the last occurrence of the specified element in 680 * this list, or -1 if this list does not contain the element 681 * @throws ClassCastException if the type of the specified element 682 * is incompatible with this list 683 * (<a href="Collection.html#optional-restrictions">optional</a>) 684 * @throws NullPointerException if the specified element is null and this 685 * list does not permit null elements 686 * (<a href="Collection.html#optional-restrictions">optional</a>) 687 */ lastIndexOf(Object o)688 int lastIndexOf(Object o); 689 690 691 // List Iterators 692 693 /** 694 * Returns a list iterator over the elements in this list (in proper 695 * sequence). 696 * 697 * @return a list iterator over the elements in this list (in proper 698 * sequence) 699 */ listIterator()700 ListIterator<E> listIterator(); 701 702 /** 703 * Returns a list iterator over the elements in this list (in proper 704 * sequence), starting at the specified position in the list. 705 * The specified index indicates the first element that would be 706 * returned by an initial call to {@link ListIterator#next next}. 707 * An initial call to {@link ListIterator#previous previous} would 708 * return the element with the specified index minus one. 709 * 710 * @param index index of the first element to be returned from the 711 * list iterator (by a call to {@link ListIterator#next next}) 712 * @return a list iterator over the elements in this list (in proper 713 * sequence), starting at the specified position in the list 714 * @throws IndexOutOfBoundsException if the index is out of range 715 * ({@code index < 0 || index > size()}) 716 */ listIterator(int index)717 ListIterator<E> listIterator(int index); 718 719 // View 720 721 /** 722 * Returns a view of the portion of this list between the specified 723 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If 724 * {@code fromIndex} and {@code toIndex} are equal, the returned list is 725 * empty.) The returned list is backed by this list, so non-structural 726 * changes in the returned list are reflected in this list, and vice-versa. 727 * The returned list supports all of the optional list operations supported 728 * by this list.<p> 729 * 730 * This method eliminates the need for explicit range operations (of 731 * the sort that commonly exist for arrays). Any operation that expects 732 * a list can be used as a range operation by passing a subList view 733 * instead of a whole list. For example, the following idiom 734 * removes a range of elements from a list: 735 * <pre>{@code 736 * list.subList(from, to).clear(); 737 * }</pre> 738 * Similar idioms may be constructed for {@code indexOf} and 739 * {@code lastIndexOf}, and all of the algorithms in the 740 * {@code Collections} class can be applied to a subList.<p> 741 * 742 * The semantics of the list returned by this method become undefined if 743 * the backing list (i.e., this list) is <i>structurally modified</i> in 744 * any way other than via the returned list. (Structural modifications are 745 * those that change the size of this list, or otherwise perturb it in such 746 * a fashion that iterations in progress may yield incorrect results.) 747 * 748 * @param fromIndex low endpoint (inclusive) of the subList 749 * @param toIndex high endpoint (exclusive) of the subList 750 * @return a view of the specified range within this list 751 * @throws IndexOutOfBoundsException for an illegal endpoint index value 752 * ({@code fromIndex < 0 || toIndex > size || 753 * fromIndex > toIndex}) 754 */ subList(int fromIndex, int toIndex)755 List<E> subList(int fromIndex, int toIndex); 756 757 /** 758 * Creates a {@link Spliterator} over the elements in this list. 759 * 760 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and 761 * {@link Spliterator#ORDERED}. Implementations should document the 762 * reporting of additional characteristic values. 763 * 764 * @implSpec 765 * The default implementation creates a 766 * <em><a href="Spliterator.html#binding">late-binding</a></em> 767 * spliterator as follows: 768 * <ul> 769 * <li>If the list is an instance of {@link RandomAccess} then the default 770 * implementation creates a spliterator that traverses elements by 771 * invoking the method {@link List#get}. If such invocation results or 772 * would result in an {@code IndexOutOfBoundsException} then the 773 * spliterator will <em>fail-fast</em> and throw a 774 * {@code ConcurrentModificationException}. 775 * If the list is also an instance of {@link AbstractList} then the 776 * spliterator will use the list's {@link AbstractList#modCount modCount} 777 * field to provide additional <em>fail-fast</em> behavior. 778 * <li>Otherwise, the default implementation creates a spliterator from the 779 * list's {@code Iterator}. The spliterator inherits the 780 * <em>fail-fast</em> of the list's iterator. 781 * </ul> 782 * 783 * @implNote 784 * The created {@code Spliterator} additionally reports 785 * {@link Spliterator#SUBSIZED}. 786 * 787 * @return a {@code Spliterator} over the elements in this list 788 * @since 1.8 789 */ 790 @Override spliterator()791 default Spliterator<E> spliterator() { 792 if (this instanceof RandomAccess) { 793 return new AbstractList.RandomAccessSpliterator<>(this); 794 } else { 795 return Spliterators.spliterator(this, Spliterator.ORDERED); 796 } 797 } 798 799 /** 800 * Returns an unmodifiable list containing zero elements. 801 * 802 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 803 * 804 * @param <E> the {@code List}'s element type 805 * @return an empty {@code List} 806 * 807 * @since 9 808 */ of()809 static <E> List<E> of() { 810 return ImmutableCollections.emptyList(); 811 } 812 813 /** 814 * Returns an unmodifiable list containing one element. 815 * 816 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 817 * 818 * @param <E> the {@code List}'s element type 819 * @param e1 the single element 820 * @return a {@code List} containing the specified element 821 * @throws NullPointerException if the element is {@code null} 822 * 823 * @since 9 824 */ of(E e1)825 static <E> List<E> of(E e1) { 826 return new ImmutableCollections.List12<>(e1); 827 } 828 829 /** 830 * Returns an unmodifiable list containing two elements. 831 * 832 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 833 * 834 * @param <E> the {@code List}'s element type 835 * @param e1 the first element 836 * @param e2 the second element 837 * @return a {@code List} containing the specified elements 838 * @throws NullPointerException if an element is {@code null} 839 * 840 * @since 9 841 */ of(E e1, E e2)842 static <E> List<E> of(E e1, E e2) { 843 return new ImmutableCollections.List12<>(e1, e2); 844 } 845 846 /** 847 * Returns an unmodifiable list containing three elements. 848 * 849 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 850 * 851 * @param <E> the {@code List}'s element type 852 * @param e1 the first element 853 * @param e2 the second element 854 * @param e3 the third element 855 * @return a {@code List} containing the specified elements 856 * @throws NullPointerException if an element is {@code null} 857 * 858 * @since 9 859 */ of(E e1, E e2, E e3)860 static <E> List<E> of(E e1, E e2, E e3) { 861 return new ImmutableCollections.ListN<>(e1, e2, e3); 862 } 863 864 /** 865 * Returns an unmodifiable list containing four elements. 866 * 867 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 868 * 869 * @param <E> the {@code List}'s element type 870 * @param e1 the first element 871 * @param e2 the second element 872 * @param e3 the third element 873 * @param e4 the fourth element 874 * @return a {@code List} containing the specified elements 875 * @throws NullPointerException if an element is {@code null} 876 * 877 * @since 9 878 */ of(E e1, E e2, E e3, E e4)879 static <E> List<E> of(E e1, E e2, E e3, E e4) { 880 return new ImmutableCollections.ListN<>(e1, e2, e3, e4); 881 } 882 883 /** 884 * Returns an unmodifiable list containing five elements. 885 * 886 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 887 * 888 * @param <E> the {@code List}'s element type 889 * @param e1 the first element 890 * @param e2 the second element 891 * @param e3 the third element 892 * @param e4 the fourth element 893 * @param e5 the fifth element 894 * @return a {@code List} containing the specified elements 895 * @throws NullPointerException if an element is {@code null} 896 * 897 * @since 9 898 */ of(E e1, E e2, E e3, E e4, E e5)899 static <E> List<E> of(E e1, E e2, E e3, E e4, E e5) { 900 return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5); 901 } 902 903 /** 904 * Returns an unmodifiable list containing six elements. 905 * 906 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 907 * 908 * @param <E> the {@code List}'s element type 909 * @param e1 the first element 910 * @param e2 the second element 911 * @param e3 the third element 912 * @param e4 the fourth element 913 * @param e5 the fifth element 914 * @param e6 the sixth element 915 * @return a {@code List} containing the specified elements 916 * @throws NullPointerException if an element is {@code null} 917 * 918 * @since 9 919 */ of(E e1, E e2, E e3, E e4, E e5, E e6)920 static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6) { 921 return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5, 922 e6); 923 } 924 925 /** 926 * Returns an unmodifiable list containing seven elements. 927 * 928 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 929 * 930 * @param <E> the {@code List}'s element type 931 * @param e1 the first element 932 * @param e2 the second element 933 * @param e3 the third element 934 * @param e4 the fourth element 935 * @param e5 the fifth element 936 * @param e6 the sixth element 937 * @param e7 the seventh element 938 * @return a {@code List} containing the specified elements 939 * @throws NullPointerException if an element is {@code null} 940 * 941 * @since 9 942 */ of(E e1, E e2, E e3, E e4, E e5, E e6, E e7)943 static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) { 944 return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5, 945 e6, e7); 946 } 947 948 /** 949 * Returns an unmodifiable list containing eight elements. 950 * 951 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 952 * 953 * @param <E> the {@code List}'s element type 954 * @param e1 the first element 955 * @param e2 the second element 956 * @param e3 the third element 957 * @param e4 the fourth element 958 * @param e5 the fifth element 959 * @param e6 the sixth element 960 * @param e7 the seventh element 961 * @param e8 the eighth element 962 * @return a {@code List} containing the specified elements 963 * @throws NullPointerException if an element is {@code null} 964 * 965 * @since 9 966 */ of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8)967 static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) { 968 return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5, 969 e6, e7, e8); 970 } 971 972 /** 973 * Returns an unmodifiable list containing nine elements. 974 * 975 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 976 * 977 * @param <E> the {@code List}'s element type 978 * @param e1 the first element 979 * @param e2 the second element 980 * @param e3 the third element 981 * @param e4 the fourth element 982 * @param e5 the fifth element 983 * @param e6 the sixth element 984 * @param e7 the seventh element 985 * @param e8 the eighth element 986 * @param e9 the ninth element 987 * @return a {@code List} containing the specified elements 988 * @throws NullPointerException if an element is {@code null} 989 * 990 * @since 9 991 */ of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9)992 static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) { 993 return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5, 994 e6, e7, e8, e9); 995 } 996 997 /** 998 * Returns an unmodifiable list containing ten elements. 999 * 1000 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 1001 * 1002 * @param <E> the {@code List}'s element type 1003 * @param e1 the first element 1004 * @param e2 the second element 1005 * @param e3 the third element 1006 * @param e4 the fourth element 1007 * @param e5 the fifth element 1008 * @param e6 the sixth element 1009 * @param e7 the seventh element 1010 * @param e8 the eighth element 1011 * @param e9 the ninth element 1012 * @param e10 the tenth element 1013 * @return a {@code List} containing the specified elements 1014 * @throws NullPointerException if an element is {@code null} 1015 * 1016 * @since 9 1017 */ of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10)1018 static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) { 1019 return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5, 1020 e6, e7, e8, e9, e10); 1021 } 1022 1023 /** 1024 * Returns an unmodifiable list containing an arbitrary number of elements. 1025 * See <a href="#unmodifiable">Unmodifiable Lists</a> for details. 1026 * 1027 * @apiNote 1028 * This method also accepts a single array as an argument. The element type of 1029 * the resulting list will be the component type of the array, and the size of 1030 * the list will be equal to the length of the array. To create a list with 1031 * a single element that is an array, do the following: 1032 * 1033 * <pre>{@code 1034 * String[] array = ... ; 1035 * List<String[]> list = List.<String[]>of(array); 1036 * }</pre> 1037 * 1038 * This will cause the {@link List#of(Object) List.of(E)} method 1039 * to be invoked instead. 1040 * 1041 * @param <E> the {@code List}'s element type 1042 * @param elements the elements to be contained in the list 1043 * @return a {@code List} containing the specified elements 1044 * @throws NullPointerException if an element is {@code null} or if the array is {@code null} 1045 * 1046 * @since 9 1047 */ 1048 @SafeVarargs 1049 @SuppressWarnings("varargs") of(E... elements)1050 static <E> List<E> of(E... elements) { 1051 switch (elements.length) { // implicit null check of elements 1052 case 0: 1053 return ImmutableCollections.emptyList(); 1054 case 1: 1055 return new ImmutableCollections.List12<>(elements[0]); 1056 case 2: 1057 return new ImmutableCollections.List12<>(elements[0], elements[1]); 1058 default: 1059 return new ImmutableCollections.ListN<>(elements); 1060 } 1061 } 1062 1063 /** 1064 * Returns an <a href="#unmodifiable">unmodifiable List</a> containing the elements of 1065 * the given Collection, in its iteration order. The given Collection must not be null, 1066 * and it must not contain any null elements. If the given Collection is subsequently 1067 * modified, the returned List will not reflect such modifications. 1068 * 1069 * @implNote 1070 * If the given Collection is an <a href="#unmodifiable">unmodifiable List</a>, 1071 * calling copyOf will generally not create a copy. 1072 * 1073 * @param <E> the {@code List}'s element type 1074 * @param coll a {@code Collection} from which elements are drawn, must be non-null 1075 * @return a {@code List} containing the elements of the given {@code Collection} 1076 * @throws NullPointerException if coll is null, or if it contains any nulls 1077 * @since 10 1078 */ copyOf(Collection<? extends E> coll)1079 static <E> List<E> copyOf(Collection<? extends E> coll) { 1080 return ImmutableCollections.listCopy(coll); 1081 } 1082 } 1083