ArrayList.java初探

发表于 | 分类于 | | 本文总阅读量
字数统计: 2,182 | 阅读时长 ≈ 11

前言

妹有前言

什么是Array？什么是ArrayList？我们该用哪个？

        Array是一个很常见的数据结构，很多语言都内置了Array。声明一个Array的同时就必须要进行实例化(初始化)也就是确定其Array长度，它只能存储同一数据类型的数据。

1
2
3
4
5
//声明并初始化Array

int[] a = new int[10];

int b[] = {1,2,3,...};

        ArrayList可以说是Array的企业版(haha)，它也是常见的数据结构。不需要直接声明后立即初始化，长度是根据需要而改变的。它可以存放不同类型的数据，但它存储的并不是int,float,double…，而是Integer,Float,Double…(但JAVA中存在自动装箱，所以并不用担心)

1
2
3
4
5
//声明并初始化ArrayList(并不需要同时进行)

ArrayList al = new ArrayList();

al.add(10,20,30,40,...);

        Array的性能是要优于ArrayList的，但因为数组在存储数据时是按顺序存储的，存储数据的内存也是连续的，所以它的特点就是寻址读取数据比较容易，插入和删除是比较困难的。加上Array只能存储同一种数据类型的数据且长度是固定，so,当能确定长度且数据类型一致的时候我们可以使用Array,其他时候则使用ArrayList。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//ArrayList序列号，用于判断序列化文件是否已经失效
   private static final long serialVersionUID = 8683452581122892189L;

   /**
    * Default initial capacity.
    */
//ArrayList初始容量为10
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * Shared empty array instance used for empty instances.
    */
//指定该ArrayList容量为0时，返回该空数组。
   private static final Object[] EMPTY_ELEMENTDATA = {};

   /**
    * Shared empty array instance used for default sized empty instances. We
    * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
    * first element is added.
    */
//一个空array实例，如果你调用的是无参的Constructor时，返回的就是该array(默认返回！)
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   /**
    * The array buffer into which the elements of the ArrayList are stored.
    * The capacity of the ArrayList is the length of this array buffer. Any
    * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    * will be expanded to DEFAULT_CAPACITY when the first element is added.
    */
//为什么说ArrayList是array的企业版，其实ArrayList就是把array存储在内，并提供了一些对array进行操作的方法，elementData就是我们ArrayList的容器。elemntdata也叫数组缓冲区。
   transient Object[] elementData; // non-private to simplify nested class access

   /**
    * The size of the ArrayList (the number of elements it contains).
    *
    * @serial
    */
//ArrayList世纪存储的数据数量
   private int size;

ArrayList Constructors

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
   /**
    * Constructs an empty list with the specified initial capacity.
    *
    * @param  initialCapacity  the initial capacity of the list
    * @throws IllegalArgumentException if the specified initial capacity
    *         is negative
    */
//创建一个具有初始容量的空list
   public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {	//大于零就创建一个基于initialCapacity大小的array
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {	//等于零就是创建一个空array
           this.elementData = EMPTY_ELEMENTDATA;
       } else { //非法检测
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       }
   }

   /**
    * Constructs an empty list with an initial capacity of ten.
    */
//创建一个空ArrayList,长度为0.当元素第一次被add时，扩容至默认容量10
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }

   /**
    * Constructs a list containing the elements of the specified
    * collection, in the order they are returned by the collection's
    * iterator.
    *
    * @param c the collection whose elements are to be placed into this list
    * @throws NullPointerException if the specified collection is null
    */
//创建一个包含Collection的ArrayList，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
   public ArrayList(Collection<? extends E> c) {
       elementData = c.toArray();
       if ((size = elementData.length) != 0) {
           // c.toArray might (incorrectly) not return Object[] (see 6260652)
           if (elementData.getClass() != Object[].class)
               elementData = Arrays.copyOf(elementData, size, Object[].class);
       } else {
           // replace with empty array.
           this.elementData = EMPTY_ELEMENTDATA;
       }
   }

ArrayList add()

ArrayList在每一次添加数据时，都会执行ensureCapacityInternal()检查是否超出数组容 量

这里的扩容有许多细节可以详述，我们留到下一篇博文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
   /**
    * Appends the specified element to the end of this list.
    *
    * @param e element to be appended to this list
    * @return <tt>true</tt> (as specified by {@link Collection#add})
    */
//添加指定的元素到ArrayList，位于位置最后。
   public boolean add(E e) {
	// 只有当size+1 > 数组.length时才会执行扩容
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       elementData[size++] = e; //通过下标赋值
       return true;
   }
//将指定的元素插入此ArrayList中的指定位置。
   public void add(int index, E element) {
       rangeCheckForAdd(index);//检查形式参数index是否合法。
	
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       //arraycopy()将index下标到末尾的数据右移一位↓
	//[1,2,3,4,5,6,7,0,0,0]①
	//[1,2,2,3,4,5,6,7,0,0]②
	System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
	//[1,x,2,3,4,5,6,7,0,0]③ x为element
       elementData[index] = element;
       size++;
   }

ArrayList Remove()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
   /**
    * Removes the element at the specified position in this list.
    * Shifts any subsequent elements to the left (subtracts one from their
    * indices).
    *
    * @param index the index of the element to be removed
    * @return the element that was removed from the list
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
//将指定的元素删除
   public E remove(int index) {
       rangeCheck(index);//检查形式参数index是否合法

       modCount++;
       E oldValue = elementData(index);	//需要删除的元素

       int numMoved = size - index - 1;	
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);		//整个左移numMoved个下标单位
       elementData[--size] = null; // clear to let GC do its work(让最后一个下标元素为空)

       return oldValue;
   }


   /**
    * Removes the first occurrence of the specified element from this list,
    * if it is present.  If the list does not contain the element, it is
    * unchanged.  More formally, removes the element with the lowest index
    * <tt>i</tt> such that
    * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
    * (if such an element exists).  Returns <tt>true</tt> if this list
    * contained the specified element (or equivalently, if this list
    * changed as a result of the call).
    *
    * @param o element to be removed from this list, if present
    * @return <tt>true</tt> if this list contained the specified element
    */
//删除在ArrayList中首次出现的元素
   public boolean remove(Object o) {
       if (o == null) {	//由于ArrayList一样可以存储对象，所以还要进行null值判断
           for (int index = 0; index < size; index++)
               if (elementData[index] == null) {
                   fastRemove(index);	// fastRemove()进行删除
                   return true;
               }
       } else {
           for (int index = 0; index < size; index++)
               if (o.equals(elementData[index])) {
                   fastRemove(index);// fastRemove()进行删除
                   return true;
               }
       }
       return false;
   }

   /*
    * Private remove method that skips bounds checking and does not
    * return the value removed.
    */
//调用arrayCopy()进行左移并最后一位元素进行留空
   private void fastRemove(int index) {
       modCount++;
       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null; // clear to let GC do its work
   }

   /**
    * Removes from this list all of the elements whose index is between
    * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
    * Shifts any succeeding elements to the left (reduces their index).
    * This call shortens the list by {@code (toIndex - fromIndex)} elements.
    * (If {@code toIndex==fromIndex}, this operation has no effect.)
    *
    * @throws IndexOutOfBoundsException if {@code fromIndex} or
    *         {@code toIndex} is out of range
    *         ({@code fromIndex < 0 ||
    *          fromIndex >= size() ||
    *          toIndex > size() ||
    *          toIndex < fromIndex})
    */
//删除从索引头fromIndex(包括)到toIndex(不包括)之间的元素
   protected void removeRange(int fromIndex, int toIndex) {
       modCount++;
       int numMoved = size - toIndex;	//被删除的索引范围后的元素个数
       System.arraycopy(elementData, toIndex, elementData, fromIndex,
                        numMoved);		//左移numMoved个单位

       // clear to let GC do its work
       int newSize = size - (toIndex-fromIndex);	//新array的长度
       for (int i = newSize; i < size; i++) {		
           elementData[i] = null;		//原本的下标元素置为null，好让JVM的垃圾回收机制干活	
       }
       size = newSize;	
   }

ArrayList set()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   /**
    * Replaces the element at the specified position in this list with
    * the specified element.
    *
    * @param index index of the element to replace
    * @param element element to be stored at the specified position
    * @return the element previously at the specified position
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
//用指定的元素替换相应下标的元素
   public E set(int index, E element) {
       rangeCheck(index);//检查形式参数index是否合法
	//记录被替换的oldValue
       E oldValue = elementData(index);
       elementData[index] = element;	//实现替换
       return oldValue;	//返回oldValue
   }

为什么这里要返回一个oldValue?没什么，只是List接口给set方法的一个API设计而已。set方法严格遵守了这个约定。ps:感谢ber哥

ArrayList get()

1
2
3
4
5
6
7
8
9
10
11
12
13
14

   /**
    * Returns the element at the specified position in this list.
    *
    * @param  index index of the element to return
    * @return the element at the specified position in this list
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
//返回在ArrayList中指定的元素
   public E get(int index) {
       rangeCheck(index);//检查形式参数index是否合法

       return elementData(index);
   }

最后

        通过阅读ArrayList的源码后才发现，JDK设计的精妙。就像扩容机制一样，保证要存多少个元素，就只分配多少空间资源，保证空间资源不被浪费。这应该只是冰山一角。。。。

        额哈哈哈哈哈