List

1. Collections

Collections 是java 集合的根接口，Colleciton代表了一类Object的集合，也就是元素。Collection 并没有直接实现，而是通过其他的 Set 或者List 来决定更详细的功能。 Collection 只是定义了结合的一些常用接口方法，但是对于借口中的具体实现并没有规定， 元素是否重复， 元素是否有序，元素是否可以包含Null 这些都有没有做出要求， 具体还要看其实现类。

2. List

List 也是一个接口，它直接继承了 Collection.

List 则限制了当前集合是一个有序的集合。 这个接口的实现类， 用户可以精确的控制元素的插入位置，并且通过 元素的 角标来直接访问元素。

集合中的元素是可重复的，并且也是可空的。

List 提供了一个特殊的迭代器——ListIterator . 它支持除了 Iterator接口之外双向访问功能——可以在迭代的时候进行插入和替换。 同时也支持从一个固定位置开始进行迭代。

基于List的数据结构： 查找元素会比较耗费时间，

2.1 List的静态工厂方法

通过工厂方法创建出来的 List 有以下特征：

1. 结构不可变，集合中的元素不能添加，删除、以及替换，但是允许元素自己可变。
2. 不能含有 空元素。
3. 如果所有元素可系列化，那么集合也可以序列化。
4. 创建集合时元素是什么顺序，那么创建后就是什么顺序。
5. 集合的判断是基于其内容的，因为工厂方法可能重复使用相同的list。

3. ArrayList

ArrayList 和 Vector 是相似的，

Arraylist 不是线程安全的， 但是Vectory是线程安全的。 Arraylis的容量是自增长的， 如果不断的往ArrayList 中添加元素，那么到达容量之后，Arraylist会自己进行扩容。

Arraylist在添加大量元素之前调用 ensureCapacity方法可以避免在添加过程中多次进行扩容，从而提高效率。

如果多个线程都想操作Arraylist ,可以通过使用 同步锁或者 通过调用Collections.synchronizedList 方法来创建一个同步的Arraylist。

通过Arraylist创建迭代器之后，如果不是i通过 迭代器的删除或者添加方法来修改元素，那么迭代器会产生并发修改异常。但是并发修改异常在这个条件下也不是不然发生的， 不要想通过并发修改异常来判断是否有其他线程修改了当前 集合。

3.1Arraylist 源码解读

3.1.1 一些静态特性

1. Arraylist默认容量为10
2. 空的Arraylist使用相同的空数组
3. Arraylist的元素实际上是存储在 名字叫：elementData的数组中

3.1.2 Arraylist源码分析

Arraylist中的get,set方法必须要确定不超过当前元素数量，否则会直接抛出异常。

1. add方法分析

   public void add(int index, E element) {
       if (index > size || index < 0)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
       elementData[index] = element;
       size++;
   }
   

   每次添加元素之前，首先会检查当前数组的容量是否够用，如果不够用，那么就需要针对这个数组进行扩容。

   1. 检查容量

      如果当前elementData数组中的元素是满的，那么添加就需要进行一次扩容。 具体的是调用grow()方法。

          private void grow(int minCapacity) {
              // overflow-conscious code
              int oldCapacity = elementData.length;
              int newCapacity = oldCapacity + (oldCapacity >> 1);  //正常情况下，每次增加上一次容量的1/2,
              if (newCapacity - minCapacity < 0)
                  newCapacity = minCapacity;//如果如果还不够，那么就直接使用需要的容量。
              if (newCapacity - MAX_ARRAY_SIZE > 0)
                  newCapacity = hugeCapacity(minCapacity); //如果最大还大于数组最大容量，那么只能使用数组最大容量。
              
              elementData = Arrays.copyOf(elementData, newCapacity); //进行数组复制将旧元素复制到新的数组中。
          }
      

2. 元素查找

   这里注意， 如果是非空元素，使用的是元素的equals方法，如果需要特殊判断，那么就需要自己重写equals方法。 或者可以通过重写equals方法，来查找到相同属性的元素。

   public int indexOf(Object o) {
           if (o == null) {
               for (int i = 0; i < size; i++)
                   if (elementData[i]==null)
                       return i;
           } else {
               for (int i = 0; i < size; i++)
                   if (o.equals(elementData[i]))
                       return i;
           }
           return -1;
       }
   

**总的来说，Arraylist 是线程非安全的，基于数组实现的一个集合。Arraylist每一次插入和删除指定位置的元素，是比较耗时的（因为这样每次都要进行一次数组的复制），但是如果知道元素位置，那么查找就会很方便。 避免频繁的插入和删除元素，如果必须这样做，那么就要考虑使用其他的集合进行代替。     **