【Java数据结构】ArrayList详解_java中的 arraylist 是什么结构

ArrayList是什么？

       ArrayList 是Java集合框架中的一个类，底层使用的数据结构就是顺序表，它实现了List接口，提供了动态数组的功能，ArrayList可以根据需要自动进行扩容，允许存储任意类型的对象。

一、ArrayList的设计思想

1.底层设计

       ArrayList底层是一个数组，通过一段连续的存储空间存储数据，各元素按照插入的顺序进行存储，允许出现重复的元素。依次向ArrayList中添加1~10，则底层就是存储在如下图类似的数组中。

       ArrayList使用了泛型的设计思想，他可以存储任何类型的数据，包括自定义类型、基本数据类型对应的包装类等。
       对于Java中的集合，都提供了泛型的设计思想，泛型还可以约束集合中的存储数据的类型，如果不指定一个数据类型，则集合中可以存储任意类型的数据，这样就不能保证集合中元素的类型一致性，可能会发生大量的异常，比如：字符串类型和数据类型比较大小、字符串类型进行运算等。

2.扩容机制

       ArrayList底层是一个动态数组，查看源码可发现，当使用无参构造申请一个ArrayList对象时，这时系统还未给list对象分配内存空间，即数组长度为零。当添加第一个元素时，由于此时数组长度为0，就会触发扩容机制，首次申请长度为10的数组；当数组中有效元素的个数为10时，如果再向list集合中添加元素，数组长度不够，则又会触发扩容机制，此时扩容为1.5倍扩容。

ArrayList中查看数组的初始长度源码：

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
}
1
2
3
4
5
6
7
8
9
10
11

       由此得知数组的默认初始容量为10

ArrayList中扩容函数源码：

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//注释1
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//注释2
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

       根据注释1可发现，ArrayList中数组扩容是进行1.5倍扩容。

       这里你会产生疑惑，数组不是定长的吗？为什么可以发生扩容？接下来将对此做简答：
       根据注释2可发现，数组进行扩容是，是申请一个新的数组，然后将原始数据拷贝到新数组中，让新数组作为ArrayList的数组。这样就产生了数组可变的假象，实际上是换了一个原数组1.5倍大的新数组。
       由此我们可以得出结论，当存储大量数据时，采用ArrayList作为容器，在进行扩容时，会发生大量的移动元素情况，这样会使程序的运行效率大大降低。

3.ArrayList类图

       认识了ArrayList的存储模式，再来看一看他的关系结构，ArrayList是一个普通的类，可以实例化对象，它实现了多个接口，如下图所示。

• ArrayList继承了AbstractList抽象类，实现了List接口，继承了其中多种方法，在ArrayList本类中不用再额外实现了，这样就更能体现继承的优势；
• ArrayList实现了RandomAccess接口，该接口只用声明，不用实现别的方法，代表ArrayList类可以支持随机访问；
• ArrayList实现了Cloneable接口，该接口只用声明，不用实现别的方法,代表ArrayList类可以clone；
• ArrayList实现了Serializable接口，该接口只用声明，不用实现别的方法，表明给类可以被序列化；
• ArrayList间接实现了Iterable接口，表明该类可以使用迭代器进行遍历。

二、ArrayList的基本方法及使用

       要想使用ArrayList集合，就需要先认识系统给咱们提供的API，ArrayList是在java.util包下的集合，使用时需要进行导包。

1.构造方法

       ArrayList类主要提供了三种构造方法，无参构造、传入数组初始大小的构造方法、还可以传入一个对象，该对象必须实现了Collection接口。
       注意：在进行实例化对象时，一定要指明参数的类型，否则集合中就可以存储任意类型的数据了，对于后期的维护成本较高，稍不注意还可使其发生错误

实例化对象简单使用：

public static void main(String[] args) {
        //无参构造方法，未添加元素时，数组长度为0，
        //当添加第一个元素时，初始化数组长度为10
        ArrayList<Integer> list1 = new ArrayList<>();
        //实例化对象时指定数组初始长度为 5
        ArrayList<Integer> list2 = new ArrayList<>(5);
        //实例化对象时，利用其他 Collection 构建 ArrayList
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(6);
        ArrayList<Integer> list3 = new ArrayList<>(linkedList);
        list3.add(8);
        //由此可知，当传入一个集合时，会将Collection集合中的元素依次存入ArrayList中
        for (Integer i : list3) {
            System.out.print(i + " ");//6  8
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.常用方法

       上面的类图中可以看出，ArrayList类继承了很多类也实现了众多接口，因此也继承了其中的方法，在此处只介绍ArrayList中常用的方法。

添加元素

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(2);//尾插2
        System.out.println(list.toString());// [2]
        list.add(0,1);//0下标插入1
        System.out.println(list.toString());// [1, 2]

        //Collection接口的子类
        List<Integer> list2 = new LinkedList<>();
        list2.add(3);
        list2.add(4);

        list.addAll(list2);//将list2集合中的元素尾插到list中
        System.out.println(list.toString());// [1, 2, 3, 4]
        list.addAll(1,list2);//将list2集合中的元素从1下标插入list中
        System.out.println(list.toString());// [1, 3, 4, 2, 3, 4]
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

删除元素

public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(2);
        list.add(1);

        //删除下标为0的元素,并返回该元素
        int n = list.remove(0);
        System.out.println(n);// 1
        System.out.println(list.toString());// [2, 3, 2, 1]

        //删除第一个2
        //通过显示装箱，将2数字包装成对应的包装类
        boolean result = list.remove(new Integer(2));
        System.out.println(result);// true
        System.out.println(list.toString());// [3, 2, 1]

        //清空元素
        list.clear();
        System.out.println(list.toString());// []
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

其他方法

public static void main(String[] args) {
        ArrayList<Integer> = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(1);
        list.add(2);
        //获取1下标的元素
        System.out.println(list.get(1));//2
        //设置0下标的元素为2
        System.out.println(list.set(0, 2));//1
        //判断集合中是否存在元素5
        System.out.println(list.contains(5));//false
        //返回第一个2出现的位置
        System.out.println(list.indexOf(2));//0
        //返回最后一次出现2的位置
        System.out.println(list.lastIndexOf(2));//4

        //截取0~3位置的元素
        List<Integer> sub = list.subList(0,3);
        System.out.println(sub.toString());// [2, 2, 3]
        System.out.println(list.toString());// [2, 2, 3, 1, 2]
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

List< E > subList(int fromIndex, int toIndex)方法

注意： 使用 subList() 方法截取时，实际上是fromIndex、 toIndex两个下标引用了原数组的空间，在对截取的集合进行修改时，也会影响原ArrayList中的值。

//List<E> subList(int fromIndex, int toIndex)方法
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        //截取前三个元素
        List<Integer> sub = list.subList(0,3);
        System.out.println(sub.toString());// [1, 2, 3]
        //截取的集合中的元素全修改为8
        for (int i = 0; i < sub.size(); i++) {
            sub.set(i,8);
        }
        System.out.println(sub.toString());// [8, 8, 8]
        //这里可以看出，list集合中的元素也被修改了
        System.out.println(list.toString());// [8, 8, 8, 4, 5]
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

小结

通过这篇文章，应该了解到一下内容：

• ArrayList是什么？
• ArrayList的设计思想？
• ArrayList的如何使用？

链接: gitee获取代码

如何度过不会重来的今天？
每一天都是人生限定，每一天都值得100%的努力。