1 /* 2 * Copyright 1997-2007 Sun Microsystems, Inc. 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. Sun designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 22 * CA 95054 USA or visit www.sun.com if you need additional information or 23 * have any questions. 24 */ 25 26 package java.util; 27 28 /** 29 * An ordered collection (also known as a <i>sequence</i>). The user of this 30 * interface has precise control over where in the list each element is 31 * inserted. The user can access elements by their integer index (position in 32 * the list), and search for elements in the list.<p> 33 * 34 * Unlike sets, lists typically allow duplicate elements. More formally, 35 * lists typically allow pairs of elements <tt>e1</tt> and <tt>e2</tt> 36 * such that <tt>e1.equals(e2)</tt>, and they typically allow multiple 37 * null elements if they allow null elements at all. It is not inconceivable 38 * that someone might wish to implement a list that prohibits duplicates, by 39 * throwing runtime exceptions when the user attempts to insert them, but we 40 * expect this usage to be rare.<p> 41 * 42 * The <tt>List</tt> interface places additional stipulations, beyond those 43 * specified in the <tt>Collection</tt> interface, on the contracts of the 44 * <tt>iterator</tt>, <tt>add</tt>, <tt>remove</tt>, <tt>equals</tt>, and 45 * <tt>hashCode</tt> methods. Declarations for other inherited methods are 46 * also included here for convenience.<p> 47 * 48 * The <tt>List</tt> interface provides four methods for positional (indexed) 49 * access to list elements. Lists (like Java arrays) are zero based. Note 50 * that these operations may execute in time proportional to the index value 51 * for some implementations (the <tt>LinkedList</tt> class, for 52 * example). Thus, iterating over the elements in a list is typically 53 * preferable to indexing through it if the caller does not know the 54 * implementation.<p> 55 * 56 * The <tt>List</tt> interface provides a special iterator, called a 57 * <tt>ListIterator</tt>, that allows element insertion and replacement, and 58 * bidirectional access in addition to the normal operations that the 59 * <tt>Iterator</tt> interface provides. A method is provided to obtain a 60 * list iterator that starts at a specified position in the list.<p> 61 * 62 * The <tt>List</tt> interface provides two methods to search for a specified 63 * object. From a performance standpoint, these methods should be used with 64 * caution. In many implementations they will perform costly linear 65 * searches.<p> 66 * 67 * The <tt>List</tt> interface provides two methods to efficiently insert and 68 * remove multiple elements at an arbitrary point in the list.<p> 69 * 70 * Note: While it is permissible for lists to contain themselves as elements, 71 * extreme caution is advised: the <tt>equals</tt> and <tt>hashCode</tt> 72 * methods are no longer well defined on such a list. 73 * 74 * <p>Some list implementations have restrictions on the elements that 75 * they may contain. For example, some implementations prohibit null elements, 76 * and some have restrictions on the types of their elements. Attempting to 77 * add an ineligible element throws an unchecked exception, typically 78 * <tt>NullPointerException</tt> or <tt>ClassCastException</tt>. Attempting 79 * to query the presence of an ineligible element may throw an exception, 80 * or it may simply return false; some implementations will exhibit the former 81 * behavior and some will exhibit the latter. More generally, attempting an 82 * operation on an ineligible element whose completion would not result in 83 * the insertion of an ineligible element into the list may throw an 84 * exception or it may succeed, at the option of the implementation. 85 * Such exceptions are marked as "optional" in the specification for this 86 * interface. 87 * 88 * <p>This interface is a member of the 89 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 90 * Java Collections Framework</a>. 91 * 92 * @param <E> the type of elements in this list 93 * 94 * @author Josh Bloch 95 * @author Neal Gafter 96 * @see Collection 97 * @see Set 98 * @see ArrayList 99 * @see LinkedList 100 * @see Vector 101 * @see Arrays#asList(Object[]) 102 * @see Collections#nCopies(int, Object) 103 * @see Collections#EMPTY_LIST 104 * @see AbstractList 105 * @see AbstractSequentialList 106 * @since 1.2 107 */ 108 109 public interface List<E> extends Collection<E> { 110 // Query Operations 111 112 /** 113 * Returns the number of elements in this list. If this list contains 114 * more than <tt>Integer.MAX_VALUE</tt> elements, returns 115 * <tt>Integer.MAX_VALUE</tt>. 116 * 117 * @return the number of elements in this list 118 */ 119 int size(); 120 121 /** 122 * Returns <tt>true</tt> if this list contains no elements. 123 * 124 * @return <tt>true</tt> if this list contains no elements 125 */ 126 boolean isEmpty(); 127 128 /** 129 * Returns <tt>true</tt> if this list contains the specified element. 130 * More formally, returns <tt>true</tt> if and only if this list contains 131 * at least one element <tt>e</tt> such that 132 * <tt>(o==null ? e==null : o.equals(e))</tt>. 133 * 134 * @param o element whose presence in this list is to be tested 135 * @return <tt>true</tt> if this list contains the specified element 136 * @throws ClassCastException if the type of the specified element 137 * is incompatible with this list (optional) 138 * @throws NullPointerException if the specified element is null and this 139 * list does not permit null elements (optional) 140 */ 141 boolean contains(Object o); 142 143 /** 144 * Returns an iterator over the elements in this list in proper sequence. 145 * 146 * @return an iterator over the elements in this list in proper sequence 147 */ 148 Iterator<E> iterator(); 149 150 /** 151 * Returns an array containing all of the elements in this list in proper 152 * sequence (from first to last element). 153 * 154 * <p>The returned array will be "safe" in that no references to it are 155 * maintained by this list. (In other words, this method must 156 * allocate a new array even if this list is backed by an array). 157 * The caller is thus free to modify the returned array. 158 * 159 * <p>This method acts as bridge between array-based and collection-based 160 * APIs. 161 * 162 * @return an array containing all of the elements in this list in proper 163 * sequence 164 * @see Arrays#asList(Object[]) 165 */ 166 Object[] toArray(); 167 168 /** 169 * Returns an array containing all of the elements in this list in 170 * proper sequence (from first to last element); the runtime type of 171 * the returned array is that of the specified array. If the list fits 172 * in the specified array, it is returned therein. Otherwise, a new 173 * array is allocated with the runtime type of the specified array and 174 * the size of this list. 175 * 176 * <p>If the list fits in the specified array with room to spare (i.e., 177 * the array has more elements than the list), the element in the array 178 * immediately following the end of the list is set to <tt>null</tt>. 179 * (This is useful in determining the length of the list <i>only</i> if 180 * the caller knows that the list does not contain any null elements.) 181 * 182 * <p>Like the {@link #toArray()} method, this method acts as bridge between 183 * array-based and collection-based APIs. Further, this method allows 184 * precise control over the runtime type of the output array, and may, 185 * under certain circumstances, be used to save allocation costs. 186 * 187 * <p>Suppose <tt>x</tt> is a list known to contain only strings. 188 * The following code can be used to dump the list into a newly 189 * allocated array of <tt>String</tt>: 190 * 191 * <pre> 192 * String[] y = x.toArray(new String[0]);</pre> 193 * 194 * Note that <tt>toArray(new Object[0])</tt> is identical in function to 195 * <tt>toArray()</tt>. 196 * 197 * @param a the array into which the elements of this list are to 198 * be stored, if it is big enough; otherwise, a new array of the 199 * same runtime type is allocated for this purpose. 200 * @return an array containing the elements of this list 201 * @throws ArrayStoreException if the runtime type of the specified array 202 * is not a supertype of the runtime type of every element in 203 * this list 204 * @throws NullPointerException if the specified array is null 205 */ 206 <T> T[] toArray(T[] a); 207 208 209 // Modification Operations 210 211 /** 212 * Appends the specified element to the end of this list (optional 213 * operation). 214 * 215 * <p>Lists that support this operation may place limitations on what 216 * elements may be added to this list. In particular, some 217 * lists will refuse to add null elements, and others will impose 218 * restrictions on the type of elements that may be added. List 219 * classes should clearly specify in their documentation any restrictions 220 * on what elements may be added. 221 * 222 * @param e element to be appended to this list 223 * @return <tt>true</tt> (as specified by {@link Collection#add}) 224 * @throws UnsupportedOperationException if the <tt>add</tt> operation 225 * is not supported by this list 226 * @throws ClassCastException if the class of the specified element 227 * prevents it from being added to this list 228 * @throws NullPointerException if the specified element is null and this 229 * list does not permit null elements 230 * @throws IllegalArgumentException if some property of this element 231 * prevents it from being added to this list 232 */ 233 boolean add(E e); 234 235 /** 236 * Removes the first occurrence of the specified element from this list, 237 * if it is present (optional operation). If this list does not contain 238 * the element, it is unchanged. More formally, removes the element with 239 * the lowest index <tt>i</tt> such that 240 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> 241 * (if such an element exists). Returns <tt>true</tt> if this list 242 * contained the specified element (or equivalently, if this list changed 243 * as a result of the call). 244 * 245 * @param o element to be removed from this list, if present 246 * @return <tt>true</tt> if this list contained the specified element 247 * @throws ClassCastException if the type of the specified element 248 * is incompatible with this list (optional) 249 * @throws NullPointerException if the specified element is null and this 250 * list does not permit null elements (optional) 251 * @throws UnsupportedOperationException if the <tt>remove</tt> operation 252 * is not supported by this list 253 */ 254 boolean remove(Object o); 255 256 257 // Bulk Modification Operations 258 259 /** 260 * Returns <tt>true</tt> if this list contains all of the elements of the 261 * specified collection. 262 * 263 * @param c collection to be checked for containment in this list 264 * @return <tt>true</tt> if this list contains all of the elements of the 265 * specified collection 266 * @throws ClassCastException if the types of one or more elements 267 * in the specified collection are incompatible with this 268 * list (optional) 269 * @throws NullPointerException if the specified collection contains one 270 * or more null elements and this list does not permit null 271 * elements (optional), or if the specified collection is null 272 * @see #contains(Object) 273 */ 274 boolean containsAll(Collection<?> c); 275 276 /** 277 * Appends all of the elements in the specified collection to the end of 278 * this list, in the order that they are returned by the specified 279 * collection's iterator (optional operation). The behavior of this 280 * operation is undefined if the specified collection is modified while 281 * the operation is in progress. (Note that this will occur if the 282 * specified collection is this list, and it's nonempty.) 283 * 284 * @param c collection containing elements to be added to this list 285 * @return <tt>true</tt> if this list changed as a result of the call 286 * @throws UnsupportedOperationException if the <tt>addAll</tt> operation 287 * is not supported by this list 288 * @throws ClassCastException if the class of an element of the specified 289 * collection prevents it from being added to this list 290 * @throws NullPointerException if the specified collection contains one 291 * or more null elements and this list does not permit null 292 * elements, or if the specified collection is null 293 * @throws IllegalArgumentException if some property of an element of the 294 * specified collection prevents it from being added to this list 295 * @see #add(Object) 296 */ 297 boolean addAll(Collection<? extends E> c); 298 299 /** 300 * Inserts all of the elements in the specified collection into this 301 * list at the specified position (optional operation). Shifts the 302 * element currently at that position (if any) and any subsequent 303 * elements to the right (increases their indices). The new elements 304 * will appear in this list in the order that they are returned by the 305 * specified collection's iterator. The behavior of this operation is 306 * undefined if the specified collection is modified while the 307 * operation is in progress. (Note that this will occur if the specified 308 * collection is this list, and it's nonempty.) 309 * 310 * @param index index at which to insert the first element from the 311 * specified collection 312 * @param c collection containing elements to be added to this list 313 * @return <tt>true</tt> if this list changed as a result of the call 314 * @throws UnsupportedOperationException if the <tt>addAll</tt> operation 315 * is not supported by this list 316 * @throws ClassCastException if the class of an element of the specified 317 * collection prevents it from being added to this list 318 * @throws NullPointerException if the specified collection contains one 319 * or more null elements and this list does not permit null 320 * elements, or if the specified collection is null 321 * @throws IllegalArgumentException if some property of an element of the 322 * specified collection prevents it from being added to this list 323 * @throws IndexOutOfBoundsException if the index is out of range 324 * (<tt>index < 0 || index > size()</tt>) 325 */ 326 boolean addAll(int index, Collection<? extends E> c); 327 328 /** 329 * Removes from this list all of its elements that are contained in the 330 * specified collection (optional operation). 331 * 332 * @param c collection containing elements to be removed from this list 333 * @return <tt>true</tt> if this list changed as a result of the call 334 * @throws UnsupportedOperationException if the <tt>removeAll</tt> operation 335 * is not supported by this list 336 * @throws ClassCastException if the class of an element of this list 337 * is incompatible with the specified collection (optional) 338 * @throws NullPointerException if this list contains a null element and the 339 * specified collection does not permit null elements (optional), 340 * or if the specified collection is null 341 * @see #remove(Object) 342 * @see #contains(Object) 343 */ 344 boolean removeAll(Collection<?> c); 345 346 /** 347 * Retains only the elements in this list that are contained in the 348 * specified collection (optional operation). In other words, removes 349 * from this list all of its elements that are not contained in the 350 * specified collection. 351 * 352 * @param c collection containing elements to be retained in this list 353 * @return <tt>true</tt> if this list changed as a result of the call 354 * @throws UnsupportedOperationException if the <tt>retainAll</tt> operation 355 * is not supported by this list 356 * @throws ClassCastException if the class of an element of this list 357 * is incompatible with the specified collection (optional) 358 * @throws NullPointerException if this list contains a null element and the 359 * specified collection does not permit null elements (optional), 360 * or if the specified collection is null 361 * @see #remove(Object) 362 * @see #contains(Object) 363 */ 364 boolean retainAll(Collection<?> c); 365 366 /** 367 * Removes all of the elements from this list (optional operation). 368 * The list will be empty after this call returns. 369 * 370 * @throws UnsupportedOperationException if the <tt>clear</tt> operation 371 * is not supported by this list 372 */ 373 void clear(); 374 375 376 // Comparison and hashing 377 378 /** 379 * Compares the specified object with this list for equality. Returns 380 * <tt>true</tt> if and only if the specified object is also a list, both 381 * lists have the same size, and all corresponding pairs of elements in 382 * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and 383 * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null : 384 * e1.equals(e2))</tt>.) In other words, two lists are defined to be 385 * equal if they contain the same elements in the same order. This 386 * definition ensures that the equals method works properly across 387 * different implementations of the <tt>List</tt> interface. 388 * 389 * @param o the object to be compared for equality with this list 390 * @return <tt>true</tt> if the specified object is equal to this list 391 */ 392 boolean equals(Object o); 393 394 /** 395 * Returns the hash code value for this list. The hash code of a list 396 * is defined to be the result of the following calculation: 397 * <pre> 398 * int hashCode = 1; 399 * for (E e : list) 400 * hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); 401 * </pre> 402 * This ensures that <tt>list1.equals(list2)</tt> implies that 403 * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists, 404 * <tt>list1</tt> and <tt>list2</tt>, as required by the general 405 * contract of {@link Object#hashCode}. 406 * 407 * @return the hash code value for this list 408 * @see Object#equals(Object) 409 * @see #equals(Object) 410 */ 411 int hashCode(); 412 413 414 // Positional Access Operations 415 416 /** 417 * Returns the element at the specified position in this list. 418 * 419 * @param index index of the element to return 420 * @return the element at the specified position in this list 421 * @throws IndexOutOfBoundsException if the index is out of range 422 * (<tt>index < 0 || index >= size()</tt>) 423 */ 424 E get(int index); 425 426 /** 427 * Replaces the element at the specified position in this list with the 428 * specified element (optional operation). 429 * 430 * @param index index of the element to replace 431 * @param element element to be stored at the specified position 432 * @return the element previously at the specified position 433 * @throws UnsupportedOperationException if the <tt>set</tt> operation 434 * is not supported by this list 435 * @throws ClassCastException if the class of the specified element 436 * prevents it from being added to this list 437 * @throws NullPointerException if the specified element is null and 438 * this list does not permit null elements 439 * @throws IllegalArgumentException if some property of the specified 440 * element prevents it from being added to this list 441 * @throws IndexOutOfBoundsException if the index is out of range 442 * (<tt>index < 0 || index >= size()</tt>) 443 */ 444 E set(int index, E element); 445 446 /** 447 * Inserts the specified element at the specified position in this list 448 * (optional operation). Shifts the element currently at that position 449 * (if any) and any subsequent elements to the right (adds one to their 450 * indices). 451 * 452 * @param index index at which the specified element is to be inserted 453 * @param element element to be inserted 454 * @throws UnsupportedOperationException if the <tt>add</tt> operation 455 * is not supported by this list 456 * @throws ClassCastException if the class of the specified element 457 * prevents it from being added to this list 458 * @throws NullPointerException if the specified element is null and 459 * this list does not permit null elements 460 * @throws IllegalArgumentException if some property of the specified 461 * element prevents it from being added to this list 462 * @throws IndexOutOfBoundsException if the index is out of range 463 * (<tt>index < 0 || index > size()</tt>) 464 */ 465 void add(int index, E element); 466 467 /** 468 * Removes the element at the specified position in this list (optional 469 * operation). Shifts any subsequent elements to the left (subtracts one 470 * from their indices). Returns the element that was removed from the 471 * list. 472 * 473 * @param index the index of the element to be removed 474 * @return the element previously at the specified position 475 * @throws UnsupportedOperationException if the <tt>remove</tt> operation 476 * is not supported by this list 477 * @throws IndexOutOfBoundsException if the index is out of range 478 * (<tt>index < 0 || index >= size()</tt>) 479 */ 480 E remove(int index); 481 482 483 // Search Operations 484 485 /** 486 * Returns the index of the first occurrence of the specified element 487 * in this list, or -1 if this list does not contain the element. 488 * More formally, returns the lowest index <tt>i</tt> such that 489 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 490 * or -1 if there is no such index. 491 * 492 * @param o element to search for 493 * @return the index of the first occurrence of the specified element in 494 * this list, or -1 if this list does not contain the element 495 * @throws ClassCastException if the type of the specified element 496 * is incompatible with this list (optional) 497 * @throws NullPointerException if the specified element is null and this 498 * list does not permit null elements (optional) 499 */ 500 int indexOf(Object o); 501 502 /** 503 * Returns the index of the last occurrence of the specified element 504 * in this list, or -1 if this list does not contain the element. 505 * More formally, returns the highest index <tt>i</tt> such that 506 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 507 * or -1 if there is no such index. 508 * 509 * @param o element to search for 510 * @return the index of the last occurrence of the specified element in 511 * this list, or -1 if this list does not contain the element 512 * @throws ClassCastException if the type of the specified element 513 * is incompatible with this list (optional) 514 * @throws NullPointerException if the specified element is null and this 515 * list does not permit null elements (optional) 516 */ 517 int lastIndexOf(Object o); 518 519 520 // List Iterators 521 522 /** 523 * Returns a list iterator over the elements in this list (in proper 524 * sequence). 525 * 526 * @return a list iterator over the elements in this list (in proper 527 * sequence) 528 */ 529 ListIterator<E> listIterator(); 530 531 /** 532 * Returns a list iterator over the elements in this list (in proper 533 * sequence), starting at the specified position in the list. 534 * The specified index indicates the first element that would be 535 * returned by an initial call to {@link ListIterator#next next}. 536 * An initial call to {@link ListIterator#previous previous} would 537 * return the element with the specified index minus one. 538 * 539 * @param index index of the first element to be returned from the 540 * list iterator (by a call to {@link ListIterator#next next}) 541 * @return a list iterator over the elements in this list (in proper 542 * sequence), starting at the specified position in the list 543 * @throws IndexOutOfBoundsException if the index is out of range 544 * ({@code index < 0 || index > size()}) 545 */ 546 ListIterator<E> listIterator(int index); 547 548 // View 549 550 /** 551 * Returns a view of the portion of this list between the specified 552 * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive. (If 553 * <tt>fromIndex</tt> and <tt>toIndex</tt> are equal, the returned list is 554 * empty.) The returned list is backed by this list, so non-structural 555 * changes in the returned list are reflected in this list, and vice-versa. 556 * The returned list supports all of the optional list operations supported 557 * by this list.<p> 558 * 559 * This method eliminates the need for explicit range operations (of 560 * the sort that commonly exist for arrays). Any operation that expects 561 * a list can be used as a range operation by passing a subList view 562 * instead of a whole list. For example, the following idiom 563 * removes a range of elements from a list: 564 * <pre> 565 * list.subList(from, to).clear(); 566 * </pre> 567 * Similar idioms may be constructed for <tt>indexOf</tt> and 568 * <tt>lastIndexOf</tt>, and all of the algorithms in the 569 * <tt>Collections</tt> class can be applied to a subList.<p> 570 * 571 * The semantics of the list returned by this method become undefined if 572 * the backing list (i.e., this list) is <i>structurally modified</i> in 573 * any way other than via the returned list. (Structural modifications are 574 * those that change the size of this list, or otherwise perturb it in such 575 * a fashion that iterations in progress may yield incorrect results.) 576 * 577 * @param fromIndex low endpoint (inclusive) of the subList 578 * @param toIndex high endpoint (exclusive) of the subList 579 * @return a view of the specified range within this list 580 * @throws IndexOutOfBoundsException for an illegal endpoint index value 581 * (<tt>fromIndex < 0 || toIndex > size || 582 * fromIndex > toIndex</tt>) 583 */ 584 List<E> subList(int fromIndex, int toIndex); 585 }