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

发表于   |   分类于 左手代码 计算机基础   |   阅读(220)   |   评论(0)

一、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]
  8. //2.指定初始化容量
  9.         List<String> list = new ArrayList<String>(5);
  10.         list.add("A");
  11.         list.add("B");
  12.         list.add("C");
  13.         System.out.println(list);  //[A, B, C]
  15. //3.通过另外一个ArrayList作为元素集合来实例化一个新的ArrayList
  16.         List<String> books = new ArrayList<String>();
  17.         books.add("大话数据结构");
  18.         books.add("算法");
  19.         books.add("数据结构与算法分析");
  21.         List<String> bookNameList = new ArrayList<String>(books);
  22.         System.out.println(bookNameList); //[大话数据结构, 算法, 数据结构与算法分析]
  24. //4.通过另外一个HashSet作为元素集合来实例化一个新的ArrayList;
  25.         Set<String> languages = new HashSet<>(3);
  26.         languages.add("JAVA");
  27.         languages.add("Javascript");
  28.         languages.add("PHP");
  29.         languages.add("GoLang");
  30.         languages.add("Python");
  31.         languages.add("Lua");
  33.         List<String> langList = new ArrayList<>(languages);
  34.         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]
  7. //通过iterator可以获取元素迭代器，通过迭代器，可以遍历列表元素
  8. Iterator<String> iterator = list.iterator();
  9. while(iterator.hasNext()) {
  10. 　　//调用iterator.next方法不仅可以获取下一个元素的值，而且还将迭代器指向下一个元素　
  11.     String val = iterator.next();
  12.     System.out.println(val); //A,B,C
  13. }
(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();
  6.     try {
  7.         ArrayList.this.remove(lastRet);
  8.         cursor = lastRet;
  9.         lastRet = -1;
  10.         expectedModCount = modCount;
  11.      } catch (IndexOutOfBoundsException ex) {
  12.         throw new ConcurrentModificationException();
  13.     }
  14. }
  • 调用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");
  9. String[] langArr = new String[langList.size()];
  10. langList.toArray(langArr);
  11. for (int i = 0; i< langArr.length; i++) {
  12.     System.out.println(langArr[i]);
  13. }

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);
  8. System.out.println(scores); //[59, 65, 78, 88, 98]
  10. scores.remove((Object)78);  //这里将78强制转换为Object，是因为如果直接使用78,会被当成是索引值
  11. System.out.println(scores); //[59, 65, 88, 98]
  13. scores.remove(3);
  14. System.out.println(scores); //[59, 65, 88]

remove方法实现解读

  • 通过索引值删除

    1. public E remove(int index) {
    2.   //1.检查索引值的合法性
    3.   rangeCheck(index);
    5.   //增加修改次数
    6.   modCount++;
    7.   //2.通过索引获取要删除的元素值
    8.   E oldValue = elementData(index);
    10.   //3.计算出需要移动的元素个数
    11.   int numMoved = size - index - 1;
    12.   if (numMoved > 0)
    13.       //4.通过复制的方式将元素向前移动
    14.       System.arraycopy(elementData, index+1, elementData, index,
    15.                            numMoved);
    16.   //5.将最后一位的元素值设置为null,而且将元素个数减1
    17.   elementData[--size] = null; // clear to let GC do its work
    19.   //返回被删除的对象的值
    20.   return oldValue;
    21. }
  • 通过元素对象删除
  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");
  5. List<String> addition = new ArrayList<>(5);
  6. addition.add("C");
  7. addition.add("D");
  8. addition.add("E");
  9. charList.addAll(addition);
  10. System.out.println(charList);  //[A, B, C, D, E]
  12. Set<String> charSet = new HashSet<String>(2);
  13. charSet.add("B1");
  14. charSet.add("B2");
  15. charSet.add("B3");
  17. charList.addAll(2, charSet);
  18. 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");
  8. 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");
  15. charList.addAll(2, charSet);
  16. System.out.println(charList);  //[A, B, B2, B3, B1, C, D, E]
  18. charList.removeAll(charSet);
  19. 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++;
  5.     //2.将所有元素的值设置为null
  6.     for (int i = 0; i < size; i++)
  7.         elementData[i] = null;
  9.     //将数组列表的元素个数设置为0
  10.     size = 0;
  11. }
  • 将所有元素的值设置为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]
  6. list.set(1, "D");
  7. System.out.println(list.get(1));   //D
  8. System.out.println(list);          //[A, D, C]

set方法的实现解读

  1. public E set(int index, E element) {
  2.     //1.检查索引值
  3.     rangeCheck(index);
  5.     //2.获取该索引的对应的旧元素的值
  6.     E oldValue = elementData(index);
  7.     //3.通过数组的索引设置新的值
  8.     elementData[index] = element;
  9.     return oldValue;
  10. }
(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]
  6. System.out.println(list.get(1));   //B

get方法的实现解读

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

注：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);
  9. System.out.println(numList.indexOf(18));  //2

indexOf的实现解读

  1. public int indexOf(Object o) {
  2.     //１.如果元素为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);
  9. System.out.println(numList.lastIndexOf(18));  //5

lastIndexOf的实现的解读

  1. public int lastIndexOf(Object o) {
  2.    //１.如果元素为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);
  8. numList.sort(new NumSort());
  9. 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);
  8. List<Integer> digitalList = (ArrayList<Integer>) numList.clone();
  9. 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);
  8. 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);
  8. System.out.println(numList.isEmpty()); //false

专题 更多...

分类 更多...

展开

标签 更多...

归档 更多...

展开