java数据结构之数组列表ArrayList的使用及实现原理解读

一、ArrayList的作用及优缺点

ArrayList是通过数组作为存储为实现的列表,它是一种顺序存储结构

  • 优点
    • 通过位置(索引)查找数据较快
  • 缺点
    • 插入数据需要移动插入位置后面所有的元素
    • 删除数据需要移动删除位置后面所有的元素

二、ArrayList类与其他数据结构之间的关系

1.ArrayList与其他集合类型的关系

ArrayList与其他数据结构之间的关系

2.ArrayList与具体的集合类型的关联

ArrayList与其他接口之间的关系

  • JAVA数据结构大致可分为两大类:Collection(集合)和Map,Collection属于线性结构,而ArrayList作为一种List,也属于Collection
  • Iterable接口:可迭代,主要要实现一个类型为Iterator的迭代器方法iterator

三、ArrayList的使用及具体实现

1.ArrayList的数据项
  • size : 数组列表的元素个数
  • elementData : 数组元素的存储的集合(是一个对象数组)
  1. transient Object[] elementData;
  2. private int size;
2.ArrayList的初始化
(1)使用
  • new ArrayList()
    • 初始化一个容量为0的数组列表
  • new ArrayList(int capacity);
    • 初始化一个容量为capacity的数组列表(后期可通过add扩容)
  • new ArrayList(Collection c)
    • 指定初始化内容进行初始化
  1. //1.不指定初始化容量
  2. List<Integer> intList = new ArrayList<Integer>();
  3. intList.add(2);
  4. intList.add(8);
  5. intList.add(9);
  6. System.out.println(intList); //[2, 8, 9]
  7. //2.指定初始化容量
  8. List<String> list = new ArrayList<String>(5);
  9. list.add("A");
  10. list.add("B");
  11. list.add("C");
  12. System.out.println(list); //[A, B, C]
  13. //3.通过另外一个ArrayList作为元素集合来实例化一个新的ArrayList
  14. List<String> books = new ArrayList<String>();
  15. books.add("大话数据结构");
  16. books.add("算法");
  17. books.add("数据结构与算法分析");
  18. List<String> bookNameList = new ArrayList<String>(books);
  19. System.out.println(bookNameList); //[大话数据结构, 算法, 数据结构与算法分析]
  20. //4.通过另外一个HashSet作为元素集合来实例化一个新的ArrayList;
  21. Set<String> languages = new HashSet<>(3);
  22. languages.add("JAVA");
  23. languages.add("Javascript");
  24. languages.add("PHP");
  25. languages.add("GoLang");
  26. languages.add("Python");
  27. languages.add("Lua");
  28. List<String> langList = new ArrayList<>(languages);
  29. System.out.println(langList); //[JAVA, Javascript, PHP, Lua, GoLang, Python]
(2)实现原理 
  • (1)指定数据容量:则初始化一个包含容量的对象数组用来存储元素集合
    1. public ArrayList(int initialCapacity) {
    2. //初始化容量大于0,则申请一个容量为capacity的数组来存储列表元素
    3. if (initialCapacity > 0) {
    4. this.elementData = new Object[initialCapacity];
    5. } else if (initialCapacity == 0) {
    6.   //如果容量等于0,则申请一个空数组来存储元素列表  
    7. this.elementData = EMPTY_ELEMENTDATA;
    8. } else {
    9. throw new IllegalArgumentException("Illegal Capacity: "+
    10. initialCapacity);
    11. }
    12. }
  • (2)未指定数据容量:则初始化一个空的对象数组来存储元素集合
    1. public ArrayList() {
    2. //不指定初始化容量时,以默认的空数组来存储
    3. this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    4. }
  • (3)通过集合对象初始化:通过一个集合对象来初始化,将集合的数据转化为数组
  1. public ArrayList(Collection<? extends E> c) {
  2. //1.将集合元素转化为数组对象
  3. elementData = c.toArray();
  4. if ((size = elementData.length) != 0) {
  5. //2.如果集合元素的个数不为0,而且集合元素不为对象数组(因为默认的就是对象数组来存储)
  6. if (elementData.getClass() != Object[].class)
  7. //通过复制的方式将集合的元素值存入到新的数组中
  8. elementData = Arrays.copyOf(elementData, size, Object[].class);
  9. } else {
  10. //申请空的数组来存储元素
  11. this.elementData = EMPTY_ELEMENTDATA;
  12. }
  13. }
3.ArrayList实现的迭代器接口
(1)迭代器方法iterator的用法
  1. List<String> list = new ArrayList<String>(5);
  2. list.add("A");
  3. list.add("B");
  4. list.add("C");
  5. System.out.println(list); //[A, B, C]
  6. //通过iterator可以获取元素迭代器,通过迭代器,可以遍历列表元素
  7. Iterator<String> iterator = list.iterator();
  8. while(iterator.hasNext()) {
  9.   //调用iterator.next方法不仅可以获取下一个元素的值,而且还将迭代器指向下一个元素 
  10. String val = iterator.next();
  11. System.out.println(val); //A,B,C
  12. }
(2)实现hasNext方法
  1. public boolean hasNext() {
  2. return cursor != size;
  3. }
  • cursor表示当前返回元素下一个元素的索引值
  • 当cursor等于size时,表示已经到表尾,所以只要没到表尾,就还有下一个元素
(3)实现next方法
  1. public E next() {
  2. checkForComodification();
  3. int i = cursor;
  4. if (i >= size)
  5. throw new NoSuchElementException();
  6. Object[] elementData = ArrayList.this.elementData;
  7. if (i >= elementData.length)
  8. throw new ConcurrentModificationException();
  9. cursor = i + 1;
  10. return (E) elementData[lastRet = i];
  11. }
  • lastRet : 表示上次返回的索引值
  • cursor = i + 1 表示每迭代一次,往后移动一位 
  • elementData[lastRet = i]相当于两步:
    • lastRet = i,假如i=0表示第1次迭代
    • elementData[lastRet],返回索引为lastRet的值
(4)实现remove方法
  1. public void remove() {
  2. if (lastRet < 0)
  3. throw new IllegalStateException();
  4. checkForComodification();
  5. try {
  6. ArrayList.this.remove(lastRet);
  7. cursor = lastRet;
  8. lastRet = -1;
  9. expectedModCount = modCount;
  10. } catch (IndexOutOfBoundsException ex) {
  11. throw new ConcurrentModificationException();
  12. }
  13. }
  • 调用ArrayList的remove方法,根据索引值删除元素
4.ArrayList实现Collection接口
(1)实现toArray方法

toArray方法的使用:

  1. Set<String> languages = new HashSet<>(3);
  2. languages.add("JAVA");
  3. languages.add("Javascript");
  4. languages.add("PHP");
  5. languages.add("GoLang");
  6. languages.add("Python");
  7. languages.add("Lua");
  8. String[] langArr = new String[langList.size()];
  9. langList.toArray(langArr);
  10. for (int i = 0; i< langArr.length; i++) {
  11. System.out.println(langArr[i]);
  12. }

toArray的实现原理:

  1. public <T> T[] toArray(T[] a) {
  2. //1.如果用来存储元素值的数组长度不够,则直接返回一个新的数组(将原存储数据集合的值复制到新的数组中)
  3. if (a.length < size)
  4. return (T[]) Arrays.copyOf(elementData, size, a.getClass());
  5. //2.将存储的元素的值复制到返回的a数组中
  6. System.arraycopy(elementData, 0, a, 0, size);
  7. //3.如果a的长度超过原数组长度,则让a数组的size索引对应的值设置为null
  8. if (a.length > size)
  9. a[size] = null;
  10. return a;
  11. }
  • Arrays.copyof参数说明
    • 第1个参数:srcArray 源数组,被复制的数组
    • 第2个参数:newLength 复制存储的数组的长度(被复制的长度)
    • 第3个参数:newType 新数组的元素类型
  • System.arraycopy参数说明
    • 第1个参数:srcArray 源数组(被复制的数组),是一个数组对象
    • 第2个参数:srcPos 源数组的起始索引,即从哪个位置开始复制
    • 第3个参数:dstArray 复制的目的数组,即复制存储到哪个数组元素中
    • 第4个参数:dstPos 目标数组的起始索引,复制的存储的起始位置
    • 第5个参数:size 被复制的长度  
(2)实现add方法

add方法的使用:

  • add(T value):在列表末尾添加一个元素
  • add(int index, T value):在指定位置(index)插入一个元素
  1. List<Integer> scores = new ArrayList<>(5);
  2. scores.add(59);
  3. scores.add(65);
  4. scores.add(78);
  5. scores.add(98);
  6. scores.add(3, 88);
  7. System.out.println(scores); //[59, 65, 78, 88, 98]

add方法的实现解读:

  • 不指定索引位置,添加元素,即在数组末尾添加元素
  1. public boolean add(E e) {
  2. //1.检查是否需要扩容,如果需要扩容,则扩容
  3. ensureCapacityInternal(size + 1);
  4. //2.存储插入的值,并增加元素个数
  5. elementData[size++] = e;
  6. return true;
  7. }
  • 指定索引位置,添加元素,在指定位置插入元素
  1. public void add(int index, E element) {
  2. //1.检查插入的索引值是否合法
  3. rangeCheckForAdd(index);
  4. //2.检查是否需要扩容,如果需要,则扩容
  5. ensureCapacityInternal(size + 1);
  6. //3.通过复制的方式将数组元素依次往后移动
  7. System.arraycopy(elementData, index, elementData, index + 1,
  8. size - index);
  9. //4.设置插入的值
  10. elementData[index] = element;
  11. //5.增加元素个数
  12. size++;
  13. }
(3)实现remove方法

remove方法使用

  • remove(int index) : 通过索引值删除
  • remove(Object obj) : 通过对象删除
  1. List<Integer> scores = new ArrayList<>(5);
  2. scores.add(59);
  3. scores.add(65);
  4. scores.add(78);
  5. scores.add(98);
  6. scores.add(3, 88);
  7. System.out.println(scores); //[59, 65, 78, 88, 98]
  8. scores.remove((Object)78); //这里将78强制转换为Object,是因为如果直接使用78,会被当成是索引值
  9. System.out.println(scores); //[59, 65, 88, 98]
  10. scores.remove(3);
  11. System.out.println(scores); //[59, 65, 88]

remove方法实现解读

  • 通过索引值删除

    1. public E remove(int index) {
    2. //1.检查索引值的合法性
    3. rangeCheck(index);
    4. //增加修改次数
    5. modCount++;
    6. //2.通过索引获取要删除的元素值
    7. E oldValue = elementData(index);
    8. //3.计算出需要移动的元素个数
    9. int numMoved = size - index - 1;
    10. if (numMoved > 0)
    11. //4.通过复制的方式将元素向前移动
    12. System.arraycopy(elementData, index+1, elementData, index,
    13. numMoved);
    14. //5.将最后一位的元素值设置为null,而且将元素个数减1
    15. elementData[--size] = null; // clear to let GC do its work
    16. //返回被删除的对象的值
    17. return oldValue;
    18. }
  • 通过元素对象删除
  1. public boolean remove(Object o) {
  2. //通过元素对象找到元素对应的索引值,再通过索引值来删除元素
  3. //1.如果要删除的对象是null
  4. if (o == null) {
  5. //遍历整个数组
  6. for (int index = 0; index < size; index++)
  7. //如果某个元素的值是null,则删除,并且退出循环返回
  8. if (elementData[index] == null) {
  9. fastRemove(index);
  10. return true;
  11. }
  12. } else {
  13. for (int index = 0; index < size; index++)
  14.    //比较两个对象值是否相等   
  15. if (o.equals(elementData[index])) {
  16. fastRemove(index);
  17. return true;
  18. }
  19. }
  20. return false;
  21. }

注:fastRemove的实现:

  1. private void fastRemove(int index) {
  2. //增加修改次数
  3. modCount++;
  4. //1.计算出要移动的元素的个数
  5. int numMoved = size - index - 1;
  6. if (numMoved > 0)
  7. //2.通过复制的方式来删除元素
  8. System.arraycopy(elementData, index+1, elementData, index,
  9. numMoved);
  10. //3.最后一个元素的值为null,并且减少元素个数
  11. elementData[--size] = null; // clear to let GC do its work
  12. }
(4)实现addAll方法

addAll的使用:

  • addAll(Collection c) : 在列表末尾批量添加元素
  • addAll(int index, Collection c) : 在指定位置批量插入元素
  1. List<String> charList = new ArrayList<String>(5);
  2. charList.add("A");
  3. charList.add("B");
  4. List<String> addition = new ArrayList<>(5);
  5. addition.add("C");
  6. addition.add("D");
  7. addition.add("E");
  8. charList.addAll(addition);
  9. System.out.println(charList); //[A, B, C, D, E]
  10. Set<String> charSet = new HashSet<String>(2);
  11. charSet.add("B1");
  12. charSet.add("B2");
  13. charSet.add("B3");
  14. charList.addAll(2, charSet);
  15. System.out.println(charList); //[A, B, B2, B3, B1, C, D, E]

addAll的实现解读:

  • 不指定位置批量添加元素
  1. public boolean addAll(Collection<? extends E> c) {
  2. //1.将集合对象转化为数组对象
  3. Object[] a = c.toArray();
  4. //2.获取要添加的元素个数
  5. int numNew = a.length;
  6. //3.存储扩容
  7. ensureCapacityInternal(size + numNew); // Increments modCount
  8. //3.通过复制的方式将插入的数组元素复制到原数组的末尾
  9. System.arraycopy(a, 0, elementData, size, numNew);
  10. //4.增加列表的个数
  11. size += numNew;
  12. return numNew != 0;
  13. }
  • 指定位置批量添加元素
  1. public boolean addAll(int index, Collection<? extends E> c) {
  2. //1.检查索引值
  3. rangeCheckForAdd(index);
  4. //2.将插入的集合对象转化为数组对象
  5. Object[] a = c.toArray();
  6. //3.获取新增元素的个数
  7. int numNew = a.length;
  8. //4.存储扩容
  9. ensureCapacityInternal(size + numNew); // Increments modCount
  10. //5.计算出要移动的元素个数
  11. int numMoved = size - index;
  12. if (numMoved > 0)
  13. //6.通过数组复制的方式将要移动的元素移动到相应的空间上
  14. System.arraycopy(elementData, index, elementData, index + numNew,
  15. numMoved);
  16. //7.通过数组复制的方式将新插入的元素插入到数组中
  17. System.arraycopy(a, 0, elementData, index, numNew);
  18. //8.增加数组元素的个数
  19. size += numNew;
  20. return numNew != 0;
  21. }
(5)实现removeAll方法

removeAll用法

  • removeAll(Collection c) : 批量删除ArrayList在指定集合中元素
  1. List<String> charList = new ArrayList<String>(5);
  2. charList.add("A");
  3. charList.add("B");
  4. charList.add("C");
  5. charList.add("D");
  6. charList.add("E");
  7. System.out.println(charList); //[A, B, C, D, E]
  8. Set<String> charSet = new HashSet<String>(2);
  9. charSet.add("B1");
  10. charSet.add("B2");
  11. charSet.add("B3");
  12. charList.addAll(2, charSet);
  13. System.out.println(charList); //[A, B, B2, B3, B1, C, D, E]
  14. charList.removeAll(charSet);
  15. System.out.println(charList); //[A, B, C, D, E]

removeAll实现解读

  1. public boolean removeAll(Collection<?> c) {
  2. //1.检测集合元素是否为null
  3. Objects.requireNonNull(c);
  4. //调用批量删除的方法
  5. return batchRemove(c, false);
  6. }

注:batchRemove的实现

  1. private boolean batchRemove(Collection<?> c, boolean complement) {
  2. final Object[] elementData = this.elementData;
  3. int r = 0, w = 0;
  4. boolean modified = false;
  5. try {
  6. for (; r < size; r++)
  7.    //1.过滤出那些不在删除数组中的元素(即保存的元素个数)   
  8. if (c.contains(elementData[r]) == complement)
  9. elementData[w++] = elementData[r];
  10. } finally {
  11. //2.当过滤保存元素操作时出现异常时
  12. if (r != size) {
  13. //将出现异常后面的元素放入到数组中
  14. System.arraycopy(elementData, r,
  15. elementData, w,
  16. size - r);
  17. w += size - r;
  18. }
  19. //3.当有要删除的元素时(w是保存的元素集合的索引)
  20. if (w != size) {
  21. //保留元素之后的所有元素都是要删除的元素
  22. for (int i = w; i < size; i++)
  23. elementData[i] = null;
  24. modCount += size - w;
  25. //4.重新设置列表的长度
  26. size = w;
  27. modified = true;
  28. }
  29. }
  30. return modified;
  31. }
(6)实现clear方法

clear方法用法

  • clear():清除列表中的元素,使列表成为一个空列表
  1. List<String> charList = new ArrayList<String>(5);
  2. charList.add("A");
  3. charList.add("B");
  4. charList.clear();
  5. System.out.println(charList.isEmpty()); //true

clear方法实现解读

  1. public void clear() {
  2. //1.增加修改次数
  3. modCount++;
  4. //2.将所有元素的值设置为null
  5. for (int i = 0; i < size; i++)
  6. elementData[i] = null;
  7. //将数组列表的元素个数设置为0
  8. size = 0;
  9. }
  • 将所有元素的值设置为null
  • 将数组列表的元素个数设置为0
5.ArrayList实现List接口
(1)实现set方法

set方法的使用

  • set(int index, E element):设置某个索引的值为某个对象
  1. List<String> list = new ArrayList<String>(5);
  2. list.add("A");
  3. list.add("B");
  4. System.out.println(list); //[A, B, C]
  5. list.set(1, "D");
  6. System.out.println(list.get(1)); //D
  7. System.out.println(list); //[A, D, C]

set方法的实现解读

  1. public E set(int index, E element) {
  2. //1.检查索引值
  3. rangeCheck(index);
  4. //2.获取该索引的对应的旧元素的值
  5. E oldValue = elementData(index);
  6. //3.通过数组的索引设置新的值
  7. elementData[index] = element;
  8. return oldValue;
  9. }
(2)实现get方法

get方法的使用

  • get(int index):获取某个索引的对应的元素
  1. List<String> list = new ArrayList<String>(5);
  2. list.add("A");
  3. list.add("B");
  4. System.out.println(list); //[A, B, C]
  5. System.out.println(list.get(1)); //B

get方法的实现解读

  1. public E get(int index) {
  2. //1.检查索引
  3. rangeCheck(index);
  4. //2.通过elementData方法获取元素值
  5. return elementData(index);
  6. }

注:ElementData方法

  1. E elementData(int index) {
  2. //通过数组的索引获取其对应的值
  3. return (E) elementData[index];
  4. }
(5)实现subList方法

subList方法的使用

  • subList(int fromIndex, int toIndex):获取从frontIndex到toIndex的子列表([fromIndex, toIndex))
  1. List<String> list = new ArrayList<String>(5);
  2. list.add("A");
  3. list.add("B");
  4. list.add("C");
  5. list.add("D");
  6. list.add("E");
  7. list.add("F");
  8. list.add("G");
  9. List<String> subList = list.subList(1, 5);
  10. System.out.println(subList); //[B, C, D, E]

subList方法的实现解读

  1. public List<E> subList(int fromIndex, int toIndex) {
  2. //参数检查
  3. subListRangeCheck(fromIndex, toIndex, size);
  4. return new SubList(this, 0, fromIndex, toIndex);
  5. }
(6)实现indexOf方法

indexOf的使用:

  • indexOf(E element):获取指定元素的索引值(第一次出现的)
  1. ArrayList<Integer> numList = new ArrayList<Integer>(5);
  2. numList.add(12);
  3. numList.add(8);
  4. numList.add(18);
  5. numList.add(2);
  6. numList.add(29);
  7. numList.add(18);
  8. System.out.println(numList.indexOf(18)); //2

indexOf的实现解读

  1. public int indexOf(Object o) {
  2. //1.如果元素为null,那么就查找元素值为null的元素
  3. if (o == null) {
  4. //2.依次遍历循环比较,第一个出现后就返回
  5. for (int i = 0; i < size; i++)
  6. if (elementData[i]==null)
  7. return i;
  8. } else {
  9.   //1.如果元素不为null,依次遍历循环比较,第一个出现后就返回  
  10. for (int i = 0; i < size; i++)
  11. if (o.equals(elementData[i]))
  12. return i;
  13. }
  14. //未找到相应元素
  15. return -1;
  16. }
(7)实现lastIndexOf方法

lastIndexOf的使用:

  • lastIndexOf(E element):获取指定元素的最后一次出现的索引值
  1. ArrayList<Integer> numList = new ArrayList<Integer>(5);
  2. numList.add(12);
  3. numList.add(8);
  4. numList.add(18);
  5. numList.add(2);
  6. numList.add(29);
  7. numList.add(18);
  8. System.out.println(numList.lastIndexOf(18)); //5

lastIndexOf的实现的解读

  1. public int lastIndexOf(Object o) {
  2. //1.如果元素为null,那么就查找元素值为null的元素
  3. if (o == null) {
  4. //2.从后往前依次比较
  5. for (int i = size-1; i >= 0; i--)
  6. if (elementData[i]==null)
  7. return i;
  8. } else {
  9.    //1.如果元素不为null,依次(从后往前)遍历循环比较,相等后就返回  
  10. for (int i = size-1; i >= 0; i--)
  11. if (o.equals(elementData[i]))
  12. return i;
  13. }
  14. //未找到相应元素
  15. return -1;
  16. }
(8)其他方法使用
  • sort:排序
    • 参数说明:它的参数是一个实现Comparator接口的对象
  1. public class NumSort implements Comparator {
  2. public int compare(Object o1, Object o2) {
  3. int num1 = (int) o1;
  4. int num2 = (int) o2;
  5. return num1 - num2;
  6. }
  7. }
  1. ArrayList<Integer> numList = new ArrayList<Integer>(5);
  2. numList.add(12);
  3. numList.add(8);
  4. numList.add(18);
  5. numList.add(2);
  6. numList.add(29);
  7. numList.sort(new NumSort());
  8. System.out.println(numList); //[2, 8, 12, 18, 29]
  • clone:数组克隆
  1. ArrayList<Integer> numList = new ArrayList<Integer>(5);
  2. numList.add(12);
  3. numList.add(8);
  4. numList.add(18);
  5. numList.add(2);
  6. numList.add(29);
  7. List<Integer> digitalList = (ArrayList<Integer>) numList.clone();
  8. System.out.println(digitalList); //[12, 8, 18, 2, 29]
  • contains:是否包含某个元素对象
  1. List<Integer> numList = new ArrayList<Integer>(5);
  2. numList.add(12);
  3. numList.add(8);
  4. numList.add(18);
  5. numList.add(2);
  6. numList.add(29);
  7. System.out.println(numList.contains(2)); // true
  • size : 获取列表的元素个数
  1. List<Integer> numList = new ArrayList<Integer>(5);
  2. numList.add(12);
  3. numList.add(8);
  4. numList.add(18);
  5. numList.add(2);
  6. numList.add(29);
  7. System.out.println(numList.size()); //5
  • isEmpty : 数组列表是否为空列表
  1. List<Integer> numList = new ArrayList<Integer>(5);
  2. numList.add(12);
  3. numList.add(8);
  4. numList.add(18);
  5. numList.add(2);
  6. numList.add(29);
  7. System.out.println(numList.isEmpty()); //false