{"id":1199,"date":"2022-10-26T23:03:07","date_gmt":"2022-10-26T15:03:07","guid":{"rendered":"https:\/\/qaqaq.top\/?p=1199"},"modified":"2022-11-27T12:39:48","modified_gmt":"2022-11-27T04:39:48","slug":"%e9%9b%86%e5%90%88-list%e6%8e%a5%e5%8f%a3%e5%b8%b8%e7%94%a8%e5%ae%9e%e7%8e%b0%e7%b1%bb%e7%9a%84%e5%af%b9%e6%af%94%e3%80%81arraylist%e7%9a%84%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90%e3%80%81linkedlist","status":"publish","type":"post","link":"https:\/\/qaqaq.top\/?p=1199","title":{"rendered":"\u96c6\u5408-List\u63a5\u53e3\u5e38\u7528\u5b9e\u73b0\u7c7b\u7684\u5bf9\u6bd4\u3001ArrayList\u7684\u6e90\u7801\u5206\u6790\u3001LinkedList\u7684\u6e90\u7801\u5206\u6790\u3001Vector\u7684\u6e90\u7801\u5206\u6790\u3001List\u63a5\u53e3\u4e2d\u7684\u5e38\u7528\u65b9\u6cd5\u6d4b\u8bd5\u3001List\u904d\u5386\u53ca\u65b9\u6cd5\u603b\u7ed3"},"content":{"rendered":"\n
package top.qaqaq.java.P528;\r\n\r\nimport org.junit.jupiter.api.Test;\r\n\r\nimport java.util.ArrayList;\r\nimport java.util.Arrays;\r\nimport java.util.Iterator;\r\nimport java.util.List;\r\n\r\n\/**\r\n * 1. List\u63a5\u53e3\u6846\u67b6\r\n *\r\n *      |----Collection\u63a5\u53e3\uff1a\u5355\u5217\u96c6\u5408\uff0c\u7528\u6765\u5b58\u50a8\u4e00\u4e2a\u4e00\u4e2a\u7684\u5bf9\u8c61\r\n *          |----List\u63a5\u53e3:\u5b58\u50a8\u6709\u5e8f\u7684\u3001\u53ef\u91cd\u590d\u7684\u6570\u636e\u3002  -->\"\u52a8\u6001\"\u6570\u7ec4,\u66ff\u6362\u539f\u6709\u7684\u6570\u7ec4\r\n *                  |----ArrayList\uff1a\u4f5c\u4e3aList\u63a5\u53e3\u7684\u4e3b\u8981\u5b9e\u73b0\u7c7b\uff1b\u7ebf\u7a0b\u4e0d\u5b89\u5168\u7684\uff0c\u6548\u7387\u9ad8\uff1b\u5e95\u5c42\u4f7f\u7528Object[] elementData\u5b58\u50a8\r\n *                  |----LinkedList\uff1a\u5bf9\u4e8e\u9891\u7e41\u7684\u63d2\u5165\u3001\u5220\u9664\u64cd\u4f5c\uff0c\u4f7f\u7528\u6b64\u7c7b\u6548\u7387\u6bd4ArrayList\u9ad8\uff1b\u5e95\u5c42\u4f7f\u7528\u53cc\u5411\u94fe\u8868\u5b58\u50a8\r\n *                  |----Vector\uff1a\u4f5c\u4e3aList\u63a5\u53e3\u7684\u53e4\u8001\u5b9e\u73b0\u7c7b\uff1b\u7ebf\u7a0b\u5b89\u5168\u7684\uff0c\u6548\u7387\u4f4e\uff1b\u5e95\u5c42\u4f7f\u7528Object[] elementData\u5b58\u50a8\r\n *\r\n * 2. ArrayList\u7684\u6e90\u7801\u5206\u6790\uff1a\r\n * 2.1  jdk 7\u60c5\u51b5\u4e0b\r\n *      Arraylist list = new ArrayList();\/\/\u5e95\u5c42\u521b\u5efa\u4e86\u957f\u5ea6\u662f10\u7684Objece[]\u6570\u7ec4elementData\r\n *      list.add(123);\/\/elementDate[0] = new Integer(123);\r\n *      ...\r\n *      list.add(11);\/\/\u5982\u679c\u6b64\u6b21\u7684\u6dfb\u52a0\u5bfc\u81f4\u5e95\u5c42elementDate\u6570\u7ec4\u5bb9\u91cf\u4e0d\u591f\uff0c\u5219\u6269\u5bb9\u3002\r\n *      \u9ed8\u8ba4\u60c5\u51b5\u4e0b\uff0c\u6269\u5bb9\u4e3a\u539f\u6765\u7684\u5bb9\u91cf\u76841.5\u500d\uff0c\u540c\u65f6\u9700\u8981\u5c06\u539f\u6709\u6570\u7ec4\u4e2d\u7684\u6570\u636e\u590d\u5236\u5230\u65b0\u7684\u6570\u7ec4\u4e2d\u3002\r\n *\r\n *      \u7ed3\u8bba\uff1a\u5efa\u8bae\u5f00\u53d1\u4e2d\u4f7f\u7528\u5e26\u53c2\u7684\u6784\u9020\u5668\uff1aArrayList list = new ArrayList(int capacity)\r\n *\r\n *      jdk 8\u4e2dArrayList\u7684\u53d8\u5316\uff1a\r\n *       Arraylist list = new ArrayList();\/\/\u5e95\u5c42Object[] elementDatac\u521d\u59cb\u5316\u4e3a{}.\u5e76\u6ca1\u6709\u521b\u5efa\u957f\u5ea6\u4e3a10\u7684\u6570\u7ec4\r\n *\r\n *       list.add(123);\/\/\u7b2c\u4e00\u6b21\u8c03\u7528add()\u65f6\uff0c\u5e95\u5c42\u624d\u521b\u5efa\u4e86\u957f\u5ea610\u7684\u6570\u7ec4\uff0c\u5e76\u5c06\u6570\u636e123\u6dfb\u52a0\u5230elementDate[0]\r\n *       ...\r\n *       \u540e\u7eed\u7684\u6dfb\u52a0\u548c\u6269\u5bb9\u64cd\u4f5c\u4e0ejdk 7\u65e0\u5f02\u3002\r\n * 2.3 \u5c0f\u7ed3\uff1ajdk7\u4e2d\u7684ArrayList\u7684\u5bf9\u8c61\u7684\u521b\u5efa\u7c7b\u4f3c\u4e8e\u5355\u4f8b\u7684\u997f\u6c49\u5f0f\uff0c\u800cjdk8\u4e2d\u7684ArrayList\u7684\u5bf9\u8c61\r\n *          \u7684\u521b\u5efa\u7c7b\u4f3c\u4e8e\u5355\u4f8b\u7684\u61d2\u6c49\u5f0f\uff0c\u5ef6\u8fdf\u4e86\u6570\u7ec4\u7684\u521b\u5efa\uff0c\u8282\u7701\u5185\u5b58\u3002\r\n * 3. LinkedList\u7684\u6e90\u7801\u5206\u6790\uff1a\r\n *       LinkedList list = new LinkedList(); \u5185\u90e8\u58f0\u660e\u4e86Node\u7c7b\u578b\u7684first\u548clast\u5c5e\u6027\uff0c\u9ed8\u8ba4\u503c\u4e3anull\r\n *       List.add(123);\/\/\u5c06123\u5c01\u88c5\u5230Node\u4e2d\uff0c\u521b\u5efa\u4e86Node\u5bf9\u8c61\u3002\r\n *\r\n *       \u5176\u4e2d\uff0cNode\u5b9a\u4e49\u4e3a\uff1a\u4f53\u73b0\u4e86LinkedList\u7684\u53cc\u5411\u94fe\u8868\u7684\u8bf4\u6cd5\r\n     *       private static class Node<E> {\r\n     *         E item;\r\n     *         Node<E> next;\r\n     *         Node<E> prev;\r\n     *\r\n     *         Node(Node<E> prev, E element, Node<E> next) {\r\n     *             this.item = element;\r\n     *             this.next = next;\r\n     *             this.prev = prev;\r\n     *         }\r\n     *     }\r\n *\r\n * 4. Vector\u7684\u6e90\u7801\u5206\u6790\uff1ajdk7\u548cjdk8\u4e2d\u901a\u8fc7Vector()\u6784\u9020\u5668\u521b\u5efa\u5bf9\u8c61\u65f6\uff0c\u5e95\u5c42\u90fd\u521b\u5efa\u4e86\u957f\u5ea6\u4e3a10\u7684\u6570\u7ec4\u3002\r\n *      \u5728\u6269\u5bb9\u65b9\u9762\uff0c\u9ed8\u8ba4\u6269\u5bb9\u4e3a\u539f\u6765\u7684\u6570\u7ec4\u957f\u5ea6\u76842\u500d\u3002\r\n *\r\n * \u9762\u8bd5\u9898\uff1aArrayList\u3001LinkedList\u3001Vector\u4e09\u8005\u7684\u5f02\u540c\uff1f\r\n * \u540c\uff1a\u4e09\u4e2a\u7c7b\u90fd\u662f\u5b9e\u73b0\u4e86List\u63a5\u53e3\uff0c\u5b58\u50a8\u6570\u636e\u7684\u7279\u70b9\u76f8\u540c\uff1a\u5b58\u50a8\u6709\u5e8f\u7684\u3001\u53ef\u91cd\u590d\u7684\u6570\u636e\r\n *\r\n * \u4e0d\u540c\uff1a\u89c1\u4e0a\r\n *\r\n *\r\n * 5. List\u63a5\u53e3\u4e2d\u7684\u5e38\u7528\u65b9\u6cd5\r\n *\r\n * @author RichieZhang\r\n * @create 2022-10-26 \u4e0b\u5348 1:05\r\n *\/\r\npublic class ListTest {\r\n\r\n    \/*\r\n    \uf0d8void add(int index, Object ele):\u5728index\u4f4d\u7f6e\u63d2\u5165ele\u5143\u7d20\r\n    \uf0d8boolean addAll(int index, Collection eles):\u4eceindex\u4f4d\u7f6e\u5f00\u59cb\u5c06eles\u4e2d\u7684\u6240\u6709\u5143\u7d20\u6dfb\u52a0\u8fdb\u6765\r\n    \uf0d8Object get(int index):\u83b7\u53d6\u6307\u5b9aindex\u4f4d\u7f6e\u7684\u5143\u7d20\r\n    \uf0d8int indexOf(Object obj):\u8fd4\u56deobj\u5728\u96c6\u5408\u4e2d\u9996\u6b21\u51fa\u73b0\u7684\u4f4d\u7f6e\r\n    \uf0d8int lastIndexOf(Object obj):\u8fd4\u56deobj\u5728\u5f53\u524d\u96c6\u5408\u4e2d\u672b\u6b21\u51fa\u73b0\u7684\u4f4d\u7f6e\r\n    \uf0d8Object remove(int index):\u79fb\u9664\u6307\u5b9aindex\u4f4d\u7f6e\u7684\u5143\u7d20\uff0c\u5e76\u8fd4\u56de\u6b64\u5143\u7d20\r\n    \uf0d8Object set(int index, Object ele):\u8bbe\u7f6e\u6307\u5b9aindex\u4f4d\u7f6e\u7684\u5143\u7d20\u4e3aele\r\n    \uf0d8List subList(int fromIndex, int toIndex):\u8fd4\u56de\u4ecefromIndex\u5230toIndex\u4f4d\u7f6e\u7684\u5b50\u96c6\u5408\r\n\r\n    \u603b\u7ed3\uff1a\u5e38\u7528\u65b9\u6cd5\r\n    \u589e\uff1aadd(Object obj);\r\n    \u5220\uff1aremove(int index) \/ remove(Object obj)\r\n    \u6539\uff1aset(int index, Object ele)\r\n    \u67e5\uff1aget(int index)\r\n    \u63d2\uff1aadd(int index, Object ele)\r\n    \u957f\u5ea6\uff1asize()\r\n    \u904d\u5386\uff1a\u2460 Iterator\u8fed\u4ee3\u5668\u65b9\u5f0f\r\n         \u2461  \u589e\u5f3afor\u5faa\u73af\r\n         \u2462  \u666e\u901a\u7684\u5faa\u73af\r\n\r\n     *\/\r\n    @Test\r\n    public void test3(){\r\n        ArrayList list = new ArrayList();\r\n        list.add(123);\r\n        list.add(456);\r\n        list.add(\"AA\");\r\n\r\n        \/\/\u65b9\u5f0f\u4e00\uff1aIterator\u8fed\u4ee3\u5668\u65b9\u5f0f\r\n        Iterator iterator = list.iterator();\r\n        while (iterator.hasNext()){\r\n            System.out.println(iterator.next());\r\n        }\r\n\r\n        System.out.println(\"************************\");\r\n\r\n        \/\/\u65b9\u5f0f\u4e8c\uff1a\u589e\u5f3afor\u5faa\u73af\r\n        for (Object obj : list){\r\n            System.out.println(obj);\r\n        }\r\n\r\n        System.out.println(\"************************\");\r\n        \r\n        \/\/\u65b9\u5f0f\u4e09\uff1a\u666e\u901afor\u5faa\u73af\r\n        for (int i = 0; i < list.size(); i++) {\r\n            System.out.println(list.get(i));\r\n        }\r\n\r\n    }\r\n\r\n    @Test\r\n    public void test2(){\r\n        ArrayList list = new ArrayList();\r\n        list.add(123);\r\n        list.add(456);\r\n        list.add(\"AA\");\r\n        list.add(new Person(\"Tom\",12));\r\n        list.add(456);\r\n\r\n        \/\/int indexOf(Object obj):\u8fd4\u56deobj\u5728\u96c6\u5408\u4e2d\u9996\u6b21\u51fa\u73b0\u7684\u4f4d\u7f6e\u3002\u5982\u679c\u4e0d\u5b58\u5728\uff0c\u8fd4\u56de-1.\r\n        int index = list.indexOf(4567);\r\n        System.out.println(index);\r\n\r\n        \/\/int lastIndexOf(Object obj):\u8fd4\u56deobj\u5728\u5f53\u524d\u96c6\u5408\u4e2d\u672b\u6b21\u51fa\u73b0\u7684\u4f4d\u7f6e\r\n        System.out.println(list.lastIndexOf(456));\r\n\r\n        \/\/Object remove(int index):\u79fb\u9664\u6307\u5b9aindex\u4f4d\u7f6e\u7684\u5143\u7d20\uff0c\u5e76\u8fd4\u56de\u6b64\u5143\u7d20\r\n        Object obj = list.remove(0);\r\n        System.out.println(obj);\r\n        System.out.println(list);\r\n\r\n        \/\/Object set(int index, Object ele):\u8bbe\u7f6e\u6307\u5b9aindex\u4f4d\u7f6e\u7684\u5143\u7d20\u4e3aele\r\n        list.set(1,\"CC\");\r\n        System.out.println(list);\r\n\r\n        \/\/List subList(int fromIndex, int toIndex):\u8fd4\u56de\u4ecefromIndex\u5230toIndex\u4f4d\u7f6e\u7684\u5de6\u95ed\u53f3\u5f00\u533a\u95f4\u7684\u5b50\u96c6\u5408\r\n        List subList = list.subList(2, 4);\r\n        System.out.println(subList);\r\n        System.out.println(list);\r\n\r\n    }\r\n\r\n    @Test\r\n    public void test1(){\r\n        ArrayList list = new ArrayList();\r\n        list.add(123);\r\n        list.add(456);\r\n        list.add(\"AA\");\r\n        list.add(new Person(\"Tom\",12));\r\n        list.add(456);\r\n\r\n        System.out.println(list);\r\n\r\n        \/\/void add(int index, Object ele):\u5728index\u4f4d\u7f6e\u63d2\u5165ele\u5143\u7d20\r\n        list.add(1,\"BB\");\r\n        System.out.println(list);\r\n\r\n        \/\/boolean addAll(int index, Collection eles):\u4eceindex\u4f4d\u7f6e\u5f00\u59cb\u5c06eles\u4e2d\u7684\u6240\u6709\u5143\u7d20\u6dfb\u52a0\u8fdb\u6765\r\n        List list1 = Arrays.asList(1, 2, 3);\r\n        list.addAll(list1);\r\n\/\/        list.add(list1);\r\n        System.out.println(list.size());\/\/9\r\n\r\n        \/\/Object get(int index):\u83b7\u53d6\u6307\u5b9aindex\u4f4d\u7f6e\u7684\u5143\u7d20\r\n        System.out.println(list.get(0));\r\n\r\n\r\n    }\r\n}\r\n<\/code><\/pre>\n\n\n\n
package top.qaqaq.java.P528;\r\n\r\n\/**\r\n * @author RichieZhang\r\n * @create 2022-10-25 \u4e0b\u5348 9:48\r\n *\/\r\npublic class Person {\r\n\r\n    private String name;\r\n    private int age;\r\n\r\n    public Person() {\r\n    }\r\n\r\n    public Person(String name, int age) {\r\n        this.name = name;\r\n        this.age = age;\r\n    }\r\n\r\n    public String getName() {\r\n        return name;\r\n    }\r\n\r\n    public void setName(String name) {\r\n        this.name = name;\r\n    }\r\n\r\n    public int getAge() {\r\n        return age;\r\n    }\r\n\r\n    public void setAge(int age) {\r\n        this.age = age;\r\n    }\r\n\r\n    @Override\r\n    public String toString() {\r\n        return \"Person{\" +\r\n                \"name='\" + name + '\\'' +\r\n                \", age=\" + age +\r\n                '}';\r\n    }\r\n\r\n    @Override\r\n    public boolean equals(Object o) {\r\n        System.out.println(\"Person equals().....\");\r\n        if (this == o) return true;\r\n        if (o == null || getClass() != o.getClass()) return false;\r\n\r\n        Person person = (Person) o;\r\n\r\n        if (age != person.age) return false;\r\n        return name != null ? name.equals(person.name) : person.name == null;\r\n    }\r\n\r\n}\r\n<\/code><\/pre>\n\n\n\n
jdk 7 ArrayList\u6e90\u7801<\/p>\n\n\n\n
\/*\r\n * Copyright (c) 1997, 2010, Oracle and\/or its affiliates. All rights reserved.\r\n * ORACLE PROPRIETARY\/CONFIDENTIAL. Use is subject to license terms.\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\/\r\n\r\npackage top.qaqaq.java.P528.src7;\r\n\r\nimport java.util.*;\r\n\r\n\/**\r\n * Resizable-array implementation of the <tt>List<\/tt> interface.  Implements\r\n * all optional list operations, and permits all elements, including\r\n * <tt>null<\/tt>.  In addition to implementing the <tt>List<\/tt> interface,\r\n * this class provides methods to manipulate the size of the array that is\r\n * used internally to store the list.  (This class is roughly equivalent to\r\n * <tt>Vector<\/tt>, except that it is unsynchronized.)\r\n *\r\n * <p>The <tt>size<\/tt>, <tt>isEmpty<\/tt>, <tt>get<\/tt>, <tt>set<\/tt>,\r\n * <tt>iterator<\/tt>, and <tt>listIterator<\/tt> operations run in constant\r\n * time.  The <tt>add<\/tt> operation runs in <i>amortized constant time<\/i>,\r\n * that is, adding n elements requires O(n) time.  All of the other operations\r\n * run in linear time (roughly speaking).  The constant factor is low compared\r\n * to that for the <tt>LinkedList<\/tt> implementation.\r\n *\r\n * <p>Each <tt>ArrayList<\/tt> instance has a <i>capacity<\/i>.  The capacity is\r\n * the size of the array used to store the elements in the list.  It is always\r\n * at least as large as the list size.  As elements are added to an ArrayList,\r\n * its capacity grows automatically.  The details of the growth policy are not\r\n * specified beyond the fact that adding an element has constant amortized\r\n * time cost.\r\n *\r\n * <p>An application can increase the capacity of an <tt>ArrayList<\/tt> instance\r\n * before adding a large number of elements using the <tt>ensureCapacity<\/tt>\r\n * operation.  This may reduce the amount of incremental reallocation.\r\n *\r\n * <p><strong>Note that this implementation is not synchronized.<\/strong>\r\n * If multiple threads access an <tt>ArrayList<\/tt> instance concurrently,\r\n * and at least one of the threads modifies the list structurally, it\r\n * <i>must<\/i> be synchronized externally.  (A structural modification is\r\n * any operation that adds or deletes one or more elements, or explicitly\r\n * resizes the backing array; merely setting the value of an element is not\r\n * a structural modification.)  This is typically accomplished by\r\n * synchronizing on some object that naturally encapsulates the list.\r\n *\r\n * If no such object exists, the list should be \"wrapped\" using the\r\n * {@link Collections#synchronizedList Collections.synchronizedList}\r\n * method.  This is best done at creation time, to prevent accidental\r\n * unsynchronized access to the list:<pre>\r\n *   List list = Collections.synchronizedList(new ArrayList(...));<\/pre>\r\n *\r\n * <p><a name=\"fail-fast\"\/>\r\n * The iterators returned by this class's {@link #iterator() iterator} and\r\n * {@link #listIterator(int) listIterator} methods are <em>fail-fast<\/em>:\r\n * if the list is structurally modified at any time after the iterator is\r\n * created, in any way except through the iterator's own\r\n * {@link ListIterator#remove() remove} or\r\n * {@link ListIterator#add(Object) add} methods, the iterator will throw a\r\n * {@link ConcurrentModificationException}.  Thus, in the face of\r\n * concurrent modification, the iterator fails quickly and cleanly, rather\r\n * than risking arbitrary, non-deterministic behavior at an undetermined\r\n * time in the future.\r\n *\r\n * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed\r\n * as it is, generally speaking, impossible to make any hard guarantees in the\r\n * presence of unsynchronized concurrent modification.  Fail-fast iterators\r\n * throw {@code ConcurrentModificationException} on a best-effort basis.\r\n * Therefore, it would be wrong to write a program that depended on this\r\n * exception for its correctness:  <i>the fail-fast behavior of iterators\r\n * should be used only to detect bugs.<\/i>\r\n *\r\n * <p>This class is a member of the\r\n * <a href=\"{@docRoot}\/..\/technotes\/guides\/collections\/index.html\">\r\n * Java Collections Framework<\/a>.\r\n *\r\n * @author  Josh Bloch\r\n * @author  Neal Gafter\r\n * @see     Collection\r\n * @see     List\r\n * @see     LinkedList\r\n * @see     Vector\r\n * @since   1.2\r\n *\/\r\n\r\npublic class ArrayList<E> extends AbstractList<E>\r\n        implements List<E>, RandomAccess, Cloneable, java.io.Serializable\r\n{\r\n    private static final long serialVersionUID = 8683452581122892189L;\r\n\r\n    \/**\r\n     * The array buffer into which the elements of the ArrayList are stored.\r\n     * The capacity of the ArrayList is the length of this array buffer.\r\n     *\/\r\n    private transient Object[] elementData;\r\n\r\n    \/**\r\n     * The size of the ArrayList (the number of elements it contains).\r\n     *\r\n     * @serial\r\n     *\/\r\n    private int size;\r\n\r\n    \/**\r\n     * Constructs an empty list with the specified initial capacity.\r\n     *\r\n     * @param  initialCapacity  the initial capacity of the list\r\n     * @throws IllegalArgumentException if the specified initial capacity\r\n     *         is negative\r\n     *\/\r\n    public ArrayList(int initialCapacity) {\r\n        super();\r\n        if (initialCapacity < 0)\r\n            throw new IllegalArgumentException(\"Illegal Capacity: \"+\r\n                                               initialCapacity);\r\n        this.elementData = new Object[initialCapacity];\r\n    }\r\n\r\n    \/**\r\n     * Constructs an empty list with an initial capacity of ten.\r\n     *\/\r\n    public ArrayList() {\r\n        this(10);\r\n    }\r\n\r\n    \/**\r\n     * Constructs a list containing the elements of the specified\r\n     * collection, in the order they are returned by the collection's\r\n     * iterator.\r\n     *\r\n     * @param c the collection whose elements are to be placed into this list\r\n     * @throws NullPointerException if the specified collection is null\r\n     *\/\r\n    public ArrayList(Collection<? extends E> c) {\r\n        elementData = c.toArray();\r\n        size = elementData.length;\r\n        \/\/ c.toArray might (incorrectly) not return Object[] (see 6260652)\r\n        if (elementData.getClass() != Object[].class)\r\n            elementData = Arrays.copyOf(elementData, size, Object[].class);\r\n    }\r\n\r\n    \/**\r\n     * Trims the capacity of this <tt>ArrayList<\/tt> instance to be the\r\n     * list's current size.  An application can use this operation to minimize\r\n     * the storage of an <tt>ArrayList<\/tt> instance.\r\n     *\/\r\n    public void trimToSize() {\r\n        modCount++;\r\n        int oldCapacity = elementData.length;\r\n        if (size < oldCapacity) {\r\n            elementData = Arrays.copyOf(elementData, size);\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Increases the capacity of this <tt>ArrayList<\/tt> instance, if\r\n     * necessary, to ensure that it can hold at least the number of elements\r\n     * specified by the minimum capacity argument.\r\n     *\r\n     * @param   minCapacity   the desired minimum capacity\r\n     *\/\r\n    public void ensureCapacity(int minCapacity) {\r\n        if (minCapacity > 0)\r\n            ensureCapacityInternal(minCapacity);\r\n    }\r\n\r\n    private void ensureCapacityInternal(int minCapacity) {\r\n        modCount++;\r\n        \/\/ overflow-conscious code\r\n        if (minCapacity - elementData.length > 0)\r\n            grow(minCapacity);\r\n    }\r\n\r\n    \/**\r\n     * The maximum size of array to allocate.\r\n     * Some VMs reserve some header words in an array.\r\n     * Attempts to allocate larger arrays may result in\r\n     * OutOfMemoryError: Requested array size exceeds VM limit\r\n     *\/\r\n    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;\r\n\r\n    \/**\r\n     * Increases the capacity to ensure that it can hold at least the\r\n     * number of elements specified by the minimum capacity argument.\r\n     *\r\n     * @param minCapacity the desired minimum capacity\r\n     *\/\r\n    private void grow(int minCapacity) {\r\n        \/\/ overflow-conscious code\r\n        int oldCapacity = elementData.length;\r\n        int newCapacity = oldCapacity + (oldCapacity >> 1);\r\n        if (newCapacity - minCapacity < 0)\r\n            newCapacity = minCapacity;\r\n        if (newCapacity - MAX_ARRAY_SIZE > 0)\r\n            newCapacity = hugeCapacity(minCapacity);\r\n        \/\/ minCapacity is usually close to size, so this is a win:\r\n        elementData = Arrays.copyOf(elementData, newCapacity);\r\n    }\r\n\r\n    private static int hugeCapacity(int minCapacity) {\r\n        if (minCapacity < 0) \/\/ overflow\r\n            throw new OutOfMemoryError();\r\n        return (minCapacity > MAX_ARRAY_SIZE) ?\r\n            Integer.MAX_VALUE :\r\n            MAX_ARRAY_SIZE;\r\n    }\r\n\r\n    \/**\r\n     * Returns the number of elements in this list.\r\n     *\r\n     * @return the number of elements in this list\r\n     *\/\r\n    public int size() {\r\n        return size;\r\n    }\r\n\r\n    \/**\r\n     * Returns <tt>true<\/tt> if this list contains no elements.\r\n     *\r\n     * @return <tt>true<\/tt> if this list contains no elements\r\n     *\/\r\n    public boolean isEmpty() {\r\n        return size == 0;\r\n    }\r\n\r\n    \/**\r\n     * Returns <tt>true<\/tt> if this list contains the specified element.\r\n     * More formally, returns <tt>true<\/tt> if and only if this list contains\r\n     * at least one element <tt>e<\/tt> such that\r\n     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))<\/tt>.\r\n     *\r\n     * @param o element whose presence in this list is to be tested\r\n     * @return <tt>true<\/tt> if this list contains the specified element\r\n     *\/\r\n    public boolean contains(Object o) {\r\n        return indexOf(o) >= 0;\r\n    }\r\n\r\n    \/**\r\n     * Returns the index of the first occurrence of the specified element\r\n     * in this list, or -1 if this list does not contain the element.\r\n     * More formally, returns the lowest index <tt>i<\/tt> such that\r\n     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))<\/tt>,\r\n     * or -1 if there is no such index.\r\n     *\/\r\n    public int indexOf(Object o) {\r\n        if (o == null) {\r\n            for (int i = 0; i < size; i++)\r\n                if (elementData[i]==null)\r\n                    return i;\r\n        } else {\r\n            for (int i = 0; i < size; i++)\r\n                if (o.equals(elementData[i]))\r\n                    return i;\r\n        }\r\n        return -1;\r\n    }\r\n\r\n    \/**\r\n     * Returns the index of the last occurrence of the specified element\r\n     * in this list, or -1 if this list does not contain the element.\r\n     * More formally, returns the highest index <tt>i<\/tt> such that\r\n     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))<\/tt>,\r\n     * or -1 if there is no such index.\r\n     *\/\r\n    public int lastIndexOf(Object o) {\r\n        if (o == null) {\r\n            for (int i = size-1; i >= 0; i--)\r\n                if (elementData[i]==null)\r\n                    return i;\r\n        } else {\r\n            for (int i = size-1; i >= 0; i--)\r\n                if (o.equals(elementData[i]))\r\n                    return i;\r\n        }\r\n        return -1;\r\n    }\r\n\r\n    \/**\r\n     * Returns a shallow copy of this <tt>ArrayList<\/tt> instance.  (The\r\n     * elements themselves are not copied.)\r\n     *\r\n     * @return a clone of this <tt>ArrayList<\/tt> instance\r\n     *\/\r\n    public Object clone() {\r\n        try {\r\n            @SuppressWarnings(\"unchecked\")\r\n                ArrayList<E> v = (ArrayList<E>) super.clone();\r\n            v.elementData = Arrays.copyOf(elementData, size);\r\n            v.modCount = 0;\r\n            return v;\r\n        } catch (CloneNotSupportedException e) {\r\n            \/\/ this shouldn't happen, since we are Cloneable\r\n            throw new InternalError();\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Returns an array containing all of the elements in this list\r\n     * in proper sequence (from first to last element).\r\n     *\r\n     * <p>The returned array will be \"safe\" in that no references to it are\r\n     * maintained by this list.  (In other words, this method must allocate\r\n     * a new array).  The caller is thus free to modify the returned array.\r\n     *\r\n     * <p>This method acts as bridge between array-based and collection-based\r\n     * APIs.\r\n     *\r\n     * @return an array containing all of the elements in this list in\r\n     *         proper sequence\r\n     *\/\r\n    public Object[] toArray() {\r\n        return Arrays.copyOf(elementData, size);\r\n    }\r\n\r\n    \/**\r\n     * Returns an array containing all of the elements in this list in proper\r\n     * sequence (from first to last element); the runtime type of the returned\r\n     * array is that of the specified array.  If the list fits in the\r\n     * specified array, it is returned therein.  Otherwise, a new array is\r\n     * allocated with the runtime type of the specified array and the size of\r\n     * this list.\r\n     *\r\n     * <p>If the list fits in the specified array with room to spare\r\n     * (i.e., the array has more elements than the list), the element in\r\n     * the array immediately following the end of the collection is set to\r\n     * <tt>null<\/tt>.  (This is useful in determining the length of the\r\n     * list <i>only<\/i> if the caller knows that the list does not contain\r\n     * any null elements.)\r\n     *\r\n     * @param a the array into which the elements of the list are to\r\n     *          be stored, if it is big enough; otherwise, a new array of the\r\n     *          same runtime type is allocated for this purpose.\r\n     * @return an array containing the elements of the list\r\n     * @throws ArrayStoreException if the runtime type of the specified array\r\n     *         is not a supertype of the runtime type of every element in\r\n     *         this list\r\n     * @throws NullPointerException if the specified array is null\r\n     *\/\r\n    @SuppressWarnings(\"unchecked\")\r\n    public <T> T[] toArray(T[] a) {\r\n        if (a.length < size)\r\n            \/\/ Make a new array of a's runtime type, but my contents:\r\n            return (T[]) Arrays.copyOf(elementData, size, a.getClass());\r\n        System.arraycopy(elementData, 0, a, 0, size);\r\n        if (a.length > size)\r\n            a[size] = null;\r\n        return a;\r\n    }\r\n\r\n    \/\/ Positional Access Operations\r\n\r\n    @SuppressWarnings(\"unchecked\")\r\n    E elementData(int index) {\r\n        return (E) elementData[index];\r\n    }\r\n\r\n    \/**\r\n     * Returns the element at the specified position in this list.\r\n     *\r\n     * @param  index index of the element to return\r\n     * @return the element at the specified position in this list\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public E get(int index) {\r\n        rangeCheck(index);\r\n\r\n        return elementData(index);\r\n    }\r\n\r\n    \/**\r\n     * Replaces the element at the specified position in this list with\r\n     * the specified element.\r\n     *\r\n     * @param index index of the element to replace\r\n     * @param element element to be stored at the specified position\r\n     * @return the element previously at the specified position\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public E set(int index, E element) {\r\n        rangeCheck(index);\r\n\r\n        E oldValue = elementData(index);\r\n        elementData[index] = element;\r\n        return oldValue;\r\n    }\r\n\r\n    \/**\r\n     * Appends the specified element to the end of this list.\r\n     *\r\n     * @param e element to be appended to this list\r\n     * @return <tt>true<\/tt> (as specified by {@link Collection#add})\r\n     *\/\r\n    public boolean add(E e) {\r\n        ensureCapacityInternal(size + 1);  \/\/ Increments modCount!!\r\n        elementData[size++] = e;\r\n        return true;\r\n    }\r\n\r\n    \/**\r\n     * Inserts the specified element at the specified position in this\r\n     * list. Shifts the element currently at that position (if any) and\r\n     * any subsequent elements to the right (adds one to their indices).\r\n     *\r\n     * @param index index at which the specified element is to be inserted\r\n     * @param element element to be inserted\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public void add(int index, E element) {\r\n        rangeCheckForAdd(index);\r\n\r\n        ensureCapacityInternal(size + 1);  \/\/ Increments modCount!!\r\n        System.arraycopy(elementData, index, elementData, index + 1,\r\n                         size - index);\r\n        elementData[index] = element;\r\n        size++;\r\n    }\r\n\r\n    \/**\r\n     * Removes the element at the specified position in this list.\r\n     * Shifts any subsequent elements to the left (subtracts one from their\r\n     * indices).\r\n     *\r\n     * @param index the index of the element to be removed\r\n     * @return the element that was removed from the list\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public E remove(int index) {\r\n        rangeCheck(index);\r\n\r\n        modCount++;\r\n        E oldValue = elementData(index);\r\n\r\n        int numMoved = size - index - 1;\r\n        if (numMoved > 0)\r\n            System.arraycopy(elementData, index+1, elementData, index,\r\n                             numMoved);\r\n        elementData[--size] = null; \/\/ Let gc do its work\r\n\r\n        return oldValue;\r\n    }\r\n\r\n    \/**\r\n     * Removes the first occurrence of the specified element from this list,\r\n     * if it is present.  If the list does not contain the element, it is\r\n     * unchanged.  More formally, removes the element with the lowest index\r\n     * <tt>i<\/tt> such that\r\n     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))<\/tt>\r\n     * (if such an element exists).  Returns <tt>true<\/tt> if this list\r\n     * contained the specified element (or equivalently, if this list\r\n     * changed as a result of the call).\r\n     *\r\n     * @param o element to be removed from this list, if present\r\n     * @return <tt>true<\/tt> if this list contained the specified element\r\n     *\/\r\n    public boolean remove(Object o) {\r\n        if (o == null) {\r\n            for (int index = 0; index < size; index++)\r\n                if (elementData[index] == null) {\r\n                    fastRemove(index);\r\n                    return true;\r\n                }\r\n        } else {\r\n            for (int index = 0; index < size; index++)\r\n                if (o.equals(elementData[index])) {\r\n                    fastRemove(index);\r\n                    return true;\r\n                }\r\n        }\r\n        return false;\r\n    }\r\n\r\n    \/*\r\n     * Private remove method that skips bounds checking and does not\r\n     * return the value removed.\r\n     *\/\r\n    private void fastRemove(int index) {\r\n        modCount++;\r\n        int numMoved = size - index - 1;\r\n        if (numMoved > 0)\r\n            System.arraycopy(elementData, index+1, elementData, index,\r\n                             numMoved);\r\n        elementData[--size] = null; \/\/ Let gc do its work\r\n    }\r\n\r\n    \/**\r\n     * Removes all of the elements from this list.  The list will\r\n     * be empty after this call returns.\r\n     *\/\r\n    public void clear() {\r\n        modCount++;\r\n\r\n        \/\/ Let gc do its work\r\n        for (int i = 0; i < size; i++)\r\n            elementData[i] = null;\r\n\r\n        size = 0;\r\n    }\r\n\r\n    \/**\r\n     * Appends all of the elements in the specified collection to the end of\r\n     * this list, in the order that they are returned by the\r\n     * specified collection's Iterator.  The behavior of this operation is\r\n     * undefined if the specified collection is modified while the operation\r\n     * is in progress.  (This implies that the behavior of this call is\r\n     * undefined if the specified collection is this list, and this\r\n     * list is nonempty.)\r\n     *\r\n     * @param c collection containing elements to be added to this list\r\n     * @return <tt>true<\/tt> if this list changed as a result of the call\r\n     * @throws NullPointerException if the specified collection is null\r\n     *\/\r\n    public boolean addAll(Collection<? extends E> c) {\r\n        Object[] a = c.toArray();\r\n        int numNew = a.length;\r\n        ensureCapacityInternal(size + numNew);  \/\/ Increments modCount\r\n        System.arraycopy(a, 0, elementData, size, numNew);\r\n        size += numNew;\r\n        return numNew != 0;\r\n    }\r\n\r\n    \/**\r\n     * Inserts all of the elements in the specified collection into this\r\n     * list, starting at the specified position.  Shifts the element\r\n     * currently at that position (if any) and any subsequent elements to\r\n     * the right (increases their indices).  The new elements will appear\r\n     * in the list in the order that they are returned by the\r\n     * specified collection's iterator.\r\n     *\r\n     * @param index index at which to insert the first element from the\r\n     *              specified collection\r\n     * @param c collection containing elements to be added to this list\r\n     * @return <tt>true<\/tt> if this list changed as a result of the call\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     * @throws NullPointerException if the specified collection is null\r\n     *\/\r\n    public boolean addAll(int index, Collection<? extends E> c) {\r\n        rangeCheckForAdd(index);\r\n\r\n        Object[] a = c.toArray();\r\n        int numNew = a.length;\r\n        ensureCapacityInternal(size + numNew);  \/\/ Increments modCount\r\n\r\n        int numMoved = size - index;\r\n        if (numMoved > 0)\r\n            System.arraycopy(elementData, index, elementData, index + numNew,\r\n                             numMoved);\r\n\r\n        System.arraycopy(a, 0, elementData, index, numNew);\r\n        size += numNew;\r\n        return numNew != 0;\r\n    }\r\n\r\n    \/**\r\n     * Removes from this list all of the elements whose index is between\r\n     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.\r\n     * Shifts any succeeding elements to the left (reduces their index).\r\n     * This call shortens the list by {@code (toIndex - fromIndex)} elements.\r\n     * (If {@code toIndex==fromIndex}, this operation has no effect.)\r\n     *\r\n     * @throws IndexOutOfBoundsException if {@code fromIndex} or\r\n     *         {@code toIndex} is out of range\r\n     *         ({@code fromIndex < 0 ||\r\n     *          fromIndex >= size() ||\r\n     *          toIndex > size() ||\r\n     *          toIndex < fromIndex})\r\n     *\/\r\n    protected void removeRange(int fromIndex, int toIndex) {\r\n        modCount++;\r\n        int numMoved = size - toIndex;\r\n        System.arraycopy(elementData, toIndex, elementData, fromIndex,\r\n                         numMoved);\r\n\r\n        \/\/ Let gc do its work\r\n        int newSize = size - (toIndex-fromIndex);\r\n        while (size != newSize)\r\n            elementData[--size] = null;\r\n    }\r\n\r\n    \/**\r\n     * Checks if the given index is in range.  If not, throws an appropriate\r\n     * runtime exception.  This method does *not* check if the index is\r\n     * negative: It is always used immediately prior to an array access,\r\n     * which throws an ArrayIndexOutOfBoundsException if index is negative.\r\n     *\/\r\n    private void rangeCheck(int index) {\r\n        if (index >= size)\r\n            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));\r\n    }\r\n\r\n    \/**\r\n     * A version of rangeCheck used by add and addAll.\r\n     *\/\r\n    private void rangeCheckForAdd(int index) {\r\n        if (index > size || index < 0)\r\n            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));\r\n    }\r\n\r\n    \/**\r\n     * Constructs an IndexOutOfBoundsException detail message.\r\n     * Of the many possible refactorings of the error handling code,\r\n     * this \"outlining\" performs best with both server and client VMs.\r\n     *\/\r\n    private String outOfBoundsMsg(int index) {\r\n        return \"Index: \"+index+\", Size: \"+size;\r\n    }\r\n\r\n    \/**\r\n     * Removes from this list all of its elements that are contained in the\r\n     * specified collection.\r\n     *\r\n     * @param c collection containing elements to be removed from this list\r\n     * @return {@code true} if this list changed as a result of the call\r\n     * @throws ClassCastException if the class of an element of this list\r\n     *         is incompatible with the specified collection\r\n     * (<a href=\"Collection.html#optional-restrictions\">optional<\/a>)\r\n     * @throws NullPointerException if this list contains a null element and the\r\n     *         specified collection does not permit null elements\r\n     * (<a href=\"Collection.html#optional-restrictions\">optional<\/a>),\r\n     *         or if the specified collection is null\r\n     * @see Collection#contains(Object)\r\n     *\/\r\n    public boolean removeAll(Collection<?> c) {\r\n        return batchRemove(c, false);\r\n    }\r\n\r\n    \/**\r\n     * Retains only the elements in this list that are contained in the\r\n     * specified collection.  In other words, removes from this list all\r\n     * of its elements that are not contained in the specified collection.\r\n     *\r\n     * @param c collection containing elements to be retained in this list\r\n     * @return {@code true} if this list changed as a result of the call\r\n     * @throws ClassCastException if the class of an element of this list\r\n     *         is incompatible with the specified collection\r\n     * (<a href=\"Collection.html#optional-restrictions\">optional<\/a>)\r\n     * @throws NullPointerException if this list contains a null element and the\r\n     *         specified collection does not permit null elements\r\n     * (<a href=\"Collection.html#optional-restrictions\">optional<\/a>),\r\n     *         or if the specified collection is null\r\n     * @see Collection#contains(Object)\r\n     *\/\r\n    public boolean retainAll(Collection<?> c) {\r\n        return batchRemove(c, true);\r\n    }\r\n\r\n    private boolean batchRemove(Collection<?> c, boolean complement) {\r\n        final Object[] elementData = this.elementData;\r\n        int r = 0, w = 0;\r\n        boolean modified = false;\r\n        try {\r\n            for (; r < size; r++)\r\n                if (c.contains(elementData[r]) == complement)\r\n                    elementData[w++] = elementData[r];\r\n        } finally {\r\n            \/\/ Preserve behavioral compatibility with AbstractCollection,\r\n            \/\/ even if c.contains() throws.\r\n            if (r != size) {\r\n                System.arraycopy(elementData, r,\r\n                                 elementData, w,\r\n                                 size - r);\r\n                w += size - r;\r\n            }\r\n            if (w != size) {\r\n                for (int i = w; i < size; i++)\r\n                    elementData[i] = null;\r\n                modCount += size - w;\r\n                size = w;\r\n                modified = true;\r\n            }\r\n        }\r\n        return modified;\r\n    }\r\n\r\n    \/**\r\n     * Save the state of the <tt>ArrayList<\/tt> instance to a stream (that\r\n     * is, serialize it).\r\n     *\r\n     * @serialData The length of the array backing the <tt>ArrayList<\/tt>\r\n     *             instance is emitted (int), followed by all of its elements\r\n     *             (each an <tt>Object<\/tt>) in the proper order.\r\n     *\/\r\n    private void writeObject(java.io.ObjectOutputStream s)\r\n        throws java.io.IOException{\r\n        \/\/ Write out element count, and any hidden stuff\r\n        int expectedModCount = modCount;\r\n        s.defaultWriteObject();\r\n\r\n        \/\/ Write out array length\r\n        s.writeInt(elementData.length);\r\n\r\n        \/\/ Write out all elements in the proper order.\r\n        for (int i=0; i<size; i++)\r\n            s.writeObject(elementData[i]);\r\n\r\n        if (modCount != expectedModCount) {\r\n            throw new ConcurrentModificationException();\r\n        }\r\n\r\n    }\r\n\r\n    \/**\r\n     * Reconstitute the <tt>ArrayList<\/tt> instance from a stream (that is,\r\n     * deserialize it).\r\n     *\/\r\n    private void readObject(java.io.ObjectInputStream s)\r\n        throws java.io.IOException, ClassNotFoundException {\r\n        \/\/ Read in size, and any hidden stuff\r\n        s.defaultReadObject();\r\n\r\n        \/\/ Read in array length and allocate array\r\n        int arrayLength = s.readInt();\r\n        Object[] a = elementData = new Object[arrayLength];\r\n\r\n        \/\/ Read in all elements in the proper order.\r\n        for (int i=0; i<size; i++)\r\n            a[i] = s.readObject();\r\n    }\r\n\r\n    \/**\r\n     * Returns a list iterator over the elements in this list (in proper\r\n     * sequence), starting at the specified position in the list.\r\n     * The specified index indicates the first element that would be\r\n     * returned by an initial call to {@link ListIterator#next next}.\r\n     * An initial call to {@link ListIterator#previous previous} would\r\n     * return the element with the specified index minus one.\r\n     *\r\n     * <p>The returned list iterator is <a href=\"#fail-fast\"><i>fail-fast<\/i><\/a>.\r\n     *\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public ListIterator<E> listIterator(int index) {\r\n        if (index < 0 || index > size)\r\n            throw new IndexOutOfBoundsException(\"Index: \"+index);\r\n        return new ListItr(index);\r\n    }\r\n\r\n    \/**\r\n     * Returns a list iterator over the elements in this list (in proper\r\n     * sequence).\r\n     *\r\n     * <p>The returned list iterator is <a href=\"#fail-fast\"><i>fail-fast<\/i><\/a>.\r\n     *\r\n     * @see #listIterator(int)\r\n     *\/\r\n    public ListIterator<E> listIterator() {\r\n        return new ListItr(0);\r\n    }\r\n\r\n    \/**\r\n     * Returns an iterator over the elements in this list in proper sequence.\r\n     *\r\n     * <p>The returned iterator is <a href=\"#fail-fast\"><i>fail-fast<\/i><\/a>.\r\n     *\r\n     * @return an iterator over the elements in this list in proper sequence\r\n     *\/\r\n    public Iterator<E> iterator() {\r\n        return new Itr();\r\n    }\r\n\r\n    \/**\r\n     * An optimized version of AbstractList.Itr\r\n     *\/\r\n    private class Itr implements Iterator<E> {\r\n        int cursor;       \/\/ index of next element to return\r\n        int lastRet = -1; \/\/ index of last element returned; -1 if no such\r\n        int expectedModCount = modCount;\r\n\r\n        public boolean hasNext() {\r\n            return cursor != size;\r\n        }\r\n\r\n        @SuppressWarnings(\"unchecked\")\r\n        public E next() {\r\n            checkForComodification();\r\n            int i = cursor;\r\n            if (i >= size)\r\n                throw new NoSuchElementException();\r\n            Object[] elementData = ArrayList.this.elementData;\r\n            if (i >= elementData.length)\r\n                throw new ConcurrentModificationException();\r\n            cursor = i + 1;\r\n            return (E) elementData[lastRet = i];\r\n        }\r\n\r\n        public void remove() {\r\n            if (lastRet < 0)\r\n                throw new IllegalStateException();\r\n            checkForComodification();\r\n\r\n            try {\r\n                ArrayList.this.remove(lastRet);\r\n                cursor = lastRet;\r\n                lastRet = -1;\r\n                expectedModCount = modCount;\r\n            } catch (IndexOutOfBoundsException ex) {\r\n                throw new ConcurrentModificationException();\r\n            }\r\n        }\r\n\r\n        final void checkForComodification() {\r\n            if (modCount != expectedModCount)\r\n                throw new ConcurrentModificationException();\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * An optimized version of AbstractList.ListItr\r\n     *\/\r\n    private class ListItr extends Itr implements ListIterator<E> {\r\n        ListItr(int index) {\r\n            super();\r\n            cursor = index;\r\n        }\r\n\r\n        public boolean hasPrevious() {\r\n            return cursor != 0;\r\n        }\r\n\r\n        public int nextIndex() {\r\n            return cursor;\r\n        }\r\n\r\n        public int previousIndex() {\r\n            return cursor - 1;\r\n        }\r\n\r\n        @SuppressWarnings(\"unchecked\")\r\n        public E previous() {\r\n            checkForComodification();\r\n            int i = cursor - 1;\r\n            if (i < 0)\r\n                throw new NoSuchElementException();\r\n            Object[] elementData = ArrayList.this.elementData;\r\n            if (i >= elementData.length)\r\n                throw new ConcurrentModificationException();\r\n            cursor = i;\r\n            return (E) elementData[lastRet = i];\r\n        }\r\n\r\n        public void set(E e) {\r\n            if (lastRet < 0)\r\n                throw new IllegalStateException();\r\n            checkForComodification();\r\n\r\n            try {\r\n                ArrayList.this.set(lastRet, e);\r\n            } catch (IndexOutOfBoundsException ex) {\r\n                throw new ConcurrentModificationException();\r\n            }\r\n        }\r\n\r\n        public void add(E e) {\r\n            checkForComodification();\r\n\r\n            try {\r\n                int i = cursor;\r\n                ArrayList.this.add(i, e);\r\n                cursor = i + 1;\r\n                lastRet = -1;\r\n                expectedModCount = modCount;\r\n            } catch (IndexOutOfBoundsException ex) {\r\n                throw new ConcurrentModificationException();\r\n            }\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Returns a view of the portion of this list between the specified\r\n     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If\r\n     * {@code fromIndex} and {@code toIndex} are equal, the returned list is\r\n     * empty.)  The returned list is backed by this list, so non-structural\r\n     * changes in the returned list are reflected in this list, and vice-versa.\r\n     * The returned list supports all of the optional list operations.\r\n     *\r\n     * <p>This method eliminates the need for explicit range operations (of\r\n     * the sort that commonly exist for arrays).  Any operation that expects\r\n     * a list can be used as a range operation by passing a subList view\r\n     * instead of a whole list.  For example, the following idiom\r\n     * removes a range of elements from a list:\r\n     * <pre>\r\n     *      list.subList(from, to).clear();\r\n     * <\/pre>\r\n     * Similar idioms may be constructed for {@link #indexOf(Object)} and\r\n     * {@link #lastIndexOf(Object)}, and all of the algorithms in the\r\n     * {@link Collections} class can be applied to a subList.\r\n     *\r\n     * <p>The semantics of the list returned by this method become undefined if\r\n     * the backing list (i.e., this list) is <i>structurally modified<\/i> in\r\n     * any way other than via the returned list.  (Structural modifications are\r\n     * those that change the size of this list, or otherwise perturb it in such\r\n     * a fashion that iterations in progress may yield incorrect results.)\r\n     *\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     * @throws IllegalArgumentException {@inheritDoc}\r\n     *\/\r\n    public List<E> subList(int fromIndex, int toIndex) {\r\n        subListRangeCheck(fromIndex, toIndex, size);\r\n        return new SubList(this, 0, fromIndex, toIndex);\r\n    }\r\n\r\n    static void subListRangeCheck(int fromIndex, int toIndex, int size) {\r\n        if (fromIndex < 0)\r\n            throw new IndexOutOfBoundsException(\"fromIndex = \" + fromIndex);\r\n        if (toIndex > size)\r\n            throw new IndexOutOfBoundsException(\"toIndex = \" + toIndex);\r\n        if (fromIndex > toIndex)\r\n            throw new IllegalArgumentException(\"fromIndex(\" + fromIndex +\r\n                                               \") > toIndex(\" + toIndex + \")\");\r\n    }\r\n\r\n    private class SubList extends AbstractList<E> implements RandomAccess {\r\n        private final AbstractList<E> parent;\r\n        private final int parentOffset;\r\n        private final int offset;\r\n        int size;\r\n\r\n        SubList(AbstractList<E> parent,\r\n                int offset, int fromIndex, int toIndex) {\r\n            this.parent = parent;\r\n            this.parentOffset = fromIndex;\r\n            this.offset = offset + fromIndex;\r\n            this.size = toIndex - fromIndex;\r\n            this.modCount = ArrayList.this.modCount;\r\n        }\r\n\r\n        public E set(int index, E e) {\r\n            rangeCheck(index);\r\n            checkForComodification();\r\n            E oldValue = ArrayList.this.elementData(offset + index);\r\n            ArrayList.this.elementData[offset + index] = e;\r\n            return oldValue;\r\n        }\r\n\r\n        public E get(int index) {\r\n            rangeCheck(index);\r\n            checkForComodification();\r\n            return ArrayList.this.elementData(offset + index);\r\n        }\r\n\r\n        public int size() {\r\n            checkForComodification();\r\n            return this.size;\r\n        }\r\n\r\n        public void add(int index, E e) {\r\n            rangeCheckForAdd(index);\r\n            checkForComodification();\r\n            parent.add(parentOffset + index, e);\r\n            this.modCount = parent.modCount;\r\n            this.size++;\r\n        }\r\n\r\n        public E remove(int index) {\r\n            rangeCheck(index);\r\n            checkForComodification();\r\n            E result = parent.remove(parentOffset + index);\r\n            this.modCount = parent.modCount;\r\n            this.size--;\r\n            return result;\r\n        }\r\n\r\n        protected void removeRange(int fromIndex, int toIndex) {\r\n            checkForComodification();\r\n            parent.removeRange(parentOffset + fromIndex,\r\n                               parentOffset + toIndex);\r\n            this.modCount = parent.modCount;\r\n            this.size -= toIndex - fromIndex;\r\n        }\r\n\r\n        public boolean addAll(Collection<? extends E> c) {\r\n            return addAll(this.size, c);\r\n        }\r\n\r\n        public boolean addAll(int index, Collection<? extends E> c) {\r\n            rangeCheckForAdd(index);\r\n            int cSize = c.size();\r\n            if (cSize==0)\r\n                return false;\r\n\r\n            checkForComodification();\r\n            parent.addAll(parentOffset + index, c);\r\n            this.modCount = parent.modCount;\r\n            this.size += cSize;\r\n            return true;\r\n        }\r\n\r\n        public Iterator<E> iterator() {\r\n            return listIterator();\r\n        }\r\n\r\n        public ListIterator<E> listIterator(final int index) {\r\n            checkForComodification();\r\n            rangeCheckForAdd(index);\r\n            final int offset = this.offset;\r\n\r\n            return new ListIterator<E>() {\r\n                int cursor = index;\r\n                int lastRet = -1;\r\n                int expectedModCount = ArrayList.this.modCount;\r\n\r\n                public boolean hasNext() {\r\n                    return cursor != SubList.this.size;\r\n                }\r\n\r\n                @SuppressWarnings(\"unchecked\")\r\n                public E next() {\r\n                    checkForComodification();\r\n                    int i = cursor;\r\n                    if (i >= SubList.this.size)\r\n                        throw new NoSuchElementException();\r\n                    Object[] elementData = ArrayList.this.elementData;\r\n                    if (offset + i >= elementData.length)\r\n                        throw new ConcurrentModificationException();\r\n                    cursor = i + 1;\r\n                    return (E) elementData[offset + (lastRet = i)];\r\n                }\r\n\r\n                public boolean hasPrevious() {\r\n                    return cursor != 0;\r\n                }\r\n\r\n                @SuppressWarnings(\"unchecked\")\r\n                public E previous() {\r\n                    checkForComodification();\r\n                    int i = cursor - 1;\r\n                    if (i < 0)\r\n                        throw new NoSuchElementException();\r\n                    Object[] elementData = ArrayList.this.elementData;\r\n                    if (offset + i >= elementData.length)\r\n                        throw new ConcurrentModificationException();\r\n                    cursor = i;\r\n                    return (E) elementData[offset + (lastRet = i)];\r\n                }\r\n\r\n                public int nextIndex() {\r\n                    return cursor;\r\n                }\r\n\r\n                public int previousIndex() {\r\n                    return cursor - 1;\r\n                }\r\n\r\n                public void remove() {\r\n                    if (lastRet < 0)\r\n                        throw new IllegalStateException();\r\n                    checkForComodification();\r\n\r\n                    try {\r\n                        SubList.this.remove(lastRet);\r\n                        cursor = lastRet;\r\n                        lastRet = -1;\r\n                        expectedModCount = ArrayList.this.modCount;\r\n                    } catch (IndexOutOfBoundsException ex) {\r\n                        throw new ConcurrentModificationException();\r\n                    }\r\n                }\r\n\r\n                public void set(E e) {\r\n                    if (lastRet < 0)\r\n                        throw new IllegalStateException();\r\n                    checkForComodification();\r\n\r\n                    try {\r\n                        ArrayList.this.set(offset + lastRet, e);\r\n                    } catch (IndexOutOfBoundsException ex) {\r\n                        throw new ConcurrentModificationException();\r\n                    }\r\n                }\r\n\r\n                public void add(E e) {\r\n                    checkForComodification();\r\n\r\n                    try {\r\n                        int i = cursor;\r\n                        SubList.this.add(i, e);\r\n                        cursor = i + 1;\r\n                        lastRet = -1;\r\n                        expectedModCount = ArrayList.this.modCount;\r\n                    } catch (IndexOutOfBoundsException ex) {\r\n                        throw new ConcurrentModificationException();\r\n                    }\r\n                }\r\n\r\n                final void checkForComodification() {\r\n                    if (expectedModCount != ArrayList.this.modCount)\r\n                        throw new ConcurrentModificationException();\r\n                }\r\n            };\r\n        }\r\n\r\n        public List<E> subList(int fromIndex, int toIndex) {\r\n            subListRangeCheck(fromIndex, toIndex, size);\r\n            return new SubList(this, offset, fromIndex, toIndex);\r\n        }\r\n\r\n        private void rangeCheck(int index) {\r\n            if (index < 0 || index >= this.size)\r\n                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));\r\n        }\r\n\r\n        private void rangeCheckForAdd(int index) {\r\n            if (index < 0 || index > this.size)\r\n                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));\r\n        }\r\n\r\n        private String outOfBoundsMsg(int index) {\r\n            return \"Index: \"+index+\", Size: \"+this.size;\r\n        }\r\n\r\n        private void checkForComodification() {\r\n            if (ArrayList.this.modCount != this.modCount)\r\n                throw new ConcurrentModificationException();\r\n        }\r\n    }\r\n}\r\n<\/code><\/pre>\n\n\n\n
jdk 8 ArrayList\u6e90\u7801<\/p>\n\n\n\n
\/*\r\n * Copyright (c) 1997, 2017, Oracle and\/or its affiliates. All rights reserved.\r\n * ORACLE PROPRIETARY\/CONFIDENTIAL. Use is subject to license terms.\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\r\n *\/\r\n\r\npackage top.qaqaq.java.P528.src8;\r\n\r\nimport java.util.*;\r\nimport java.util.function.Consumer;\r\nimport java.util.function.Predicate;\r\nimport java.util.function.UnaryOperator;\r\nimport sun.misc.SharedSecrets;\r\n\r\n\/**\r\n * Resizable-array implementation of the <tt>List<\/tt> interface.  Implements\r\n * all optional list operations, and permits all elements, including\r\n * <tt>null<\/tt>.  In addition to implementing the <tt>List<\/tt> interface,\r\n * this class provides methods to manipulate the size of the array that is\r\n * used internally to store the list.  (This class is roughly equivalent to\r\n * <tt>Vector<\/tt>, except that it is unsynchronized.)\r\n *\r\n * <p>The <tt>size<\/tt>, <tt>isEmpty<\/tt>, <tt>get<\/tt>, <tt>set<\/tt>,\r\n * <tt>iterator<\/tt>, and <tt>listIterator<\/tt> operations run in constant\r\n * time.  The <tt>add<\/tt> operation runs in <i>amortized constant time<\/i>,\r\n * that is, adding n elements requires O(n) time.  All of the other operations\r\n * run in linear time (roughly speaking).  The constant factor is low compared\r\n * to that for the <tt>LinkedList<\/tt> implementation.\r\n *\r\n * <p>Each <tt>ArrayList<\/tt> instance has a <i>capacity<\/i>.  The capacity is\r\n * the size of the array used to store the elements in the list.  It is always\r\n * at least as large as the list size.  As elements are added to an ArrayList,\r\n * its capacity grows automatically.  The details of the growth policy are not\r\n * specified beyond the fact that adding an element has constant amortized\r\n * time cost.\r\n *\r\n * <p>An application can increase the capacity of an <tt>ArrayList<\/tt> instance\r\n * before adding a large number of elements using the <tt>ensureCapacity<\/tt>\r\n * operation.  This may reduce the amount of incremental reallocation.\r\n *\r\n * <p><strong>Note that this implementation is not synchronized.<\/strong>\r\n * If multiple threads access an <tt>ArrayList<\/tt> instance concurrently,\r\n * and at least one of the threads modifies the list structurally, it\r\n * <i>must<\/i> be synchronized externally.  (A structural modification is\r\n * any operation that adds or deletes one or more elements, or explicitly\r\n * resizes the backing array; merely setting the value of an element is not\r\n * a structural modification.)  This is typically accomplished by\r\n * synchronizing on some object that naturally encapsulates the list.\r\n *\r\n * If no such object exists, the list should be \"wrapped\" using the\r\n * {@link Collections#synchronizedList Collections.synchronizedList}\r\n * method.  This is best done at creation time, to prevent accidental\r\n * unsynchronized access to the list:<pre>\r\n *   List list = Collections.synchronizedList(new ArrayList(...));<\/pre>\r\n *\r\n * <p><a name=\"fail-fast\">\r\n * The iterators returned by this class's {@link #iterator() iterator} and\r\n * {@link #listIterator(int) listIterator} methods are <em>fail-fast<\/em>:<\/a>\r\n * if the list is structurally modified at any time after the iterator is\r\n * created, in any way except through the iterator's own\r\n * {@link ListIterator#remove() remove} or\r\n * {@link ListIterator#add(Object) add} methods, the iterator will throw a\r\n * {@link ConcurrentModificationException}.  Thus, in the face of\r\n * concurrent modification, the iterator fails quickly and cleanly, rather\r\n * than risking arbitrary, non-deterministic behavior at an undetermined\r\n * time in the future.\r\n *\r\n * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed\r\n * as it is, generally speaking, impossible to make any hard guarantees in the\r\n * presence of unsynchronized concurrent modification.  Fail-fast iterators\r\n * throw {@code ConcurrentModificationException} on a best-effort basis.\r\n * Therefore, it would be wrong to write a program that depended on this\r\n * exception for its correctness:  <i>the fail-fast behavior of iterators\r\n * should be used only to detect bugs.<\/i>\r\n *\r\n * <p>This class is a member of the\r\n * <a href=\"{@docRoot}\/..\/technotes\/guides\/collections\/index.html\">\r\n * Java Collections Framework<\/a>.\r\n *\r\n * @author  Josh Bloch\r\n * @author  Neal Gafter\r\n * @see     Collection\r\n * @see     List\r\n * @see     LinkedList\r\n * @see     Vector\r\n * @since   1.2\r\n *\/\r\n\r\npublic class ArrayList<E> extends AbstractList<E>\r\n        implements List<E>, RandomAccess, Cloneable, java.io.Serializable\r\n{\r\n    private static final long serialVersionUID = 8683452581122892189L;\r\n\r\n    \/**\r\n     * Default initial capacity.\r\n     *\/\r\n    private static final int DEFAULT_CAPACITY = 10;\r\n\r\n    \/**\r\n     * Shared empty array instance used for empty instances.\r\n     *\/\r\n    private static final Object[] EMPTY_ELEMENTDATA = {};\r\n\r\n    \/**\r\n     * Shared empty array instance used for default sized empty instances. We\r\n     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when\r\n     * first element is added.\r\n     *\/\r\n    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};\r\n\r\n    \/**\r\n     * The array buffer into which the elements of the ArrayList are stored.\r\n     * The capacity of the ArrayList is the length of this array buffer. Any\r\n     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA\r\n     * will be expanded to DEFAULT_CAPACITY when the first element is added.\r\n     *\/\r\n    transient Object[] elementData; \/\/ non-private to simplify nested class access\r\n\r\n    \/**\r\n     * The size of the ArrayList (the number of elements it contains).\r\n     *\r\n     * @serial\r\n     *\/\r\n    private int size;\r\n\r\n    \/**\r\n     * Constructs an empty list with the specified initial capacity.\r\n     *\r\n     * @param  initialCapacity  the initial capacity of the list\r\n     * @throws IllegalArgumentException if the specified initial capacity\r\n     *         is negative\r\n     *\/\r\n    public ArrayList(int initialCapacity) {\r\n        if (initialCapacity > 0) {\r\n            this.elementData = new Object[initialCapacity];\r\n        } else if (initialCapacity == 0) {\r\n            this.elementData = EMPTY_ELEMENTDATA;\r\n        } else {\r\n            throw new IllegalArgumentException(\"Illegal Capacity: \"+\r\n                                               initialCapacity);\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Constructs an empty list with an initial capacity of ten.\r\n     *\/\r\n    public ArrayList() {\r\n        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;\r\n    }\r\n\r\n    \/**\r\n     * Constructs a list containing the elements of the specified\r\n     * collection, in the order they are returned by the collection's\r\n     * iterator.\r\n     *\r\n     * @param c the collection whose elements are to be placed into this list\r\n     * @throws NullPointerException if the specified collection is null\r\n     *\/\r\n    public ArrayList(Collection<? extends E> c) {\r\n        Object[] a = c.toArray();\r\n        if ((size = a.length) != 0) {\r\n            if (c.getClass() == ArrayList.class) {\r\n                elementData = a;\r\n            } else {\r\n                elementData = Arrays.copyOf(a, size, Object[].class);\r\n            }\r\n        } else {\r\n            \/\/ replace with empty array.\r\n            elementData = EMPTY_ELEMENTDATA;\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Trims the capacity of this <tt>ArrayList<\/tt> instance to be the\r\n     * list's current size.  An application can use this operation to minimize\r\n     * the storage of an <tt>ArrayList<\/tt> instance.\r\n     *\/\r\n    public void trimToSize() {\r\n        modCount++;\r\n        if (size < elementData.length) {\r\n            elementData = (size == 0)\r\n              ? EMPTY_ELEMENTDATA\r\n              : Arrays.copyOf(elementData, size);\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Increases the capacity of this <tt>ArrayList<\/tt> instance, if\r\n     * necessary, to ensure that it can hold at least the number of elements\r\n     * specified by the minimum capacity argument.\r\n     *\r\n     * @param   minCapacity   the desired minimum capacity\r\n     *\/\r\n    public void ensureCapacity(int minCapacity) {\r\n        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)\r\n            \/\/ any size if not default element table\r\n            ? 0\r\n            \/\/ larger than default for default empty table. It's already\r\n            \/\/ supposed to be at default size.\r\n            : DEFAULT_CAPACITY;\r\n\r\n        if (minCapacity > minExpand) {\r\n            ensureExplicitCapacity(minCapacity);\r\n        }\r\n    }\r\n\r\n    private static int calculateCapacity(Object[] elementData, int minCapacity) {\r\n        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {\r\n            return Math.max(DEFAULT_CAPACITY, minCapacity);\r\n        }\r\n        return minCapacity;\r\n    }\r\n\r\n    private void ensureCapacityInternal(int minCapacity) {\r\n        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));\r\n    }\r\n\r\n    private void ensureExplicitCapacity(int minCapacity) {\r\n        modCount++;\r\n\r\n        \/\/ overflow-conscious code\r\n        if (minCapacity - elementData.length > 0)\r\n            grow(minCapacity);\r\n    }\r\n\r\n    \/**\r\n     * The maximum size of array to allocate.\r\n     * Some VMs reserve some header words in an array.\r\n     * Attempts to allocate larger arrays may result in\r\n     * OutOfMemoryError: Requested array size exceeds VM limit\r\n     *\/\r\n    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;\r\n\r\n    \/**\r\n     * Increases the capacity to ensure that it can hold at least the\r\n     * number of elements specified by the minimum capacity argument.\r\n     *\r\n     * @param minCapacity the desired minimum capacity\r\n     *\/\r\n    private void grow(int minCapacity) {\r\n        \/\/ overflow-conscious code\r\n        int oldCapacity = elementData.length;\r\n        int newCapacity = oldCapacity + (oldCapacity >> 1);\r\n        if (newCapacity - minCapacity < 0)\r\n            newCapacity = minCapacity;\r\n        if (newCapacity - MAX_ARRAY_SIZE > 0)\r\n            newCapacity = hugeCapacity(minCapacity);\r\n        \/\/ minCapacity is usually close to size, so this is a win:\r\n        elementData = Arrays.copyOf(elementData, newCapacity);\r\n    }\r\n\r\n    private static int hugeCapacity(int minCapacity) {\r\n        if (minCapacity < 0) \/\/ overflow\r\n            throw new OutOfMemoryError();\r\n        return (minCapacity > MAX_ARRAY_SIZE) ?\r\n            Integer.MAX_VALUE :\r\n            MAX_ARRAY_SIZE;\r\n    }\r\n\r\n    \/**\r\n     * Returns the number of elements in this list.\r\n     *\r\n     * @return the number of elements in this list\r\n     *\/\r\n    public int size() {\r\n        return size;\r\n    }\r\n\r\n    \/**\r\n     * Returns <tt>true<\/tt> if this list contains no elements.\r\n     *\r\n     * @return <tt>true<\/tt> if this list contains no elements\r\n     *\/\r\n    public boolean isEmpty() {\r\n        return size == 0;\r\n    }\r\n\r\n    \/**\r\n     * Returns <tt>true<\/tt> if this list contains the specified element.\r\n     * More formally, returns <tt>true<\/tt> if and only if this list contains\r\n     * at least one element <tt>e<\/tt> such that\r\n     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))<\/tt>.\r\n     *\r\n     * @param o element whose presence in this list is to be tested\r\n     * @return <tt>true<\/tt> if this list contains the specified element\r\n     *\/\r\n    public boolean contains(Object o) {\r\n        return indexOf(o) >= 0;\r\n    }\r\n\r\n    \/**\r\n     * Returns the index of the first occurrence of the specified element\r\n     * in this list, or -1 if this list does not contain the element.\r\n     * More formally, returns the lowest index <tt>i<\/tt> such that\r\n     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))<\/tt>,\r\n     * or -1 if there is no such index.\r\n     *\/\r\n    public int indexOf(Object o) {\r\n        if (o == null) {\r\n            for (int i = 0; i < size; i++)\r\n                if (elementData[i]==null)\r\n                    return i;\r\n        } else {\r\n            for (int i = 0; i < size; i++)\r\n                if (o.equals(elementData[i]))\r\n                    return i;\r\n        }\r\n        return -1;\r\n    }\r\n\r\n    \/**\r\n     * Returns the index of the last occurrence of the specified element\r\n     * in this list, or -1 if this list does not contain the element.\r\n     * More formally, returns the highest index <tt>i<\/tt> such that\r\n     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))<\/tt>,\r\n     * or -1 if there is no such index.\r\n     *\/\r\n    public int lastIndexOf(Object o) {\r\n        if (o == null) {\r\n            for (int i = size-1; i >= 0; i--)\r\n                if (elementData[i]==null)\r\n                    return i;\r\n        } else {\r\n            for (int i = size-1; i >= 0; i--)\r\n                if (o.equals(elementData[i]))\r\n                    return i;\r\n        }\r\n        return -1;\r\n    }\r\n\r\n    \/**\r\n     * Returns a shallow copy of this <tt>ArrayList<\/tt> instance.  (The\r\n     * elements themselves are not copied.)\r\n     *\r\n     * @return a clone of this <tt>ArrayList<\/tt> instance\r\n     *\/\r\n    public Object clone() {\r\n        try {\r\n            ArrayList<?> v = (ArrayList<?>) super.clone();\r\n            v.elementData = Arrays.copyOf(elementData, size);\r\n            v.modCount = 0;\r\n            return v;\r\n        } catch (CloneNotSupportedException e) {\r\n            \/\/ this shouldn't happen, since we are Cloneable\r\n            throw new InternalError(e);\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Returns an array containing all of the elements in this list\r\n     * in proper sequence (from first to last element).\r\n     *\r\n     * <p>The returned array will be \"safe\" in that no references to it are\r\n     * maintained by this list.  (In other words, this method must allocate\r\n     * a new array).  The caller is thus free to modify the returned array.\r\n     *\r\n     * <p>This method acts as bridge between array-based and collection-based\r\n     * APIs.\r\n     *\r\n     * @return an array containing all of the elements in this list in\r\n     *         proper sequence\r\n     *\/\r\n    public Object[] toArray() {\r\n        return Arrays.copyOf(elementData, size);\r\n    }\r\n\r\n    \/**\r\n     * Returns an array containing all of the elements in this list in proper\r\n     * sequence (from first to last element); the runtime type of the returned\r\n     * array is that of the specified array.  If the list fits in the\r\n     * specified array, it is returned therein.  Otherwise, a new array is\r\n     * allocated with the runtime type of the specified array and the size of\r\n     * this list.\r\n     *\r\n     * <p>If the list fits in the specified array with room to spare\r\n     * (i.e., the array has more elements than the list), the element in\r\n     * the array immediately following the end of the collection is set to\r\n     * <tt>null<\/tt>.  (This is useful in determining the length of the\r\n     * list <i>only<\/i> if the caller knows that the list does not contain\r\n     * any null elements.)\r\n     *\r\n     * @param a the array into which the elements of the list are to\r\n     *          be stored, if it is big enough; otherwise, a new array of the\r\n     *          same runtime type is allocated for this purpose.\r\n     * @return an array containing the elements of the list\r\n     * @throws ArrayStoreException if the runtime type of the specified array\r\n     *         is not a supertype of the runtime type of every element in\r\n     *         this list\r\n     * @throws NullPointerException if the specified array is null\r\n     *\/\r\n    @SuppressWarnings(\"unchecked\")\r\n    public <T> T[] toArray(T[] a) {\r\n        if (a.length < size)\r\n            \/\/ Make a new array of a's runtime type, but my contents:\r\n            return (T[]) Arrays.copyOf(elementData, size, a.getClass());\r\n        System.arraycopy(elementData, 0, a, 0, size);\r\n        if (a.length > size)\r\n            a[size] = null;\r\n        return a;\r\n    }\r\n\r\n    \/\/ Positional Access Operations\r\n\r\n    @SuppressWarnings(\"unchecked\")\r\n    E elementData(int index) {\r\n        return (E) elementData[index];\r\n    }\r\n\r\n    \/**\r\n     * Returns the element at the specified position in this list.\r\n     *\r\n     * @param  index index of the element to return\r\n     * @return the element at the specified position in this list\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public E get(int index) {\r\n        rangeCheck(index);\r\n\r\n        return elementData(index);\r\n    }\r\n\r\n    \/**\r\n     * Replaces the element at the specified position in this list with\r\n     * the specified element.\r\n     *\r\n     * @param index index of the element to replace\r\n     * @param element element to be stored at the specified position\r\n     * @return the element previously at the specified position\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public E set(int index, E element) {\r\n        rangeCheck(index);\r\n\r\n        E oldValue = elementData(index);\r\n        elementData[index] = element;\r\n        return oldValue;\r\n    }\r\n\r\n    \/**\r\n     * Appends the specified element to the end of this list.\r\n     *\r\n     * @param e element to be appended to this list\r\n     * @return <tt>true<\/tt> (as specified by {@link Collection#add})\r\n     *\/\r\n    public boolean add(E e) {\r\n        ensureCapacityInternal(size + 1);  \/\/ Increments modCount!!\r\n        elementData[size++] = e;\r\n        return true;\r\n    }\r\n\r\n    \/**\r\n     * Inserts the specified element at the specified position in this\r\n     * list. Shifts the element currently at that position (if any) and\r\n     * any subsequent elements to the right (adds one to their indices).\r\n     *\r\n     * @param index index at which the specified element is to be inserted\r\n     * @param element element to be inserted\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public void add(int index, E element) {\r\n        rangeCheckForAdd(index);\r\n\r\n        ensureCapacityInternal(size + 1);  \/\/ Increments modCount!!\r\n        System.arraycopy(elementData, index, elementData, index + 1,\r\n                         size - index);\r\n        elementData[index] = element;\r\n        size++;\r\n    }\r\n\r\n    \/**\r\n     * Removes the element at the specified position in this list.\r\n     * Shifts any subsequent elements to the left (subtracts one from their\r\n     * indices).\r\n     *\r\n     * @param index the index of the element to be removed\r\n     * @return the element that was removed from the list\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public E remove(int index) {\r\n        rangeCheck(index);\r\n\r\n        modCount++;\r\n        E oldValue = elementData(index);\r\n\r\n        int numMoved = size - index - 1;\r\n        if (numMoved > 0)\r\n            System.arraycopy(elementData, index+1, elementData, index,\r\n                             numMoved);\r\n        elementData[--size] = null; \/\/ clear to let GC do its work\r\n\r\n        return oldValue;\r\n    }\r\n\r\n    \/**\r\n     * Removes the first occurrence of the specified element from this list,\r\n     * if it is present.  If the list does not contain the element, it is\r\n     * unchanged.  More formally, removes the element with the lowest index\r\n     * <tt>i<\/tt> such that\r\n     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))<\/tt>\r\n     * (if such an element exists).  Returns <tt>true<\/tt> if this list\r\n     * contained the specified element (or equivalently, if this list\r\n     * changed as a result of the call).\r\n     *\r\n     * @param o element to be removed from this list, if present\r\n     * @return <tt>true<\/tt> if this list contained the specified element\r\n     *\/\r\n    public boolean remove(Object o) {\r\n        if (o == null) {\r\n            for (int index = 0; index < size; index++)\r\n                if (elementData[index] == null) {\r\n                    fastRemove(index);\r\n                    return true;\r\n                }\r\n        } else {\r\n            for (int index = 0; index < size; index++)\r\n                if (o.equals(elementData[index])) {\r\n                    fastRemove(index);\r\n                    return true;\r\n                }\r\n        }\r\n        return false;\r\n    }\r\n\r\n    \/*\r\n     * Private remove method that skips bounds checking and does not\r\n     * return the value removed.\r\n     *\/\r\n    private void fastRemove(int index) {\r\n        modCount++;\r\n        int numMoved = size - index - 1;\r\n        if (numMoved > 0)\r\n            System.arraycopy(elementData, index+1, elementData, index,\r\n                             numMoved);\r\n        elementData[--size] = null; \/\/ clear to let GC do its work\r\n    }\r\n\r\n    \/**\r\n     * Removes all of the elements from this list.  The list will\r\n     * be empty after this call returns.\r\n     *\/\r\n    public void clear() {\r\n        modCount++;\r\n\r\n        \/\/ clear to let GC do its work\r\n        for (int i = 0; i < size; i++)\r\n            elementData[i] = null;\r\n\r\n        size = 0;\r\n    }\r\n\r\n    \/**\r\n     * Appends all of the elements in the specified collection to the end of\r\n     * this list, in the order that they are returned by the\r\n     * specified collection's Iterator.  The behavior of this operation is\r\n     * undefined if the specified collection is modified while the operation\r\n     * is in progress.  (This implies that the behavior of this call is\r\n     * undefined if the specified collection is this list, and this\r\n     * list is nonempty.)\r\n     *\r\n     * @param c collection containing elements to be added to this list\r\n     * @return <tt>true<\/tt> if this list changed as a result of the call\r\n     * @throws NullPointerException if the specified collection is null\r\n     *\/\r\n    public boolean addAll(Collection<? extends E> c) {\r\n        Object[] a = c.toArray();\r\n        int numNew = a.length;\r\n        ensureCapacityInternal(size + numNew);  \/\/ Increments modCount\r\n        System.arraycopy(a, 0, elementData, size, numNew);\r\n        size += numNew;\r\n        return numNew != 0;\r\n    }\r\n\r\n    \/**\r\n     * Inserts all of the elements in the specified collection into this\r\n     * list, starting at the specified position.  Shifts the element\r\n     * currently at that position (if any) and any subsequent elements to\r\n     * the right (increases their indices).  The new elements will appear\r\n     * in the list in the order that they are returned by the\r\n     * specified collection's iterator.\r\n     *\r\n     * @param index index at which to insert the first element from the\r\n     *              specified collection\r\n     * @param c collection containing elements to be added to this list\r\n     * @return <tt>true<\/tt> if this list changed as a result of the call\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     * @throws NullPointerException if the specified collection is null\r\n     *\/\r\n    public boolean addAll(int index, Collection<? extends E> c) {\r\n        rangeCheckForAdd(index);\r\n\r\n        Object[] a = c.toArray();\r\n        int numNew = a.length;\r\n        ensureCapacityInternal(size + numNew);  \/\/ Increments modCount\r\n\r\n        int numMoved = size - index;\r\n        if (numMoved > 0)\r\n            System.arraycopy(elementData, index, elementData, index + numNew,\r\n                             numMoved);\r\n\r\n        System.arraycopy(a, 0, elementData, index, numNew);\r\n        size += numNew;\r\n        return numNew != 0;\r\n    }\r\n\r\n    \/**\r\n     * Removes from this list all of the elements whose index is between\r\n     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.\r\n     * Shifts any succeeding elements to the left (reduces their index).\r\n     * This call shortens the list by {@code (toIndex - fromIndex)} elements.\r\n     * (If {@code toIndex==fromIndex}, this operation has no effect.)\r\n     *\r\n     * @throws IndexOutOfBoundsException if {@code fromIndex} or\r\n     *         {@code toIndex} is out of range\r\n     *         ({@code fromIndex < 0 ||\r\n     *          fromIndex >= size() ||\r\n     *          toIndex > size() ||\r\n     *          toIndex < fromIndex})\r\n     *\/\r\n    protected void removeRange(int fromIndex, int toIndex) {\r\n        modCount++;\r\n        int numMoved = size - toIndex;\r\n        System.arraycopy(elementData, toIndex, elementData, fromIndex,\r\n                         numMoved);\r\n\r\n        \/\/ clear to let GC do its work\r\n        int newSize = size - (toIndex-fromIndex);\r\n        for (int i = newSize; i < size; i++) {\r\n            elementData[i] = null;\r\n        }\r\n        size = newSize;\r\n    }\r\n\r\n    \/**\r\n     * Checks if the given index is in range.  If not, throws an appropriate\r\n     * runtime exception.  This method does *not* check if the index is\r\n     * negative: It is always used immediately prior to an array access,\r\n     * which throws an ArrayIndexOutOfBoundsException if index is negative.\r\n     *\/\r\n    private void rangeCheck(int index) {\r\n        if (index >= size)\r\n            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));\r\n    }\r\n\r\n    \/**\r\n     * A version of rangeCheck used by add and addAll.\r\n     *\/\r\n    private void rangeCheckForAdd(int index) {\r\n        if (index > size || index < 0)\r\n            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));\r\n    }\r\n\r\n    \/**\r\n     * Constructs an IndexOutOfBoundsException detail message.\r\n     * Of the many possible refactorings of the error handling code,\r\n     * this \"outlining\" performs best with both server and client VMs.\r\n     *\/\r\n    private String outOfBoundsMsg(int index) {\r\n        return \"Index: \"+index+\", Size: \"+size;\r\n    }\r\n\r\n    \/**\r\n     * Removes from this list all of its elements that are contained in the\r\n     * specified collection.\r\n     *\r\n     * @param c collection containing elements to be removed from this list\r\n     * @return {@code true} if this list changed as a result of the call\r\n     * @throws ClassCastException if the class of an element of this list\r\n     *         is incompatible with the specified collection\r\n     * (<a href=\"Collection.html#optional-restrictions\">optional<\/a>)\r\n     * @throws NullPointerException if this list contains a null element and the\r\n     *         specified collection does not permit null elements\r\n     * (<a href=\"Collection.html#optional-restrictions\">optional<\/a>),\r\n     *         or if the specified collection is null\r\n     * @see Collection#contains(Object)\r\n     *\/\r\n    public boolean removeAll(Collection<?> c) {\r\n        Objects.requireNonNull(c);\r\n        return batchRemove(c, false);\r\n    }\r\n\r\n    \/**\r\n     * Retains only the elements in this list that are contained in the\r\n     * specified collection.  In other words, removes from this list all\r\n     * of its elements that are not contained in the specified collection.\r\n     *\r\n     * @param c collection containing elements to be retained in this list\r\n     * @return {@code true} if this list changed as a result of the call\r\n     * @throws ClassCastException if the class of an element of this list\r\n     *         is incompatible with the specified collection\r\n     * (<a href=\"Collection.html#optional-restrictions\">optional<\/a>)\r\n     * @throws NullPointerException if this list contains a null element and the\r\n     *         specified collection does not permit null elements\r\n     * (<a href=\"Collection.html#optional-restrictions\">optional<\/a>),\r\n     *         or if the specified collection is null\r\n     * @see Collection#contains(Object)\r\n     *\/\r\n    public boolean retainAll(Collection<?> c) {\r\n        Objects.requireNonNull(c);\r\n        return batchRemove(c, true);\r\n    }\r\n\r\n    private boolean batchRemove(Collection<?> c, boolean complement) {\r\n        final Object[] elementData = this.elementData;\r\n        int r = 0, w = 0;\r\n        boolean modified = false;\r\n        try {\r\n            for (; r < size; r++)\r\n                if (c.contains(elementData[r]) == complement)\r\n                    elementData[w++] = elementData[r];\r\n        } finally {\r\n            \/\/ Preserve behavioral compatibility with AbstractCollection,\r\n            \/\/ even if c.contains() throws.\r\n            if (r != size) {\r\n                System.arraycopy(elementData, r,\r\n                                 elementData, w,\r\n                                 size - r);\r\n                w += size - r;\r\n            }\r\n            if (w != size) {\r\n                \/\/ clear to let GC do its work\r\n                for (int i = w; i < size; i++)\r\n                    elementData[i] = null;\r\n                modCount += size - w;\r\n                size = w;\r\n                modified = true;\r\n            }\r\n        }\r\n        return modified;\r\n    }\r\n\r\n    \/**\r\n     * Save the state of the <tt>ArrayList<\/tt> instance to a stream (that\r\n     * is, serialize it).\r\n     *\r\n     * @serialData The length of the array backing the <tt>ArrayList<\/tt>\r\n     *             instance is emitted (int), followed by all of its elements\r\n     *             (each an <tt>Object<\/tt>) in the proper order.\r\n     *\/\r\n    private void writeObject(java.io.ObjectOutputStream s)\r\n        throws java.io.IOException{\r\n        \/\/ Write out element count, and any hidden stuff\r\n        int expectedModCount = modCount;\r\n        s.defaultWriteObject();\r\n\r\n        \/\/ Write out size as capacity for behavioural compatibility with clone()\r\n        s.writeInt(size);\r\n\r\n        \/\/ Write out all elements in the proper order.\r\n        for (int i=0; i<size; i++) {\r\n            s.writeObject(elementData[i]);\r\n        }\r\n\r\n        if (modCount != expectedModCount) {\r\n            throw new ConcurrentModificationException();\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Reconstitute the <tt>ArrayList<\/tt> instance from a stream (that is,\r\n     * deserialize it).\r\n     *\/\r\n    private void readObject(java.io.ObjectInputStream s)\r\n        throws java.io.IOException, ClassNotFoundException {\r\n        elementData = EMPTY_ELEMENTDATA;\r\n\r\n        \/\/ Read in size, and any hidden stuff\r\n        s.defaultReadObject();\r\n\r\n        \/\/ Read in capacity\r\n        s.readInt(); \/\/ ignored\r\n\r\n        if (size > 0) {\r\n            \/\/ be like clone(), allocate array based upon size not capacity\r\n            int capacity = calculateCapacity(elementData, size);\r\n            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);\r\n            ensureCapacityInternal(size);\r\n\r\n            Object[] a = elementData;\r\n            \/\/ Read in all elements in the proper order.\r\n            for (int i=0; i<size; i++) {\r\n                a[i] = s.readObject();\r\n            }\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Returns a list iterator over the elements in this list (in proper\r\n     * sequence), starting at the specified position in the list.\r\n     * The specified index indicates the first element that would be\r\n     * returned by an initial call to {@link ListIterator#next next}.\r\n     * An initial call to {@link ListIterator#previous previous} would\r\n     * return the element with the specified index minus one.\r\n     *\r\n     * <p>The returned list iterator is <a href=\"#fail-fast\"><i>fail-fast<\/i><\/a>.\r\n     *\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     *\/\r\n    public ListIterator<E> listIterator(int index) {\r\n        if (index < 0 || index > size)\r\n            throw new IndexOutOfBoundsException(\"Index: \"+index);\r\n        return new ListItr(index);\r\n    }\r\n\r\n    \/**\r\n     * Returns a list iterator over the elements in this list (in proper\r\n     * sequence).\r\n     *\r\n     * <p>The returned list iterator is <a href=\"#fail-fast\"><i>fail-fast<\/i><\/a>.\r\n     *\r\n     * @see #listIterator(int)\r\n     *\/\r\n    public ListIterator<E> listIterator() {\r\n        return new ListItr(0);\r\n    }\r\n\r\n    \/**\r\n     * Returns an iterator over the elements in this list in proper sequence.\r\n     *\r\n     * <p>The returned iterator is <a href=\"#fail-fast\"><i>fail-fast<\/i><\/a>.\r\n     *\r\n     * @return an iterator over the elements in this list in proper sequence\r\n     *\/\r\n    public Iterator<E> iterator() {\r\n        return new Itr();\r\n    }\r\n\r\n    \/**\r\n     * An optimized version of AbstractList.Itr\r\n     *\/\r\n    private class Itr implements Iterator<E> {\r\n        int cursor;       \/\/ index of next element to return\r\n        int lastRet = -1; \/\/ index of last element returned; -1 if no such\r\n        int expectedModCount = modCount;\r\n\r\n        Itr() {}\r\n\r\n        public boolean hasNext() {\r\n            return cursor != size;\r\n        }\r\n\r\n        @SuppressWarnings(\"unchecked\")\r\n        public E next() {\r\n            checkForComodification();\r\n            int i = cursor;\r\n            if (i >= size)\r\n                throw new NoSuchElementException();\r\n            Object[] elementData = ArrayList.this.elementData;\r\n            if (i >= elementData.length)\r\n                throw new ConcurrentModificationException();\r\n            cursor = i + 1;\r\n            return (E) elementData[lastRet = i];\r\n        }\r\n\r\n        public void remove() {\r\n            if (lastRet < 0)\r\n                throw new IllegalStateException();\r\n            checkForComodification();\r\n\r\n            try {\r\n                ArrayList.this.remove(lastRet);\r\n                cursor = lastRet;\r\n                lastRet = -1;\r\n                expectedModCount = modCount;\r\n            } catch (IndexOutOfBoundsException ex) {\r\n                throw new ConcurrentModificationException();\r\n            }\r\n        }\r\n\r\n        @Override\r\n        @SuppressWarnings(\"unchecked\")\r\n        public void forEachRemaining(Consumer<? super E> consumer) {\r\n            Objects.requireNonNull(consumer);\r\n            final int size = ArrayList.this.size;\r\n            int i = cursor;\r\n            if (i >= size) {\r\n                return;\r\n            }\r\n            final Object[] elementData = ArrayList.this.elementData;\r\n            if (i >= elementData.length) {\r\n                throw new ConcurrentModificationException();\r\n            }\r\n            while (i != size && modCount == expectedModCount) {\r\n                consumer.accept((E) elementData[i++]);\r\n            }\r\n            \/\/ update once at end of iteration to reduce heap write traffic\r\n            cursor = i;\r\n            lastRet = i - 1;\r\n            checkForComodification();\r\n        }\r\n\r\n        final void checkForComodification() {\r\n            if (modCount != expectedModCount)\r\n                throw new ConcurrentModificationException();\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * An optimized version of AbstractList.ListItr\r\n     *\/\r\n    private class ListItr extends Itr implements ListIterator<E> {\r\n        ListItr(int index) {\r\n            super();\r\n            cursor = index;\r\n        }\r\n\r\n        public boolean hasPrevious() {\r\n            return cursor != 0;\r\n        }\r\n\r\n        public int nextIndex() {\r\n            return cursor;\r\n        }\r\n\r\n        public int previousIndex() {\r\n            return cursor - 1;\r\n        }\r\n\r\n        @SuppressWarnings(\"unchecked\")\r\n        public E previous() {\r\n            checkForComodification();\r\n            int i = cursor - 1;\r\n            if (i < 0)\r\n                throw new NoSuchElementException();\r\n            Object[] elementData = ArrayList.this.elementData;\r\n            if (i >= elementData.length)\r\n                throw new ConcurrentModificationException();\r\n            cursor = i;\r\n            return (E) elementData[lastRet = i];\r\n        }\r\n\r\n        public void set(E e) {\r\n            if (lastRet < 0)\r\n                throw new IllegalStateException();\r\n            checkForComodification();\r\n\r\n            try {\r\n                ArrayList.this.set(lastRet, e);\r\n            } catch (IndexOutOfBoundsException ex) {\r\n                throw new ConcurrentModificationException();\r\n            }\r\n        }\r\n\r\n        public void add(E e) {\r\n            checkForComodification();\r\n\r\n            try {\r\n                int i = cursor;\r\n                ArrayList.this.add(i, e);\r\n                cursor = i + 1;\r\n                lastRet = -1;\r\n                expectedModCount = modCount;\r\n            } catch (IndexOutOfBoundsException ex) {\r\n                throw new ConcurrentModificationException();\r\n            }\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Returns a view of the portion of this list between the specified\r\n     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If\r\n     * {@code fromIndex} and {@code toIndex} are equal, the returned list is\r\n     * empty.)  The returned list is backed by this list, so non-structural\r\n     * changes in the returned list are reflected in this list, and vice-versa.\r\n     * The returned list supports all of the optional list operations.\r\n     *\r\n     * <p>This method eliminates the need for explicit range operations (of\r\n     * the sort that commonly exist for arrays).  Any operation that expects\r\n     * a list can be used as a range operation by passing a subList view\r\n     * instead of a whole list.  For example, the following idiom\r\n     * removes a range of elements from a list:\r\n     * <pre>\r\n     *      list.subList(from, to).clear();\r\n     * <\/pre>\r\n     * Similar idioms may be constructed for {@link #indexOf(Object)} and\r\n     * {@link #lastIndexOf(Object)}, and all of the algorithms in the\r\n     * {@link Collections} class can be applied to a subList.\r\n     *\r\n     * <p>The semantics of the list returned by this method become undefined if\r\n     * the backing list (i.e., this list) is <i>structurally modified<\/i> in\r\n     * any way other than via the returned list.  (Structural modifications are\r\n     * those that change the size of this list, or otherwise perturb it in such\r\n     * a fashion that iterations in progress may yield incorrect results.)\r\n     *\r\n     * @throws IndexOutOfBoundsException {@inheritDoc}\r\n     * @throws IllegalArgumentException {@inheritDoc}\r\n     *\/\r\n    public List<E> subList(int fromIndex, int toIndex) {\r\n        subListRangeCheck(fromIndex, toIndex, size);\r\n        return new SubList(this, 0, fromIndex, toIndex);\r\n    }\r\n\r\n    static void subListRangeCheck(int fromIndex, int toIndex, int size) {\r\n        if (fromIndex < 0)\r\n            throw new IndexOutOfBoundsException(\"fromIndex = \" + fromIndex);\r\n        if (toIndex > size)\r\n            throw new IndexOutOfBoundsException(\"toIndex = \" + toIndex);\r\n        if (fromIndex > toIndex)\r\n            throw new IllegalArgumentException(\"fromIndex(\" + fromIndex +\r\n                                               \") > toIndex(\" + toIndex + \")\");\r\n    }\r\n\r\n    private class SubList extends AbstractList<E> implements RandomAccess {\r\n        private final AbstractList<E> parent;\r\n        private final int parentOffset;\r\n        private final int offset;\r\n        int size;\r\n\r\n        SubList(AbstractList<E> parent,\r\n                int offset, int fromIndex, int toIndex) {\r\n            this.parent = parent;\r\n            this.parentOffset = fromIndex;\r\n            this.offset = offset + fromIndex;\r\n            this.size = toIndex - fromIndex;\r\n            this.modCount = ArrayList.this.modCount;\r\n        }\r\n\r\n        public E set(int index, E e) {\r\n            rangeCheck(index);\r\n            checkForComodification();\r\n            E oldValue = ArrayList.this.elementData(offset + index);\r\n            ArrayList.this.elementData[offset + index] = e;\r\n            return oldValue;\r\n        }\r\n\r\n        public E get(int index) {\r\n            rangeCheck(index);\r\n            checkForComodification();\r\n            return ArrayList.this.elementData(offset + index);\r\n        }\r\n\r\n        public int size() {\r\n            checkForComodification();\r\n            return this.size;\r\n        }\r\n\r\n        public void add(int index, E e) {\r\n            rangeCheckForAdd(index);\r\n            checkForComodification();\r\n            parent.add(parentOffset + index, e);\r\n            this.modCount = parent.modCount;\r\n            this.size++;\r\n        }\r\n\r\n        public E remove(int index) {\r\n            rangeCheck(index);\r\n            checkForComodification();\r\n            E result = parent.remove(parentOffset + index);\r\n            this.modCount = parent.modCount;\r\n            this.size--;\r\n            return result;\r\n        }\r\n\r\n        protected void removeRange(int fromIndex, int toIndex) {\r\n            checkForComodification();\r\n            parent.removeRange(parentOffset + fromIndex,\r\n                               parentOffset + toIndex);\r\n            this.modCount = parent.modCount;\r\n            this.size -= toIndex - fromIndex;\r\n        }\r\n\r\n        public boolean addAll(Collection<? extends E> c) {\r\n            return addAll(this.size, c);\r\n        }\r\n\r\n        public boolean addAll(int index, Collection<? extends E> c) {\r\n            rangeCheckForAdd(index);\r\n            int cSize = c.size();\r\n            if (cSize==0)\r\n                return false;\r\n\r\n            checkForComodification();\r\n            parent.addAll(parentOffset + index, c);\r\n            this.modCount = parent.modCount;\r\n            this.size += cSize;\r\n            return true;\r\n        }\r\n\r\n        public Iterator<E> iterator() {\r\n            return listIterator();\r\n        }\r\n\r\n        public ListIterator<E> listIterator(final int index) {\r\n            checkForComodification();\r\n            rangeCheckForAdd(index);\r\n            final int offset = this.offset;\r\n\r\n            return new ListIterator<E>() {\r\n                int cursor = index;\r\n                int lastRet = -1;\r\n                int expectedModCount = ArrayList.this.modCount;\r\n\r\n                public boolean hasNext() {\r\n                    return cursor != SubList.this.size;\r\n                }\r\n\r\n                @SuppressWarnings(\"unchecked\")\r\n                public E next() {\r\n                    checkForComodification();\r\n                    int i = cursor;\r\n                    if (i >= SubList.this.size)\r\n                        throw new NoSuchElementException();\r\n                    Object[] elementData = ArrayList.this.elementData;\r\n                    if (offset + i >= elementData.length)\r\n                        throw new ConcurrentModificationException();\r\n                    cursor = i + 1;\r\n                    return (E) elementData[offset + (lastRet = i)];\r\n                }\r\n\r\n                public boolean hasPrevious() {\r\n                    return cursor != 0;\r\n                }\r\n\r\n                @SuppressWarnings(\"unchecked\")\r\n                public E previous() {\r\n                    checkForComodification();\r\n                    int i = cursor - 1;\r\n                    if (i < 0)\r\n                        throw new NoSuchElementException();\r\n                    Object[] elementData = ArrayList.this.elementData;\r\n                    if (offset + i >= elementData.length)\r\n                        throw new ConcurrentModificationException();\r\n                    cursor = i;\r\n                    return (E) elementData[offset + (lastRet = i)];\r\n                }\r\n\r\n                @SuppressWarnings(\"unchecked\")\r\n                public void forEachRemaining(Consumer<? super E> consumer) {\r\n                    Objects.requireNonNull(consumer);\r\n                    final int size = SubList.this.size;\r\n                    int i = cursor;\r\n                    if (i >= size) {\r\n                        return;\r\n                    }\r\n                    final Object[] elementData = ArrayList.this.elementData;\r\n                    if (offset + i >= elementData.length) {\r\n                        throw new ConcurrentModificationException();\r\n                    }\r\n                    while (i != size && modCount == expectedModCount) {\r\n                        consumer.accept((E) elementData[offset + (i++)]);\r\n                    }\r\n                    \/\/ update once at end of iteration to reduce heap write traffic\r\n                    lastRet = cursor = i;\r\n                    checkForComodification();\r\n                }\r\n\r\n                public int nextIndex() {\r\n                    return cursor;\r\n                }\r\n\r\n                public int previousIndex() {\r\n                    return cursor - 1;\r\n                }\r\n\r\n                public void remove() {\r\n                    if (lastRet < 0)\r\n                        throw new IllegalStateException();\r\n                    checkForComodification();\r\n\r\n                    try {\r\n                        SubList.this.remove(lastRet);\r\n                        cursor = lastRet;\r\n                        lastRet = -1;\r\n                        expectedModCount = ArrayList.this.modCount;\r\n                    } catch (IndexOutOfBoundsException ex) {\r\n                        throw new ConcurrentModificationException();\r\n                    }\r\n                }\r\n\r\n                public void set(E e) {\r\n                    if (lastRet < 0)\r\n                        throw new IllegalStateException();\r\n                    checkForComodification();\r\n\r\n                    try {\r\n                        ArrayList.this.set(offset + lastRet, e);\r\n                    } catch (IndexOutOfBoundsException ex) {\r\n                        throw new ConcurrentModificationException();\r\n                    }\r\n                }\r\n\r\n                public void add(E e) {\r\n                    checkForComodification();\r\n\r\n                    try {\r\n                        int i = cursor;\r\n                        SubList.this.add(i, e);\r\n                        cursor = i + 1;\r\n                        lastRet = -1;\r\n                        expectedModCount = ArrayList.this.modCount;\r\n                    } catch (IndexOutOfBoundsException ex) {\r\n                        throw new ConcurrentModificationException();\r\n                    }\r\n                }\r\n\r\n                final void checkForComodification() {\r\n                    if (expectedModCount != ArrayList.this.modCount)\r\n                        throw new ConcurrentModificationException();\r\n                }\r\n            };\r\n        }\r\n\r\n        public List<E> subList(int fromIndex, int toIndex) {\r\n            subListRangeCheck(fromIndex, toIndex, size);\r\n            return new SubList(this, offset, fromIndex, toIndex);\r\n        }\r\n\r\n        private void rangeCheck(int index) {\r\n            if (index < 0 || index >= this.size)\r\n                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));\r\n        }\r\n\r\n        private void rangeCheckForAdd(int index) {\r\n            if (index < 0 || index > this.size)\r\n                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));\r\n        }\r\n\r\n        private String outOfBoundsMsg(int index) {\r\n            return \"Index: \"+index+\", Size: \"+this.size;\r\n        }\r\n\r\n        private void checkForComodification() {\r\n            if (ArrayList.this.modCount != this.modCount)\r\n                throw new ConcurrentModificationException();\r\n        }\r\n\r\n        public Spliterator<E> spliterator() {\r\n            checkForComodification();\r\n            return new ArrayListSpliterator<E>(ArrayList.this, offset,\r\n                                               offset + this.size, this.modCount);\r\n        }\r\n    }\r\n\r\n    @Override\r\n    public void forEach(Consumer<? super E> action) {\r\n        Objects.requireNonNull(action);\r\n        final int expectedModCount = modCount;\r\n        @SuppressWarnings(\"unchecked\")\r\n        final E[] elementData = (E[]) this.elementData;\r\n        final int size = this.size;\r\n        for (int i=0; modCount == expectedModCount && i < size; i++) {\r\n            action.accept(elementData[i]);\r\n        }\r\n        if (modCount != expectedModCount) {\r\n            throw new ConcurrentModificationException();\r\n        }\r\n    }\r\n\r\n    \/**\r\n     * Creates a <em><a href=\"Spliterator.html#binding\">late-binding<\/a><\/em>\r\n     * and <em>fail-fast<\/em> {@link Spliterator} over the elements in this\r\n     * list.\r\n     *\r\n     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},\r\n     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.\r\n     * Overriding implementations should document the reporting of additional\r\n     * characteristic values.\r\n     *\r\n     * @return a {@code Spliterator} over the elements in this list\r\n     * @since 1.8\r\n     *\/\r\n    @Override\r\n    public Spliterator<E> spliterator() {\r\n        return new ArrayListSpliterator<>(this, 0, -1, 0);\r\n    }\r\n\r\n    \/** Index-based split-by-two, lazily initialized Spliterator *\/\r\n    static final class ArrayListSpliterator<E> implements Spliterator<E> {\r\n\r\n        \/*\r\n         * If ArrayLists were immutable, or structurally immutable (no\r\n         * adds, removes, etc), we could implement their spliterators\r\n         * with Arrays.spliterator. Instead we detect as much\r\n         * interference during traversal as practical without\r\n         * sacrificing much performance. We rely primarily on\r\n         * modCounts. These are not guaranteed to detect concurrency\r\n         * violations, and are sometimes overly conservative about\r\n         * within-thread interference, but detect enough problems to\r\n         * be worthwhile in practice. To carry this out, we (1) lazily\r\n         * initialize fence and expectedModCount until the latest\r\n         * point that we need to commit to the state we are checking\r\n         * against; thus improving precision.  (This doesn't apply to\r\n         * SubLists, that create spliterators with current non-lazy\r\n         * values).  (2) We perform only a single\r\n         * ConcurrentModificationException check at the end of forEach\r\n         * (the most performance-sensitive method). When using forEach\r\n         * (as opposed to iterators), we can normally only detect\r\n         * interference after actions, not before. Further\r\n         * CME-triggering checks apply to all other possible\r\n         * violations of assumptions for example null or too-small\r\n         * elementData array given its size(), that could only have\r\n         * occurred due to interference.  This allows the inner loop\r\n         * of forEach to run without any further checks, and\r\n         * simplifies lambda-resolution. While this does entail a\r\n         * number of checks, note that in the common case of\r\n         * list.stream().forEach(a), no checks or other computation\r\n         * occur anywhere other than inside forEach itself.  The other\r\n         * less-often-used methods cannot take advantage of most of\r\n         * these streamlinings.\r\n         *\/\r\n\r\n        private final ArrayList<E> list;\r\n        private int index; \/\/ current index, modified on advance\/split\r\n        private int fence; \/\/ -1 until used; then one past last index\r\n        private int expectedModCount; \/\/ initialized when fence set\r\n\r\n        \/** Create new spliterator covering the given  range *\/\r\n        ArrayListSpliterator(ArrayList<E> list, int origin, int fence,\r\n                             int expectedModCount) {\r\n            this.list = list; \/\/ OK if null unless traversed\r\n            this.index = origin;\r\n            this.fence = fence;\r\n            this.expectedModCount = expectedModCount;\r\n        }\r\n\r\n        private int getFence() { \/\/ initialize fence to size on first use\r\n            int hi; \/\/ (a specialized variant appears in method forEach)\r\n            ArrayList<E> lst;\r\n            if ((hi = fence) < 0) {\r\n                if ((lst = list) == null)\r\n                    hi = fence = 0;\r\n                else {\r\n                    expectedModCount = lst.modCount;\r\n                    hi = fence = lst.size;\r\n                }\r\n            }\r\n            return hi;\r\n        }\r\n\r\n        public ArrayListSpliterator<E> trySplit() {\r\n            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;\r\n            return (lo >= mid) ? null : \/\/ divide range in half unless too small\r\n                new ArrayListSpliterator<E>(list, lo, index = mid,\r\n                                            expectedModCount);\r\n        }\r\n\r\n        public boolean tryAdvance(Consumer<? super E> action) {\r\n            if (action == null)\r\n                throw new NullPointerException();\r\n            int hi = getFence(), i = index;\r\n            if (i < hi) {\r\n                index = i + 1;\r\n                @SuppressWarnings(\"unchecked\") E e = (E)list.elementData[i];\r\n                action.accept(e);\r\n                if (list.modCount != expectedModCount)\r\n                    throw new ConcurrentModificationException();\r\n                return true;\r\n            }\r\n            return false;\r\n        }\r\n\r\n        public void forEachRemaining(Consumer<? super E> action) {\r\n            int i, hi, mc; \/\/ hoist accesses and checks from loop\r\n            ArrayList<E> lst; Object[] a;\r\n            if (action == null)\r\n                throw new NullPointerException();\r\n            if ((lst = list) != null && (a = lst.elementData) != null) {\r\n                if ((hi = fence) < 0) {\r\n                    mc = lst.modCount;\r\n                    hi = lst.size;\r\n                }\r\n                else\r\n                    mc = expectedModCount;\r\n                if ((i = index) >= 0 && (index = hi) <= a.length) {\r\n                    for (; i < hi; ++i) {\r\n                        @SuppressWarnings(\"unchecked\") E e = (E) a[i];\r\n                        action.accept(e);\r\n                    }\r\n                    if (lst.modCount == mc)\r\n                        return;\r\n                }\r\n            }\r\n            throw new ConcurrentModificationException();\r\n        }\r\n\r\n        public long estimateSize() {\r\n            return (long) (getFence() - index);\r\n        }\r\n\r\n        public int characteristics() {\r\n            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;\r\n        }\r\n    }\r\n\r\n    @Override\r\n    public boolean removeIf(Predicate<? super E> filter) {\r\n        Objects.requireNonNull(filter);\r\n        \/\/ figure out which elements are to be removed\r\n        \/\/ any exception thrown from the filter predicate at this stage\r\n        \/\/ will leave the collection unmodified\r\n        int removeCount = 0;\r\n        final BitSet removeSet = new BitSet(size);\r\n        final int expectedModCount = modCount;\r\n        final int size = this.size;\r\n        for (int i=0; modCount == expectedModCount && i < size; i++) {\r\n            @SuppressWarnings(\"unchecked\")\r\n            final E element = (E) elementData[i];\r\n            if (filter.test(element)) {\r\n                removeSet.set(i);\r\n                removeCount++;\r\n            }\r\n        }\r\n        if (modCount != expectedModCount) {\r\n            throw new ConcurrentModificationException();\r\n        }\r\n\r\n        \/\/ shift surviving elements left over the spaces left by removed elements\r\n        final boolean anyToRemove = removeCount > 0;\r\n        if (anyToRemove) {\r\n            final int newSize = size - removeCount;\r\n            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {\r\n                i = removeSet.nextClearBit(i);\r\n                elementData[j] = elementData[i];\r\n            }\r\n            for (int k=newSize; k < size; k++) {\r\n                elementData[k] = null;  \/\/ Let gc do its work\r\n            }\r\n            this.size = newSize;\r\n            if (modCount != expectedModCount) {\r\n                throw new ConcurrentModificationException();\r\n            }\r\n            modCount++;\r\n        }\r\n\r\n        return anyToRemove;\r\n    }\r\n\r\n    @Override\r\n    @SuppressWarnings(\"unchecked\")\r\n    public void replaceAll(UnaryOperator<E> operator) {\r\n        Objects.requireNonNull(operator);\r\n        final int expectedModCount = modCount;\r\n        final int size = this.size;\r\n        for (int i=0; modCount == expectedModCount && i < size; i++) {\r\n            elementData[i] = operator.apply((E) elementData[i]);\r\n        }\r\n        if (modCount != expectedModCount) {\r\n            throw new ConcurrentModificationException();\r\n        }\r\n        modCount++;\r\n    }\r\n\r\n    @Override\r\n    @SuppressWarnings(\"unchecked\")\r\n    public void sort(Comparator<? super E> c) {\r\n        final int expectedModCount = modCount;\r\n        Arrays.sort((E[]) elementData, 0, size, c);\r\n        if (modCount != expectedModCount) {\r\n            throw new ConcurrentModificationException();\r\n        }\r\n        modCount++;\r\n    }\r\n}\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
jdk 7 ArrayList\u6e90\u7801 jdk 8 ArrayList\u6e90\u7801<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[46],"class_list":["post-1199","post","type-post","status-publish","format-standard","hentry","category-java-code","tag-java"],"_links":{"self":[{"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts\/1199"}],"collection":[{"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1199"}],"version-history":[{"count":1,"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts\/1199\/revisions"}],"predecessor-version":[{"id":1200,"href":"https:\/\/qaqaq.top\/index.php?rest_route=\/wp\/v2\/posts\/1199\/revisions\/1200"}],"wp:attachment":[{"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1199"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1199"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/qaqaq.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1199"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}