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