Java常用类_数组和ArrayList类

数组和ArrayList类

---

1 数组

1.1 创建数组

创建数组格式： dataType[] arrayName = new dataType[arraySize];

double[] array = new double[10];

数组一旦创建其大小是不能改的。

1.2 For-Each 循环

该新循环方法是从JDK 1.5开始引进的，可以不需要下标遍历数组。

        double[] myList = {1.9, 2.9, 3.4, 3.5};
        for(double element : myList){
            System.out.print(element + " "); // 遍历数组
        }
OUT: 1.9 2.9 3.4 3.5 

        Random r = new Random();
        int[] array = new int[10];
        for(int element : array ){
            element = r.nextInt(10); // 但是这样并不会给数组赋值，显示的结果还是未初始化的数组
        }
OUT: 0 0 0 0 0 0 0 0 0 0

1.3 Arrays 类

调用java.util.Arrays实现对数组的操作
具体的方法：

• public static void fill(int[] a, int val) ： 给数组赋值，其他数据类型均可；
• public static void sort(Object[] a) ： 数组升序排序，其他数据类型均可；
  • 如果是数值，sort默认按照升序从小到大。
  • 如果是字符串，sort默认按照字母升序。
  • 如果是自定义类型，那么这个自定义的类需要有Comparable或者Comparator接口的支持。
• public static boolean equals(long[] a, long[] a2) ： 当两个数组数量相同且相应元素也是相等的，则两个数组是相等的，如果对应的不相等即使数量相同返回的也是false；
• public static String toString(int[] a) ： 将数组输出成为字符串，以特定形式输出，其他类型均可；

          int[] array1 = {1,0,1,0,1};
          String str = Arrays.toString(array1);
          System.out.println("OUT: "+str);
  OUT: [1, 0, 1, 0, 1]

• public static int binarySearch(Object[] a, Object key) ： 用二分查找算法在给定数组中搜索给定值，返回搜索键的索引，如果不在数组中就返回 (-(插入点) - 1)。数组在调用前必须排序好；

          Random r = new Random();
          int[] array = new int[10];
          for (int i = 0; i < array.length; i++) {
              array[i] = r.nextInt(7);
              System.out.print(array[i]+ " ");
          }
          Arrays.sort(array);
          int index = Arrays.binarySearch(array,4);
          System.out.println("index: "+index);
  
  OUT：0 0 5 5 0 5 1 4 3 6 index: 5

  2 ArrayList

2.1 ArrayList创建及应用

ArrayList实现

• 1. 创建

     ArrayList<Integer> array = new ArrayList<>(10); // initialCapacity 为10，不写则为0

• 2. 常见方法
     增删改查等常规方法。

     // 简单的摘录几个
         public void add(int index, E element) {}
         public E remove(int index) {}
         public E set(int index, E element) {}
         public E get(int index) {}

     2.2 ArrayList类简单解析

     ArrayList类不同于数组的关键在于ArrayList数组的长度是可变的，ArrayList类的构造函数可以传分配多大的内存的参数，该参数作为初始容量(initialCapacity)，当添加元素的个数(size)等于容量时，会重新开辟一个更大的空间存放数组，执行的操作是grow()方法(私有方法)。

     // 1. 扩容
     int newCapacity = oldCapacity + (oldCapacity >> 1);
     // 2. 复制到新的存储空间
     this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));

     扩容操作因为包含复制到新空间的步骤，所以会使add()的时间复杂度变成O(n)，但是其实只有当恰好满的时候才会触发扩容操作。所以更应该算的是均摊复杂度，也就是O[(n-1+n)/(n+1)]，最后的均摊时间复杂度是O(1)。

当删除元素的时候，可能会伴有缩容操作。要注意的是，不能是只要size恰好小于当前的capacity就缩容，这样可能会造成扩容缩容操作的连续震荡。（比如实现缩容后，又要扩容操作，就需要重新拷贝）。可以参考如下写法：

// 当size是capacity的1/4时，再缩容到原capacity的一半。
if((size == data.length/4) && (data.length/2 != 0)){
    resize(data.length/2);
}

2.3 ArrayList类时间复杂度分析

ArrayList类和链表虽同为线性结构，但是个别方法的时间复杂度并不相同。

• 在指定位置上插入元素：时间复杂度 : O(n)
• 删除指定元素：时间复杂度 : O(n)
• 在指定位置上更改元素：时间复杂度 : O(1)
• 查找是否包含元素e(contains)：时间复杂度 : O(n)
• 根据索引查找元素(get)：时间复杂度 : O(1)

2.4 ArrayList类总结

在ArrayList中，底层数组存/取元素效率非常的高(get/set)，时间复杂度是O(1)，而查找，插入和删除元素效率似乎不太高，时间复杂度为O(n)。
当我们ArrayList里有大量数据时，这时候去频繁插入/删除元素会触发底层数组频繁拷贝，效率不高，还会造成内存空间的浪费，LinkedList可以解决这种问题。HashMap可以更好的改进查找元素效率不高的问题。