【Java集合-3】ArrayList简析

待我称王封你为后i 2023-10-18 21:37 25阅读 0赞

Java集合03 ArrayList简析

  • 1 ArrayList说明
    • 1.1 ArrayList简介
    • ArrayList继承关系
    • 1.2 ArrayList数据结构
    • 1.3 ArrayList构造函数
    • 1.4 ArrayList的API
  • 2 ArrayList常用操作
    • 2.1 ArrayList遍历
    • 2.2 ArrayList排序
    • 2.3 ArrayList删除元素
  • 3 ArrayList部分方法源码(基于JDK1.8)
    • 3.1 get(int index)
    • 3.2 add(E e)
    • 3.3 remove(Object o)
    • 3.4 addAll(Collection<? extends E> c)

在前面的集合框架那一章中,简单总结了Java集合的架构,List是Collection下的一大分支,而ArrayList又是List中最为常用的。本章将对ArrayList做一个总结,以供将来回顾之用。

1 ArrayList说明

1.1 ArrayList简介

ArrayList是一个数组队列,相当于动态数组。与Java中的数组相比,它的容量能动态增长。

  1. ArrayList 是一个数组队列,继承了AbstractList,实现了List,提供了元素添加、删除、修改、遍历等功能。
  2. ArrayList 实现了RandmoAccess接口,即提供了随机访问功能(通过元素序号快速获取元素,即所谓的快速访问)。
  3. ArrayList 实现了Cloneable接口,即覆盖了函数clone(),能被克隆。
  4. ArrayList 实现java.io.Serializable接口,这意味着ArrayList支持序列化,能通过序列化去传输。
  5. ArrayList 线程不安全,在多线程中可以选择CopyOnWriteArrayList。

ArrayList继承关系

在这里插入图片描述

1.2 ArrayList数据结构

ArrayList的成员变量:

  1. //初始化默认容量
  2. private static final int DEFAULT_CAPACITY = 10;
  3. // 空对象数组
  4. private static final Object[] EMPTY_ELEMENTDATA = {
  5. };
  6. // 默认容量的空对象数组
  7. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
  8. };
  9. // 实际存储对象的数组
  10. transient Object[] elementData;
  11. // 存储的数量
  12. private int size;
  13. // 数组能申请的最大数量
  14. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

成员变量中的elementData 和 size 是两个比较重要的参数:

  1. elementData 是”Object[]类型的数组”,它保存了添加到ArrayList中的元素。实际上,elementData是个动态数组,我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity;如果通过不含参数的构造函数ArrayList()来创建ArrayList,则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长,具体的增长方式,请参考源码分析中的ensureCapacity()函数。
  2. size 则是动态数组的实际大小。

1.3 ArrayList构造函数

ArrayList提供了三个构造函数:

  1. // 默认构造函数
  2. public ArrayList()
  3. // capacity:ArrayList的默认容量大小。增加数据导致容量不足时,ArrayList会扩容,增加上一次容量大小的一半。
  4. public ArrayList(int capacity) {
  5. // 当 initialCapacity > 0 时,初始化对应大小的数组
  6. if (initialCapacity > 0) {
  7. this.elementData = new Object[initialCapacity];
  8. // 为 0 时,用指向EMPTY_ELEMENTDATA
  9. } else if (initialCapacity == 0) {
  10. this.elementData = EMPTY_ELEMENTDATA;
  11. } else {
  12. throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
  13. }
  14. }
  15. // 创建一个包含collection的ArrayList
  16. public ArrayList(Collection<? extends E> collection) {
  17. elementData = c.toArray();
  18. if ((size = elementData.length) != 0) {
  19. // c.toArray不返回Object[]的时候,则进行数组拷贝
  20. if (elementData.getClass() != Object[].class)
  21. elementData = Arrays.copyOf(elementData, size, Object[].class);
  22. } else {
  23. // 如果为空,则指向EMPTY_ELEMENTDATA
  24. this.elementData = EMPTY_ELEMENTDATA;
  25. }
  26. }

1.4 ArrayList的API















































































































返回值 方法 描述
boolean add(E e) 将指定的元素添加到此列表的尾部。
void add(int index, E element) 将指定的元素插入此列表中的指定位置。
boolean addAll(Collection<? extends E> c) 按照指定 collection 的迭代器所返回的元素顺序,将该 collection 中的所有元素添加到此列表的尾部。
boolean addAll(int index, Collection<? extends E> c) 从指定的位置开始,将指定 collection 中的所有元素插入到此列表中。
void clear() 移除此列表中的所有元素。
Object clone() 返回此 ArrayList 实例的浅表副本。
boolean contains(Object o) 如果此列表中包含指定的元素,则返回 true。
void ensureCapacity(int minCapacity) 如有必要,增加此 ArrayList 实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数。
E get(int index) 返回此列表中指定位置上的元素。
int indexOf(Object o) 返回此列表中首次出现的指定元素的索引,或如果此列表不包含元素,则返回 -1。
boolean isEmpty() 如果此列表中没有元素,则返回 true
int lastIndexOf(Object o) 返回此列表中最后一次出现的指定元素的索引,或如果此列表不包含索引,则返回 -1。
E remove(int index) 移除此列表中指定位置上的元素。
boolean remove(Object o) 移除此列表中首次出现的指定元素(如果存在)
protected void removeRange(int fromIndex, int toIndex) 移除列表中索引在 fromIndex(包括)和 toIndex(不包括)之间的所有元素。
E set(int index, E element) 用指定的元素替代此列表中指定位置上的元素。
int size() 返回此列表中的元素数。
Object[] toArray() 按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组。
T[] toArray(T[] a) 按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组;返回数组的运行时类型是指定数组的运行时类型。
void trimToSize() 将此 ArrayList 实例的容量调整为列表的当前大小。

2 ArrayList常用操作

2.1 ArrayList遍历

ArrayList支持三种遍历方式:迭代器遍历、随机访问遍历、增强for遍历

  1. public static void main(String[] args) {
  2. List<Integer> list = Arrays.asList(1, 7, 5, 3, 8, 2);
  3. // 迭代器遍历
  4. Iterator<Integer> it = list.iterator();
  5. while (it.hasNext()) {
  6. int value = (int) it.next();
  7. System.out.println(value + " ");
  8. }
  9. // 随机访问遍历
  10. for (int i = 0; i < list.size(); i++) {
  11. int value = list.get(i);
  12. System.out.println(value + " ");
  13. }
  14. // 增强for遍历
  15. for (int value : list) {
  16. System.out.print(value + " ");
  17. }
  18. }

2.2 ArrayList排序

ArrayList集合排序依赖于Collections.sort(),其默认是按升序排序的,如果想要降序排列,需重写Collections.sort()方法。

  1. public static void main(String[] args) {
  2. List<Integer> list = Arrays.asList(1, 7, 5, 3, 8, 2);
  3. // 按照字典顺序排序
  4. Collections.sort(list);
  5. System.out.println("默认排序:" + list);
  6. // 自定义排序
  7. Collections.sort(list, new Comparator<Integer>() {
  8. @Override
  9. public int compare(Integer o1, Integer o2) {
  10. int i = o1.compareTo(o2);
  11. // int、double型,可以直接用o1 > o2做if的判断条件,String类型只能用compareTo方法
  12. if (i > 0)
  13. return -1;
  14. return 1;
  15. }
  16. });
  17. System.out.println("自定义排序:" + list);
  18. }

运行结果:

  1. 默认排序:[1, 2, 3, 5, 7, 8]
  2. 自定义排序:[8, 7, 5, 3, 2, 1]

2.3 ArrayList删除元素

现在有 [a,a,b,c,e,a,d] 这么一个ArrayList集合,删除该集合中的所有的”a”。也许有人觉得很简单,并给出下面代码:

  1. public static void main(String[] args) {
  2. List<String> list = new ArrayList<>();
  3. list.add("a");
  4. list.add("a");
  5. list.add("d");
  6. list.add("c");
  7. list.add("a");
  8. list.add("e");
  9. list.add("m");
  10. // 错误的删除方法:
  11. for (int i = 0; i < list.size(); i++) {
  12. String value = list.get(i);
  13. if (value.equals("a"))
  14. list.remove(i);
  15. }
  16. System.out.println(list);
  17. }

运行结果:

  1. [a, d, c, e, m]

可以看到,当有连续两个以上a元素时,最终会保留一个。原因是,删除元素后,ArrayList集合的索引重新排列,删除元素后面的元素索引全部向前移动一位,本例中,删除第一个a后,第二个a的索引就由1变成了0,而for循环已经运行过0了,导致第二个a未被删除。
正确的做法是倒序遍历删除:

  1. for (int i = list.size()-1; i >= 0; i--) {
  2. String value = list.get(i);
  3. if (value.equals("a"))
  4. list.remove(i);
  5. }

3 ArrayList部分方法源码(基于JDK1.8)

3.1 get(int index)

  1. // 先检查index范围是否正确,正确的话从数组里取出元素
  2. public E get(int index) {
  3. rangeCheck(index);
  4. return elementData(index);
  5. }
  6. E elementData(int index) {
  7. return (E) elementData[index];
  8. }
  9. private void rangeCheck(int index) {
  10. // 如果index 大于 存储的个数,则抛出异常
  11. if (index >= size)
  12. // outOfBoundsMsg里面就是简单的字符串拼接。
  13. throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  14. }

3.2 add(E e)

  1. public boolean add(E e) {
  2. // 对于刚初始化的数组,要初始化它的大小
  3. // 判断数组大小是否足够,如果不够大,扩容
  4. // 对于扩容要判断是否到达数组的最大数量
  5. ensureCapacityInternal(size + 1);
  6. //赋值,然后指针走到下一个空位
  7. elementData[size++] = e;
  8. return true;
  9. }
  10. private void ensureCapacityInternal(int minCapacity) {
  11. // 上述情况一:初始化数组的大小
  12. if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  13. // 取minCapacity和DEFAULT_CAPACITY中较大的那个
  14. minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  15. }
  16. // 检查有没有扩容的必要
  17. ensureExplicitCapacity(minCapacity);
  18. }
  19. private void ensureExplicitCapacity(int minCapacity) {
  20. // 修改次数的计数器(在AbstractList中定义的)
  21. modCount++;
  22. // 如果需要的空间大小 > 当前数组的长度,则进行扩容
  23. if (minCapacity - elementData.length > 0)
  24. grow(minCapacity);
  25. }
  26. private void grow(int minCapacity) {
  27. // 记录旧的length
  28. int oldCapacity = elementData.length;
  29. // 扩容1.5倍, 位运算符效率更高
  30. int newCapacity = oldCapacity + (oldCapacity >> 1);
  31. // 判断有没有溢出
  32. if (newCapacity - minCapacity < 0)
  33. newCapacity = minCapacity;
  34. // 判断有没有超过最大的数组大小
  35. if (newCapacity - MAX_ARRAY_SIZE > 0)
  36. //计算最大的容量
  37. newCapacity = hugeCapacity(minCapacity);
  38. // 旧数组拷贝到新的大小数组
  39. elementData = Arrays.copyOf(elementData, newCapacity);
  40. }
  41. // 最大的容量
  42. private static int hugeCapacity(int minCapacity) {
  43. // 大小溢出
  44. if (minCapacity < 0)
  45. throw new OutOfMemoryError();
  46. // 需要的最小容量 > 数组最大的长度,则取Integer的最大值,否则取数组最大长度
  47. return (minCapacity > MAX_ARRAY_SIZE) ?
  48. Integer.MAX_VALUE :
  49. MAX_ARRAY_SIZE;
  50. }

3.3 remove(Object o)

  1. public boolean remove(Object o) {
  2. // 判断o为null,loop遍历找到为null的元素
  3. if (o == null) {
  4. for (int index = 0; index < size; index++)
  5. if (elementData[index] == null) {
  6. fastRemove(index);
  7. return true;
  8. }
  9. // 不为null
  10. } else {
  11. for (int index = 0; index < size; index++)
  12. if (o.equals(elementData[index])) {
  13. fastRemove(index);
  14. return true;
  15. }
  16. }
  17. return false;
  18. }
  19. // 与上面的remove(int index) 类似
  20. private void fastRemove(int index) {
  21. modCount++;
  22. int numMoved = size - index - 1;
  23. if (numMoved > 0)
  24. System.arraycopy(elementData, index+1, elementData, index,
  25. numMoved);
  26. elementData[--size] = null;
  27. }

set(int index, E element)

  1. public E set(int index, E element) {
  2. rangeCheck(index);
  3. // 记录旧的值
  4. E oldValue = elementData(index);
  5. //在原位置设置新的值
  6. elementData[index] = element;
  7. return oldValue;
  8. }

3.4 addAll(Collection<? extends E> c)

  1. public boolean addAll(Collection<? extends E> c) {
  2. Object[] a = c.toArray();
  3. int numNew = a.length;
  4. // 对于新的最小长度进行判断处理
  5. ensureCapacityInternal(size + numNew);
  6. //将a数组,从index-0开始,拷贝numNew个,到elementData的size位置
  7. System.arraycopy(a, 0, elementData, size, numNew);
  8. //将size增加numNew个
  9. size += numNew;
  10. return numNew != 0;
  11. }

发表评论

表情:
评论列表 (有 0 条评论,25人围观)

还没有评论,来说两句吧...

相关阅读