ArrayList学习

忘是亡心i 2024-04-17 18:27 47阅读 0赞

### 文章目录 ###

*   *   *  一、底层数据结构
         *  二、方法思维导图
         *  三、部分方法展示
         *   *  1. 构造方法
             *  2. boolean add(E e)
             *  3. add(int index, E element)
             *  4. void trimToSize()
             *  5. Object clone()
             *  6. set(int index, E element)
             *  7. remove(int index) & remove(Object o)
             *  8. boolean addAll(Collection<? extends E> c)
             *  9. boolean addAll(int index, Collection<? extends E> c)
             *  10. boolean retainAll(Collection<?> c)
             *  11. subList(int fromIndex, int toIndex)

**特点：**  
**1.基于数组实现的有序集合，容量可以扩充**  
**2.在不要求线程安全的情况下，数据查询更推荐使用ArrayList.**

### 一、底层数据结构 ###

private transient Object[] elementData;

可以看出ArrayList是**基于数组**实现的.

### 二、方法思维导图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70]

### 三、部分方法展示 ###

#### 1. 构造方法 ####

public ArrayList(int initialCapacity)； //指定初始容量
    public ArrayList()； // 使用默认初始容量10
    public ArrayList(Collection<? extends E> c)； //以collection子类实例作为初始化参数

#### 2. boolean add(E e) ####

直接上源码. ArrayList添加元素是通过操作缓冲数组**elementData**实现的.

public boolean add(E e) {
            ensureCapacityInternal(size + 1);  //检查容量，如果有需要就进行扩容
            elementData[size++] = e; //赋值
            return true;
        }

private void ensureCapacityInternal(int minCapacity) {
            if (elementData == EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); //是空集合就分配默认容量
            }
    
            ensureExplicitCapacity(minCapacity); //检查容量
        }

private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0) //当前容量已满
                grow(minCapacity); // 扩容
        }

private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            elementData = Arrays.copyOf(elementData, newCapacity); //调用copyOf返回新长度的集合
        }

**Arrays.copyOf**其实是调用了**System.arraycopy**.下面将看到, 涉及到集合的修改时, 基本上都是调用**System.arraycopy**.

#### 3. add(int index, E element) ####

往指定位置添加元素

// 主要代码
    System.arraycopy(elementData, index, elementData, index + 1,  size - index);
    elementData[index] = element;

That means, **当指定插入位置时**, 插入一个元素, 就要移动**size-index**个元素. 且**位置越靠近集合前端, 移动的元素就越多.**

#### 4. void trimToSize() ####

**-该方法就是去掉多分配的容量。**

// 源码
    public void trimToSize() {
            modCount++;
            if (size < elementData.length) {
                elementData = Arrays.copyOf(elementData, size);
            }
        }

// 栗子
    ArrayList a = new ArrayList(4); //分配初始容量为：4
    a.add("a");
    a.add("b");
    a.add("c");
    a.add("d");
    a.add("e"); // 容量增长为:6
                // 元素数量为:5
    a.trimToSize(); // 容量变为:5

#### 5. Object clone() ####

对集合进行浅克隆, 返回一个副本. **当你想在某个集合的基础上进行额外操作, 但不想破坏原集合时可使用.**

// 栗子
    ArrayList a = new ArrayList(4);
    a.add("a");
    a.add("b");
    
    ArrayList a2 = (ArrayList) a.clone();
    
    System.out.println(a); //[a, b]
    System.out.println(a2); //[a, b]
    
    a2.set(0, "b");
    
    System.out.println(a); //[a, b]
    System.out.println(a2); //[b, b]

But, **集合为的元素为引用时要小心, 特别是涉及修改对象属性时** :

Person person = new Person("z3", 100); //自定义类
    
    ArrayList<Person> personList = new ArrayList<>();
    personList.add(person);
    
    List<Person> personList2 = (ArrayList<Person>)personList.clone();
    
    System.out.println(personList); // [Person{name='z3', age=100}]
    System.out.println(personList); // [Person{name='z3', age=100}]
    
    personList2.get(0).setName("Li4"); //修改属性
    
    System.out.println(personList); // [Person{name='Li4', age=100}]
    System.out.println(personList2); // [Person{name='Li4', age=100}]

#### 6. set(int index, E element) ####

修改指定索引的元素并返回被替换的元素

public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

#### 7. remove(int index) & remove(Object o) ####

1.删除集合中**指定索引**处的元素

// 主要代码
    int numMoved = size - index - 1;
    if (numMoved > 0)
     System.arraycopy(elementData, index+1, elementData, index,
    numMoved);
    elementData[--size] = null;

2.根据**元素本身**来删除

public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }

可以观察到, 该删除操作是调用**System.arraycopy**来完成的.

#### 8. boolean addAll(Collection<? extends E> c) ####

Appends all of the elements in the specified collection **to the end of this list**

public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }

#### 9. boolean addAll(int index, Collection<? extends E> c) ####

Inserts all of the elements in the specified collection into this list, **starting at the specified position.**

public boolean addAll(int index, Collection<? extends E> c) {
         rangeCheckForAdd(index);
    
         Object[] a = c.toArray();
         int numNew = a.length;
         ensureCapacityInternal(size + numNew);  // Increments modCount
    
         int numMoved = size - index;
         if (numMoved > 0)
             System.arraycopy(elementData, index, elementData, index + numNew,
                              numMoved);  // 移动数组元素
    
         System.arraycopy(a, 0, elementData, index, numNew); // 填充数组
         size += numNew;
         return numNew != 0;
     }

#### 10. boolean retainAll(Collection<?> c) ####

\-**取两个集合的交集**

// 关键代码
    int r = 0, w = 0;
    
    for (; r < size; r++)
       if (c.contains(elementData[r]) == complement) //complement = true
           elementData[w++] = elementData[r];
    
    ...
    
    if (w != size) {
        // clear to let GC do its work
         for (int i = w; i < size; i++)
             elementData[i] = null;
         modCount += size - w;
         size = w;
         modified = true;
     }

它的思想: **将相等的元素移到数组前列, 然后将其余位置的赋值为null.**

// 栗子
    ArrayList a = new ArrayList(4);
    a.add("a");
    a.add("b");
    a.add("c");
    
    ArrayList b = new ArrayList(4);
    b.add("b");
    
    System.out.println(a); // [a, b, c]
    a.retainAll(b);
    System.out.println(a); // [b]

#### 11. subList(int fromIndex, int toIndex) ####

返回原集合的子集, **子集区间为\[fromIndex, toIndex).** 子集类型为ArrayList的**内部类SubList**

// 源码
    public List<E> subList(int fromIndex, int toIndex) {
            subListRangeCheck(fromIndex, toIndex, size);
            return new SubList(this, 0, fromIndex, toIndex); // 关键代码
        }

// 栗子
    ArrayList<Integer> arrayList = new ArrayList();
    arrayList.add(1);
    arrayList.add(2);
    arrayList.add(3);
    arrayList.add(4);
    
    List<Integer> subList = arrayList.subList(1,3);
    System.out.println(subList);
    // 输出: [2, 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NzZG5MZXJhbmVy_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/8c68cc3dfd6c4e96968472389d5ae164.png