1. ArrayList集合底层数据结构

  1. ArrayList集合介绍

List 接口的可调整大小的数组实现。

数组:一旦初始化长度就不可以发生改变

  1. 数组结构介绍
  • 增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。
  • 查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。

2. ArrayList继承关系

2.1 Serializable标记性接口

  1. 介绍 类的序列化由实现java.io.Serializable接口的类启用。 不实现此接口的类将不会使任何状态序列化或反 序列化。 可序列化类的所有子类型都是可序列化的。 序列化接口没有方法或字段，仅用于标识可串行化的语 义。

    序列化:将对象的数据写入到文件(写对象)

    反序列化:将文件中对象的数据读取出来(读对象) 2. Serializable源码介绍

  2. Serializable源码介绍

1
2
public interface Serializable { 
}

案例: 通过序列化流序列化和反序列化集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.io.Serializable;

/**
 * @author zzxx
 */
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Student implements Serializable{
    //姓名
    private String name;
    //年龄
    private Integer age;

    /*
        分析:
            创建StringBuilder对象
            先追加一个当前类的类名,以及大括号、成员变量的名字以及='
            再追加成员变量对应的值
            再追加', 成员变量的名字以及=
            最后再次追加成员变量的名字 和 大括号
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Student{name='");
        sb.append(this.name);
        sb.append("', age=");
        sb.append(this.age);
        sb.append("}");
        return sb.toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package com.heima.serDemo.demo;

import com.heima.serDemo.domain.Student;

import java.io.*;
import java.util.ArrayList;

/**
 * @author zzxx
 * @since JDK 1.8
 *
 * 需求:
 *      已知4个学生对象,要求将4个学生对象序列化到当前模块根路径下的stu.txt中
 *      序列化成功后,请通过反序列化将文件中的数据读取出来,且打印到控制台
 *
 * 分析:
 *      创建ArrayList集合
 *      将要序列化的学生对象添加到集合
 *      序列化一次集合即可
 *      反序列化一次集合
 *      遍历集合
 */
public class SerTest02 {
    public static void main(String[] args) throws Exception {
        Student s1 = new Student("悔创阿里杰克马",51);
        Student s2 = new Student("会打一点长几颗",26);
        Student s3 = new Student("容颜老去蒋青青",32);
        Student s4 = new Student("将里最丑刘一飞",27);
        //创建ArrayList集合
        ArrayList<Student> list = new ArrayList<Student>();
        list.add(s1);
        list.add(s2);
        list.add(s3);
        list.add(s4);
        //创建对象操作流
        ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("Test\\stu.txt"));
        //将集合写入到文件
        oos.writeObject(list);
        //关闭流
        oos.close();

        //反序列化
        //创建对象操作流
        ObjectInputStream ois = new ObjectInputStream(new FileInputStream("Test\\stu.txt"));
        //读数据
        ArrayList<Student> list1 = (ArrayList<Student>) ois.readObject();
        //遍历集合
        for (Student student : list1) {
            System.out.println(student);
        }
    }
}

2.2 Cloneable 标记性接口

  1. 介绍 一个类实现 Cloneable 接口来指示 Object.clone() 方法，该方法对于该类的实例进行字段的复制是合 法的。在不实现 Cloneable 接口的实例上调用对象的克隆方法会导致异常 CloneNotSupportedException 被抛 出。简言之:克隆就是依据已经有的数据，创造一份新的完全一样的数据拷贝
  2. Cloneable源码介绍
1
2
public interface Cloneable { 
}
  1. 克隆的前提条件
    • 被克隆对象所在的类必须实现 Cloneable 接口
    • 必须重写 clone 方法
  2. clone的基本使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package com.heima.cloneDemo.demo;

import java.util.ArrayList;

/**
 * @author zzxx
 * @since JDK 1.8
 *
 * 克隆的基本使用:
 *         将ArrayList集合的数据clone到另外一个集合
 */
public class ArrayList_Clone {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        list.add("人生就是旅途");
        list.add("也许终点和起点会重合");
        list.add("但是一开始就站在起点等待终点");
        list.add("那么其中就没有美丽的沿途风景和令人难忘的过往");

        //调用方法进行克隆
        Object o = list.clone();
        System.out.println(o == list);
        System.out.println(o);
        System.out.println(list);
    }
}

输出
false
[人生就是旅途, 也许终点和起点会重合, 但是一开始就站在起点等待终点, 那么其中就没有美丽的沿途风景和令人难忘的过往]
[人生就是旅途, 也许终点和起点会重合, 但是一开始就站在起点等待终点, 那么其中就没有美丽的沿途风景和令人难忘的过往]
  1. clone源码分析
1
2
3
4
5
6
7
8
9
10
11
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

案例:已知 A 对象的姓名为豹子头林冲，年龄30 。由于项目特殊要求需要将该对象的数据复制另外一个对象 B 中，并且此后 A 和 B 两个对象的数据不会相互影响

案例:已知 A 对象的姓名为鲁智深，年龄30,技能为倒拔垂杨柳 (技能为一个引用数据类型 Skill )，由于项目 特殊要求需要将该对象的数据复制另外一个对象 B 中，并且此后 A 和 B 两个对象的数据不会相互影响

方式一:创建两个对象模拟

  1. 准备学生类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package com.heima.cloneDemo.domain;

/**
 * @author zzxx
 * @since JDK 1.8
 */
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Student implements Cloneable{
    //姓名
    private String name;
    //年龄
    private int age;


}

  1. 准备测试类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class CloneTest01 {
  public static void main(String[] args) {
      //传统方式:
      //创建学生对象
      Student stu1 = new Student("豹子头林冲",30);
      //再次创建一个新的学生对象
      Student stu2 = new Student();
      //把stu1对象name的值取出来赋值给stu2对象的name
      stu2.setName(stu1.getName());
      //把stu1对象age的值取出来赋值给stu2对象的age
      stu2.setAge(stu1.getAge());

      System.out.println(stu1 == stu2);
      System.out.println(stu1);
      System.out.println(stu2);

      System.out.println("----此时不管修改哪个对象的内容,stu1和stu2都不会受到影响----");
      stu1.setName("扈三娘");
      System.out.println(stu1);
      System.out.println(stu2);
  }

  1. 控制台效果

    false Student{name=’豹子头林冲’, age=29} Student{name=’豹子头林冲’, age=29} —-此时不管修改哪 个对象的内容,stu1和stu2都不会受到影响—- Student{name=’扈三娘’, age=29} Student{name=’豹子 头林冲’, age=29}

方式二:使用克隆

  • 浅克隆

1.定义Javabean类

学生技能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * @author zzxx
 * @since JDK 1.8
 */
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Skill implements Cloneable{
    private String skillName;
    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
}

学生类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package com.heima.cloneDemo.domain;

/**
 * @author zzxx
 * @since JDK 1.8
 */
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Student implements Cloneable{
    //姓名
    private String name;
    //年龄
    private int age;
    //技能
    private Skill skill;

  
    /*
        注意:
            首先方法的权限修饰符需要更改为public
            方法的返回值可以更改为当前类的类名
     */
    @Override
    public Object clone() throws CloneNotSupportedException {
        return super.clone();     
    }

}

2.定义测试类

测试类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Test01{
     public static void main(String[] args) {
         //用自定义对象演示 深浅拷贝
          Skill skill = new Skill("倒拔垂杨柳");
          Student s = new Student("鲁智深",31,skill);
         // 调用clone方法进行克隆
          Student obj = s.clone();
         // 比较地址
          System.out.println(s == obj);
          System.out.println("被克隆对象:  "+s);
          System.out.println("----华丽的分割线----");
          //克隆之后,更改skill中的数据        
         skill.setSkillName("荷花酒");        
         //更改克隆后对象的数据        
         obj.setName("扈三娘");
         obj.setAge(19);
         System.out.println("被克隆对象:  "+s);
         System.out.println("克隆出来的对象:  "+obj);

     }
 }

控制台效果

image-20200830165905376

存在的问题: 基本数据类型可以达到完全复制，引用数据类型则不可以

原因: 在学生对象s被克隆的时候，其属性skill(引用数据类型)仅仅是拷贝了一份引用，因此当skill的值发生改 变时，被克隆对象s的属性skill也将跟随改变

  • 深克隆

1.定义Javabean类

学生技能类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package com.heima.cloneDemo.domain;

/**
 * @author zzxx
 * @since JDK 1.8
 */
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Skill implements Cloneable{
    private String skillName;
    
 //重写克隆方法,将权限修饰符改成public 
    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
}

学生类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package com.heima.cloneDemo.domain;

/**
 * @author zzxx
 * @since JDK 1.8
 */
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Student implements Cloneable{
    //姓名
    private String name;
    //年龄
    private int age;
    //技能
    private Skill skill;
  
    /*
        注意:
            首先方法的权限修饰符需要更改为public
            方法的返回值可以更改为当前类的类名
     */
    /*
        注意:
            首先方法的权限修饰符需要更改为public
            方法的返回值可以更改为当前类的类名
     */
    @Override
    public Object clone() throws CloneNotSupportedException {
        //return super.clone();     //深拷贝,不能简单的调用父类的方法
        //先克隆出来一个学生对象
        Student stu = (Student) super.clone();
        //调用Skill类中的克隆方法,克隆出来一个Skill对象
        Skill skill = (Skill) this.skill.clone();
        //将克隆出来的skill赋值给stu该对象的成员变量
        stu.setSkill(skill);
        //需要把stu返回
        return stu;
    }

 
}

2.定义测试类

测试类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Test01 {    
    public static void main(String[] args) throws CloneNotSupportedException {
        //用自定义对象演示 深浅拷贝        
        Skill skill = new Skill("倒拔垂杨柳");    
        Student s = new Student("鲁智深",31,skill);      
        //调用clone方法进行克隆
        Student obj = s.clone();
        //比较地址
        System.out.println(s == obj);
        System.out.println("被克隆对象:  "+s);
                
        System.out.println("克隆出来的对象:  "+obj);  
        System.out.println("----华丽的分割线----");   
        //克隆之后,更改skill中的数据
        skill.setSkillName("荷花酒");
        //更改克隆后对象的数据
        obj.setName("扈三娘");
        obj.setAge(19);
        System.out.println("被克隆对象:  "+s);
        System.out.println("克隆出来的对象:  "+obj);
    }
}

控制台效果

image-20200830171210173

2.3 RandomAccess标记接口

  1. 介绍 标记接口由 List 实现使用，以表明它们支持快速（通常为恒定时间）随机访问。 此接口的主要目的是允许通用算法更改其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性 能。

    用于操纵随机访问列表的佳算法（例如 ArrayList ）可以在应用于顺序访问列表时产生二次行为（如 LinkedList ）。 鼓励通用列表算法在应用如果将其应用于顺序访问列表之前提供较差性能的算法时，检查 给定列表是否为 instanceof ，并在必要时更改其行为以保证可接受的性能。

    人们认识到，随机访问和顺序访问之间的区别通常是模糊的。 例如，一些 List 实现提供渐近的线性访问时 间，如果它们在实践中获得巨大但是恒定的访问时间。 这样的一个 List 实现应该通常实现这个接口。 根据 经验， List 实现应实现此接口，如果对于类的典型实例，此循环：

1
2
for (int i=0, n=list.size(); i < n; i++)            
    list.get(i);

比这个循环运行得更快：

1
2
for (Iterator i=list.iterator(); i.hasNext(); )
    i.next();
  1. 案例演示一·
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Test01 {    
    public static void main(String[] args) {        
        //创建ArrayList集合       
        List<String> list = new ArrayList<>();        
        //添加10W条数据
 
        for (int i = 0; i < 100000; i++) {            
            list.add(i+"a");        
        }
 
        System.out.println("----通过索引(随机访问:)----")
        long startTime = System.currentTimeMillis();        
        for (int i = 0; i < list.size(); i++) {            
            //仅仅为了演示取出数据的时间,因此不对取出的数据进行打印            
            list.get(i);        
        }        
        long endTime = System.currentTimeMillis();        
        System.out.println("随机访问: "+(endTime-startTime));
        
        System.out.println("----通过迭代器(顺序访问:)----");        
        startTime = System.currentTimeMillis();        
        Iterator<String> it = list.iterator();        
        while (it.hasNext()){            
            //仅仅为了演示取出数据的时间,因此不对取出的数据进行打印   
            it.next();        
        }       
        endTime = System.currentTimeMillis();        
        System.out.println("顺序访问: "+(endTime-startTime)); 
    } 
}

控制台效果

—-通过索引(随机访问:)—- 随机访问: 2 —-通过迭代器(顺序访问:)—- 顺序访问: 3

  1. 案例演示二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Test02 {    
    public static void main(String[] args) {        
        //创建LinkedList集合        
        List<String> list = new LinkedList<>();        
        //添加10W条数据        
        for (int i = 0; i < 100000; i++) {            
            list.add(i+"a");
 
            System.out.println("----通过索引(随机访问:)----");
   
            long startTime = System.currentTimeMillis();        
            for (int i = 0; i < list.size(); i++) {            
                //仅仅为了演示取出数据的时间,因此不对取出的数据进行打印            
                list.get(i);        
            }        
            long endTime = System.currentTimeMillis();        
            System.out.println("随机访问: "+(endTime-startTime));     
            System.out.println("----通过迭代器(顺序访问:)----");        
            startTime = System.currentTimeMillis();        
            Iterator<String> it = list.iterator();        
            while (it.hasNext()){            
                //仅仅为了演示取出数据的时间,因此不对取出的数据进行打印            
                it.next();        
            }        
            endTime = System.currentTimeMillis();        
            System.out.println("顺序访问: "+(endTime-startTime));    
        } 
    }

控制台效果

—-通过索引(随机访问:)—- 随机访问: 33759 —-通过迭代器(顺序访问:)—- 顺序访问: 9

为什么LinkedList随机访问比顺序访问要慢这么多?

源码分析

随机访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//每次LinkedList对象调用get方法获取元素,都会执行以下代码 
list.get(i);
 
public class LinkedList<E> {    
    public E get(int index) {        
        //检验是否有效        
        checkElementIndex(index);        
        //调用node(index)        
        return node(index).item;    
    }        
    //node方法     
    Node<E> node(int index) {         
        //node方法每次被调用的时候都会根据集合size进行折半动作         
        //判断get方法中的index是小于集合长度的一半还是大于        
        if (index < (size >> 1)) {            
            //如果小于就从链表的头部一个个的往后找            
            Node<E> x = first;            
            for (int i = 0; i < index; i++)                
                x = x.next;
               } else {            
            Node<E> x = last;            
            //如果大于就从链表的尾部一个个的往前找            
            for (int i = size - 1; i > index; i--)                
                x = x.prev;            
            return x;        
        }    
    } 
}

顺序访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class LinkedList<E>{    
    public ListIterator<E> listIterator(int index) {        
        //检查索引位置        
        checkPositionIndex(index);        
        //返回ListItr对象        
        return new ListItr(index);    
    }        
    //LinkedList迭代器实现类    
    private class ListItr implements ListIterator<E> {        
        private Node<E> lastReturned;        
        private Node<E> next;        
        private int nextIndex;        
        //将实际修改集合次数赋值给预期修改次数        
        private int expectedModCount = modCount;                
        ListItr(int index) {            
            //判断 0 == size,实际上就是调用 node(index)方法            
            next = (index == size) ? null : node(index);            
            //将index的值赋值给 nextIndex,便于下次查找            
            nextIndex = index;        
        }    
    }        
    Node<E> node(int index) {        
        //在获取迭代器的时候也会进行折半的动作        
        //但是在获取迭代器的时候 index 一定是0,因此 if的条件成立        
        if (index < (size >> 1)) {
            
         //由于循环条件不成立,不会执行 x.next;            
            for (int i = 0; i < index; i++)                
                x = x.next;            
            return x;   //返回第一个元素        
        } else {            
            Node<E> x = last;            
            for (int i = size - 1; i > index; i--)                
                x = x.prev;            
            return x;        
        }    
    } 
}
 
//迭代器调用 hasNext()方法的时候,会执行以下代码 
private class ListItr implements ListIterator<E> {    
    public boolean hasNext() {        
    //如果nextIndex < 集合的长度,就说明还有元素,可以进行next        
        return nextIndex < size;    
    } 
}
 
//当迭代器调用it.next();方法的时候会执行以下代码 it.next(); 
public class LinkedList<E>{    
    private class ListItr implements ListIterator<E> {        
    public E next() {            
        checkForComodification();   
        //检查集合实际修改次数和预期次数是否一样            
        //再次判断是否有元素            
        if (!hasNext())                
            throw new NoSuchElementException();            
        //将链表的第一个元素赋值给lastReturned            
        lastReturned = next;            
        //将下一个元素赋值给next            
        next = next.next;            
        //nextIndex++            
        nextIndex++;            
        //返回第一个元素            
        return lastReturned.item;        
        }    
    } 
}

小结: 由于随机访问的时候源码底层每次都需要进行折半的动作，再经过判断是从头还是从尾部一个个寻找。 而顺序访问只会在获取迭代器的时候进行一次折半的动作,以后每次都是在上一次的基础上获取下一个元素。 因此顺序访问要比随机访问快得

3. ArrayList源码分析

3.1 构造方法

Constructor Constructor描述
ArrayList() 构造一个初始容量为十的空列表。
ArrayList(int initialCapacity) 构造具有指定初始容量的空列表。
ArrayList(Collection<? extends E> c) 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回 的顺序。

1. 空参构造ArrayList()

1
2
3
4
5
6
7
8
public class Test01 {
    public static void main(String[] args) {
        //这行代码做了什么?
        //真的构造一个初始容量为十的空列表?
        ArrayList<String> list = new ArrayList<String>();
        
    }
}

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
public class ArrayList<E> {
    //默认空容量的数组,长度为0
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}

    //集合真正存储数据的容器
    Object[] elementData;

    //空参构造
    public ArrayList() {
        //赋值
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
}

结论

通过空参构造方法创建集合对象并未构造一个初始容量为十的空列表，仅仅将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址赋值给elementData

2. 指定容量ArrayList(int initialCapacity)

1
2
3
4
5
6
7
public class Test02 {
    public static void main(String[] args) {
        //这行代码ArrayList底层做了什么?
        ArrayList<String> list = new ArrayList<String>(5);
    }
}

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class ArrayList<E> {
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //指定容量的构造方法
    public ArrayList(int initialCapacity) {
        //判断容量是否大于0
        if (initialCapacity > 0) {
            //根据构造方法的参数创建指定长度的数据
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //将空数组的地址赋值给elementData
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //制造出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
}

结论

根据 ArrayList 构造方法参数创建指定长度的数组

3. ArrayList(Collection<? extends E> c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Test03 {
    public static void main(String[] args) {
        //ArrayList(Collection <? extends E> c) 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
        ArrayList<String> list = new ArrayList<String>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");

        //这行代码做了什么?
        ArrayList<String> list1 = new ArrayList<>(list);

        for (String s : list1) {
            System.out.println(s);
        }
    }
}

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    public ArrayList(Collection<? extends E> c) {
        //将构造方法中的参数转成数组
        elementData = c.toArray();

        if ((size = elementData.length) != 0) {
            // 再次进行判断
            if (elementData.getClass() != Object[].class)
                // 数组的创建和拷贝
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 就把空数组的地址赋值给集合存元素的数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    //将集合转数组的方法
    public Object[] toArray() {
        //调用数组工具类的方法
        return Arrays.copyOf(elementData, size);
    }
}

class Arrays {
    public static <T> T[] copyOf(T[] original, int newLength) {
        //再次调用方法得到一个数组
        return (T[]) copyOf(original, newLength, original.getClass());
    }

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        //不管三元运算符的结果如何,都会创建一个新的数组
        //新数组的长度一定是和集合的size一样
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        //数组的拷贝
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        //返回新数组
        return copy;
    }
}

3.2 添加方法

方法名 描述
public boolean add(E e) 将指定的元素追加到此列表的末尾。
public void add(int index, E element) 在此列表中的指定位置插入指定的元素。
public boolean addAll(Collection<? extends E> c) 按指定集合的Iterator返回的顺序将指定集合中的所有元素 追加到此列表的末尾。
public boolean addAll(i nt index, Collection<? extends E> c) 将指定集合中的所有元素插入到此列表中，从指定的位置 开始。

添加单个元素

public boolean add(E e) 添加单个元素

1
2
3
4
5
6
7
public class Test01 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("黑马程序员");

    }
}

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
            modCount++;

        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // >> : 右移,右移几位就相当于除以2的几次幂
        // << : 左移,左移几位就相当于乘以2的几次幂
        //扩容的核心算法: 原容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 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);
    }


 }

在指定索引处添加元素

public void add(int index, E element) 在指定索引处添加元素

1
2
3
4
5
6
7
8
9
10
public class Test02 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("黑马程序员");
        list.add("传智播客");
        list.add("传智大学");
        list.add(1, "长沙校区");
        System.out.println(list);
    }
}

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    public void add(int index, E element) {
            rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

     private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        //只有容量不够的情况下才会调用 核心扩容的grow方法
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
     }

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

 }

将集合的所有元素一次性添加到集合

public boolean addAll(Collection<? extends E> c) 将集合的所有元素一次性添加到集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Test03 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("黑马程序员");
        list.add("传智播客");
        list.add("传智大学");
        ArrayList<String> list1 = new ArrayList<>();
        //将list集合的所有元素一次性添加到集合list1
        list1.addAll(list);

        System.out.println(list);
        System.out.println(list1);
    }
}

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    public boolean addAll(Collection<? extends E> c) {
        //把有数据的集合转成数组
        Object[] a = c.toArray();
        //有数据集合长度赋值给numNew
        int numNew = a.length;
        //校验以及扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //真正拷贝的代码
        System.arraycopy(a, 0, elementData, size, numNew);
        //集合的长度进行更改
        size += numNew;
        //根据numNew的值返回是否添加成功
        return numNew != 0;
    }

 }

 //结论:底层使用了System.arraycopy方法进行了拷贝

在指定的索引位置添加集合

public boolean addAll(int index, Collection<? extends E> c) 在指定的索引位置添加集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Test04 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("黑马程序员");
        list.add("传智播客");
        list.add("传智大学");
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("酷丁鱼");
        list1.add("博学谷");
        //在指定索引处添加一个集合
        list1.addAll(1,list);

        System.out.println(list);
        System.out.println(list1);
    }
}

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

     public boolean addAll(int index, Collection<? extends E> c) {
        //校验索引
        rangeCheckForAdd(index);
        //将数据源转成数组
        Object[] a = c.toArray();
        //记录数据源的长度 3
        int numNew = a.length;
        //目的就是为了给集合存储数据的数组进行扩容
        ensureCapacityInternal(size + numNew);

        //numMoved:代表要移动元素的个数 --> 1个
        //numMoved: 数据目的(集合list1)的长度-调用addAll的第一个参数 (索引1)
        int numMoved = size - index;
        //判断需要移动的个数是否大于0
        if (numMoved > 0)
            //使用System中的方法arraycopy进行移动
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        //才是真正将数据源(list)中的所有数据添加到数据目的(lsit1)
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 }

public final class System {

    参数
            src - 源数组。
            srcPos - 源数组中的起始位置。
            dest - 目标数组。
            destPos - 目的地数据中的起始位置。
            length - 要复制的数组元素的数量。

    public static void arraycopy​(Object src,int srcPos,Object dest,int destPos,int length)
}

3.3 删除方法

根据索引删除元素

public E remove(int index) 根据索引删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Test01 {    
    public static void main(String[] args) {        
        ArrayList<String> list = new ArrayList<>();        
        list.add("山东大李逵");        
        list.add("天魁星宋江");        
        list.add("天罡星卢俊义");        
        list.add("西门大人");
 
        //根据索引删除元素        
        String value = list.remove(3);        
        System.out.println("删除的元素为: "+value);        
        System.out.println("集合的元素: "+list);  
    } 
}

效果图

image-20200830220410538

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ArrayList<E> {    
    public E remove(int index) {        
        //范围校验        
        rangeCheck(index);       
        //增量++        
        modCount++;        
        //将index对应的元素赋值给 oldValue        
        E oldValue = elementData(index);        
        //计算集合需要移动元素个数        
        int numMoved = size - index - 1;        
        //如果需要移动元素个数大于0,就使用arrayCopy方法进行拷贝        
        //注意:数据源和数据目的就是elementData        
        if (numMoved > 0) 
            System.arraycopy(elementData, index+1, elementData, index,numMoved);        
        //将源集合后一个元素置为null,尽早让垃圾回收机制对其进行回收        
        elementData[--size] = null;        
        //返回被删除的元素        
        return oldValue;    
    } 
}

根据元素删除元素

public boolean remove(Object o) 根据元素删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Test01 {    
    public static void main(String[] args) {        
        ArrayList<String> list = new ArrayList<>();
        list.add("山东大李逵");        
        list.add("天魁星宋江");        
        list.add("西门大人");        
        list.add("天罡星卢俊义");
 
        //根据索引删除元素   
        boolean flag = list.remove("西门大人");        
        System.out.println("是否删除成功: "+flag);        
        System.out.println("集合的元素: "+list);
    } 
}

效果

image-20200830220808748

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class ArrayList<E> {    
    public boolean remove(Object o) {        
        //判断要删除的元素是否为null        
        if (o == null) {            
            //遍历集合            
            for (int index = 0; index < size; index++)     
                //判断集合的元素是否为null                
                if (elementData[index] == null) { 
                    //如果相等,调用fastRemove方法快速删除 
                    fastRemove(index);                    
                    return true;                
                }        
        } else {            
            //遍历集合            
            for (int index = 0; index < size; index++)                
                //用o对象的equals方法和集合每一个元素进行比较                
                if (o.equals(elementData[index])) {                    
                    //如果相等,调用fastRemove方法快速删除                    
                    fastRemove(index);                    
                    return true;                
                }        
        }        
        //如果集合没有o该元素,那么就会返回false        
        return false;    
    }        
    private void fastRemove(int index) {
          
        //增量++        
        modCount++;        
        //计算集合需要移动元素的个数        
        int numMoved = size - index - 1;        
        //如果需要移动的个数大于0,调用arrayCopy方法进行拷贝        
        if (numMoved > 0)            
            System.arraycopy(elementData, index+1, elementData, index,numMoved);        
        //将集合后一个元素置为null,尽早被释放        
        elementData[--size] = null;     
    } 
}

3.4 修改方法

根据索引修改集合元素

public E set(int index, E element) 根据索引修改集合元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Test01 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("山东大李逵");
        list.add("天魁星宋江");
        list.add("天罡星卢俊义");
        list.add("西门大人");

        //根据索引修改集合元素
        String value = list.set(3, "花和尚鲁智深");
        System.out.println("set方法返回值: "+value);
        System.out.println("集合的元素: "+list);
    }
}

效果

image-20200830222350977

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    public E set(int index, E element) {
        //校验索引
        rangeCheck(index);
        //根据索引取出元素 --> 被替换的元素
        E oldValue = elementData(index);
        //把element存入到elementData数组中
        elementData[index] = element;
        //返回被替换的元素
        return oldValue;
    }

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 }

3.5 获取方法

根据索引获取元素

public E get(int index) 根据索引获取元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Test01 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("山东大李逵");
        list.add("天魁星宋江");
        list.add("天罡星卢俊义");
        list.add("西门大人");

        //根据索引获取集合元素
        String value = list.get(1);
        System.out.println("get方法返回值: "+value);
        System.out.println("集合的元素: "+list);
    }
}

效果

image-20200830223721993

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;


    public E get(int index) {
        //校验索引
        rangeCheck(index);
        //根据索引获取数组(集合)中的元素
        return elementData(index);
    }

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 }

3.6 转换方法

把集合所有数据转换成字符串

public String toString() 把集合所有数据转换成字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Test01 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("山东大李逵");
        list.add("天魁星宋江");
        list.add("天罡星卢俊义");
        list.add("西门大人");

        //将集合的元素转换为字符串
        String str = list.toString();
        System.out.println(str);

        //System.out.println("集合的元素: "+list);
    }
}

效果

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;
 }

 //ArrayList集合的亲爷爷类
 public abstract class AbstractCollection<E> {

    public String toString() {
        //获取迭代器
        Iterator<E> it = iterator();
        //判断迭代器是否有元素
        if (! it.hasNext())
            return "[]";
        //创建StringBuilder
        StringBuilder sb = new StringBuilder();
        //先追加了'['
        sb.append('[');
        //无限循环
        for (;;) {
            //调用迭代器的next方法取出元素,且将光标向下移动
            E e = it.next();
            //三元判断
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                //没有元素,在缓冲区的最后追加']',且把整个缓冲区的数据转成字符串
                //然后再介绍该方法
                return sb.append(']').toString();

            //有元素,就直接追加
            sb.append(',').append(' ');
        }
    }
 }

3.7 迭代器

普通迭代器

public Iterator iterator() 普通迭代器

案例一: 已知集合：List list = new ArrayList();里面有三个元素：”hello”、”Java”、”PHP”，使用迭代器遍 历获取集合的每一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Test01 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<String>();
        //添加元素
        list.add("hello");
        list.add("Java");
        list.add("PHP");
        //获取迭代器
        Iterator<String> it = list.iterator();
        //遍历集合
        while (it.hasNext()) {
            String s = it.next();
            System.out.println(s);
        }
    }
}

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    //获取迭代器的方法
    public Iterator<E> iterator() {
        //创建了一个对象
        return new Itr();
    }

    //ArrayList集合的内部类 --> 迭代器的源码
    private class Itr implements Iterator<E> {
        int cursor;       // 光标,默认值就是0
        int lastRet = -1; // 记录-1
        // 将集合实际修改次数赋值给预期修改次数
        int expectedModCount = modCount;

        //判断集合是否有元素
        public boolean hasNext() {
            //光标是否不等于集合的size 3
            return cursor != size;
        }

        public E next() {
            checkForComodification();
            //光标赋值给i = 0
            int i = cursor;
            //判断,如果大于集合的size就说明没有元素了
            if (i >= size)
                throw new NoSuchElementException();
            //把集合存储数据数组的地址赋值给该方法的局部变量
            Object[] elementData = ArrayList.this.elementData;
            //进行判断,如果条件满足就会产生并发修改异常
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            //光标自增
            cursor = i + 1;
            //从数组中取出元素且返回
            return (E) elementData[lastRet = i];
        }

        //校验预期修改集合次数是否和实际修改集合次数一样
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

 }

案例二: 已知集合：List list = new ArrayList();里面有三个元素：”hello”、”Java”、”PHP”，使用迭代器遍 历集合看有没有”PHP”这个元素，如果有，就使用集合对象删除该元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Test02 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<String>();
        //添加元素
        list.add("hello");
        list.add("Java");
        list.add("PHP");
        //获取迭代器
        Iterator<String> it = list.iterator();
        //遍历集合
        while (it.hasNext()) {
            String s = it.next();
            if(s.equals("PHP")) {
                list.remove("PHP");
            }
        }
    }
}

控制台结果:并发修改异常

Exception in thread “main” java.util.ConcurrentModificationException at

java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901) at

java.util.ArrayList$Itr.next(ArrayList.java:851) at cn.itheima.method.Test01.main(Test01.java:24)

源码分析:(应该从获取迭代器的时候就进入到源代码中)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    //查看add方法其目的就是为了找到记录集合实际修改次数的变量
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    //获取迭代器的方法
    public Iterator<E> iterator() {
        //创建了一个对象
        return new Itr();
    }

    //ArrayList集合的内部类 --> 迭代器的源码
    private class Itr implements Iterator<E> {
        int cursor;       // 光标,默认值就是0
        int lastRet = -1; // 记录-1
        // 将集合实际修改次数赋值给预期修改次数
        // 获取迭代器的时候,那么expectedModCount的值也就是 3
        int expectedModCount = modCount;

        //判断集合是否有元素
        public boolean hasNext() {
            //光标是否不等于集合的size 3
            return cursor != size;
        }

        public E next() {
            checkForComodification();
            //光标赋值给i = 0
            int i = cursor;
            //判断,如果大于集合的size就说明没有元素了
            if (i >= size)
                throw new NoSuchElementException();
            //把集合存储数据数组的地址赋值给该方法的局部变量
            Object[] elementData = ArrayList.this.elementData;
            //进行判断,如果条件满足就会产生并发修改异常
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            //光标自增
            cursor = i + 1;
            //从数组中取出元素且返回
            return (E) elementData[lastRet = i];
        }

        //校验预期修改集合次数是否和实际修改集合次数一样
        final void checkForComodification() {
            if (modCount != expectedModCount)
                //如果不一样,就会产生并发修改异常
                throw new ConcurrentModificationException();
        }
    }

    //集合删除元素的方法
    public boolean remove(Object o) {
        //判断要删除的元素是否为null
        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;
    }

    //真正删除元素的方法
    private void fastRemove(int index) {
        //在删除的方法中集合实际修改次数会自增
        //集合实际修改次数为:4 但是预期修改次数为:3
        modCount++;
        //计算集合要移动元素的个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //移动的核心代码
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //就是让删除的元素置为null,就是为了尽快被垃圾回收机制回收
        elementData[--size] = null; // clear to let GC do its work
    }

 }

 结论:
    一,集合每次调用add方法的时候,实际修改次数变量的值都会自增一次
    二,在获取迭代器的时候,集合只会执行一次将实际修改集合的次数赋值给预期修改集合的次数
    三,集合在删除元素的时候也会针对实际修改次数的变量进行自增的操作

案例三:已知集合：List list = new ArrayList();里面有三个元素：”hello”、”PHP”、”JavaSE”，使用迭代器 遍历集合看有没有”PHP”这个元素，如果有，就使用集合对象删除该元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Test03 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<String>();
        //添加元素
        list.add("hello");
        list.add("PHP");
        list.add("Java");

        //获取迭代器
        Iterator<String> it = list.iterator();
        //遍历集合
        while (it.hasNext()) {
            String s = it.next();
            if(s.equals("PHP")) {
                list.remove("PHP");
            }
        }

        System.out.println(list);
    }
}

结果图

image-20200831191430709

结论

1
2
3
4
5
结论:
   当要删除的元素在集合的倒数第二个位置的时候,不会产生并发修改异常
原因:
   是因为在调用hasNext方法的时候,光标的值和集合的长度一样,那么就会返回false
   因此就不会再去调用next方法获取集合的元素,既然不会调用next方法那么底层就不会产生并发修改异常

图解

image-20200831191504886

迭代器中的remove方法（不是上面Arraylist中的）,删除集合中的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Test04 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<String>();
        //添加元素
        list.add("hello");
        list.add("PHP");
        list.add("Java");
        //获取迭代器
        Iterator<String> it = list.iterator();
        //遍历集合
        while (it.hasNext()) {
            String s = it.next();
            if(s.equals("hello")) {
                it.remove();
            }
        }
        System.out.println(list);
    }
}

结果图

image-20200901232818730

源码分析(应该从获取迭代器的时候就进入到源代码中)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    //查看add方法其目的就是为了找到记录集合实际修改次数的变量
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    //获取迭代器的方法
    public Iterator<E> iterator() {
        //创建了一个对象
        return new Itr();
    }

    //ArrayList集合的内部类 --> 迭代器的源码
    private class Itr implements Iterator<E> {
        int cursor;       // 光标,默认值就是0
        int lastRet = -1; // 记录-1
        // 将集合实际修改次数赋值给预期修改次数
        // 获取迭代器的时候,那么expectedModCount的值也就是 3
        int expectedModCount = modCount;

        //判断集合是否有元素
        public boolean hasNext() {
            //光标是否不等于集合的size 3
            return cursor != size;
        }

         //迭代器自带的方法
         public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                //把实际修改集合次数赋值给预期修改次数
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public E next() {
            checkForComodification();
            //光标赋值给i = 0
            int i = cursor;
            //判断,如果大于集合的size就说明没有元素了
            if (i >= size)
                throw new NoSuchElementException();
            //把集合存储数据数组的地址赋值给该方法的局部变量
            Object[] elementData = ArrayList.this.elementData;
            //进行判断,如果条件满足就会产生并发修改异常
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            //光标自增
            cursor = i + 1;
            //从数组中取出元素且返回
            return (E) elementData[lastRet = i];
        }

        //校验预期修改集合次数是否和实际修改集合次数一样
        final void checkForComodification() {
            if (modCount != expectedModCount)
                //如果不一样,就会产生并发修改异常
                throw new ConcurrentModificationException();
        }
    }

    //集合删除元素的方法
    public boolean remove(Object o) {
        //判断要删除的元素是否为null
        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;
    }

    //真正删除元素的方法
    private void fastRemove(int index) {
        //在删除的方法中集合实际修改次数会自增
        //集合实际修改次数为:4 但是预期修改次数为:3
        modCount++;
        //计算集合要移动元素的个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //移动的核心代码
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //就是让删除的元素置为null,就是为了尽快被垃圾回收机制回收
        elementData[--size] = null; // clear to let GC do its work
    }

    //集合删除的方法
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

 }

 结论:
    一,迭代器调用remove方法删除元素,其实底层真正还是调用集合自己的删除方法来删除元素
    二,在调用remove方法中会每次都给预期修改次数的变量赋值

3.8 清空方法

清空集合所有数据

public void clear() 清空集合所有数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Test01 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<String>();
        //添加元素
        list.add("hello");
        list.add("PHP");
        list.add("Java");
        System.out.println("清空前的集合: "+list);
        //清空集合所有元素
        list.clear();
        System.out.println("清空后的集合: "+list);
    }
}

效果图

image-20200901233032488

源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class ArrayList<E> {
	//长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    //清空集合元素的方法
    public void clear() {
        //实际修改次数自增
        modCount++;
        //遍历集合
        for (int i = 0; i < size; i++)
            //把数组的每一个位置都置为null,让垃圾回收期尽早地回收
            elementData[i] = null;
        //把集合的长度置为0
        size = 0;
    }
}

3.9 包含方法

判断集合是否包含指定元素

public boolean contains(Object o) 判断集合是否包含指定元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Test01 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<String>();
        //添加元素
        list.add("hello");
        list.add("PHP");
        list.add("Java");

        //需求:如果集合中没有JavaSE该元素,请添加一个JavaSE元素
        //method(list);

        //解决方式二:使用集合contains方法判断,根据判断的结果决定是否要添加元素
        if (!list.contains("JavaSE")){
            //添加元素到集合
            list.add("JavaSE");
        }

        System.out.println(list);

    }

    private static void method(List<String> list) {
        //解决方式一:循环遍历集合,判断集合是否包含JavaSE,如果没有包含就调用集合的add方法进行添加操作
        //定义一个标记
        boolean flag = false;
        //遍历集合
        for (String value : list) {
            //对遍历到的元素进行判断
            if(value.equals("JavaSE")){
                //更改标记的值
                flag = true;
                //结束循环
                break;
            }
        }

        //根据标记的状态决定是否要添加元素到集合
        if(!flag){
            //添加元素到集合
            list.add("JavaSE");
        }

        System.out.println(list);
    }
}

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    //判断是否包含的方法
    public boolean contains(Object o) {
        // 根据 indexOf方法返回的结果 和 0 进行比较
        // 如果大于等于0 就说明找到(包含)了,否则就说明没有找到(未包含)
        return indexOf(o) >= 0;
    }

    public int indexOf(Object o) {
        //判断要找的元素否为null
        if (o == null) {
            //循环遍历集合
            for (int i = 0; i < size; i++)
                //进行判断
                if (elementData[i]==null)
                    //找到之后返回该元素的索引
                    return i;
        } else {
            //循环遍历集合
            for (int i = 0; i < size; i++)
                //拿着集合的每一个元素和要找的元素进行比较内容
                if (o.equals(elementData[i]))
                    //返回该元素在集合的索引
                    return i;
        }
        //在if 和 else中都没有执行return,就返回-1 说明没有找到
        return -1;
    }

}

3.10 判断集合是否为空

public boolean isEmpty()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Test01 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<String>();
        //添加元素
        list.add("hello");
        list.add("PHP");
        list.add("Java");

        boolean b = list.isEmpty();
        System.out.println(b);
        System.out.println(list);
    }
}

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class ArrayList<E> {
    //长度为0的空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //默认容量为空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //集合存元素的数组
    Object[] elementData;

    //集合的长度
    private int size;

    //默认的容量
    private static final int DEFAULT_CAPACITY = 10;

    public boolean isEmpty() {
        //根据集合的长度返回对应的结果
        return size == 0;
    }
 }

4. 面试题

4.1 ArrayList是如何扩容的？

源码分析过程中已经讲解

第一次扩容10

以后每次都是原容量的1.5倍

4.2 ArrayList频繁扩容导致添加性能急剧下降，如何处理？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Test01 {
    public static void main(String[] args) {
        //创建集合对象
        List<String> list = new ArrayList<String>();
        //添加元素
        list.add("hello");
        list.add("PHP");
        list.add("Java");

        long startTime = System.currentTimeMillis();
        //需求:还需要添加10W条数据
        for (int i = 0; i < 100000; i++) {
            list.add(i+"");
        }
        long endTime = System.currentTimeMillis();
        System.out.println("添加10W条数据用时: "+ (endTime - startTime));


        System.out.println("-----------------------------");
        //ArrayList​(int initialCapacity) 构造具有指定初始容量的空列表。
        List<String> list1 = new ArrayList<>(10000);
        //添加之前记录时间
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            list1.add(i+"");
        }
        //循环结束之后记录时间jva
        endTime = System.currentTimeMillis();
        System.out.println("添加10W条数据用时: "+ (endTime - startTime));
    }
}


添加10W条数据用时: 39
-----------------------------
添加10W条数据用时: 4

4.3 ArrayList插入或删除元素一定比LinkedList慢么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Test02 {
    public static void main(String[] args) {
        //创建ArrayList集合对象
        ArrayList<String> arrayList = new ArrayList<String>();
        //添加500W个元素
        for (int i = 0; i < 5000000; i++) {
            arrayList.add(i+"黑马");
        }
        //获取开始时间
        long startTime = System.currentTimeMillis();
        //根据索引删除ArrayList集合元素
        //删除索引5000对应的元素
        String value = arrayList.remove(50000);
        System.out.println(value);
        //获取结束时间
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList集合删除元素的时间: "+(endTime-startTime));

        //创建LinkedList集合对象
        LinkedList<String> linkedList = new LinkedList<String>();
        //添加500W个元素
        for (int i = 0; i < 5000000; i++) {
            linkedList.add(i+"黑马");
        }
        //获取开始时间
        startTime = System.currentTimeMillis();
        //根据索引删除LinkedList集合元素
        //删除索引5000对应的元素
        value = arrayList.remove(50000);
        System.out.println(value);
        endTime = System.currentTimeMillis();
        System.out.println("LinkedList集合删除元素的时间: "+(endTime-startTime));
    }
}

50000黑马
ArrayList集合删除元素的时间: 5
50001黑马
LinkedList集合删除元素的时间: 4

4.4 ArrayList是线程安全的么？

1

4.5 如何复制某个ArrayList到另一个ArrayList中去?

  • 使用clone()方法
  • 使用ArrayList构造方法
  • 使用addAll方法
  • 以上三种方式都在前面有讲

4.6 已知成员变量集合存储N多用户名称,在多线程的环境下,使用迭代器在读 取集合数据的同时如何保证还可以正常的写入数据到集合?

4.7 ArrayList 和 LinkList区别？

  • ArrayList

    • 基于动态数组的数据结构
    • 对于随机访问的get和set，ArrayList要优于LinkedList
    • 对于随机操作的add和remove，ArrayList不一定比LinkedList慢 (ArrayList底层由于是动态数组，因此 并不是每次add和remove的时候都需要创建新数组)

    LinkedList 基于链表的数据结构 对于顺序操作，LinkedList不一定比ArrayList慢 对于随机操作，LinkedList效率明显较

5. 自定义ArrayList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
package com.zzxx.customArrayList;
/**
 * @author zzxx
 *
 * 自定义ArrayList
 *      成员变量
 *      构造方法
 *      添加方法
 *      简单扩容
 *      转换方法&测试
 *      修改&删除&测试
 *
 *      获取方法&测试
 *          根据索引获取元素
 *          获取集合的长度
 */
public class MyArrayList<E> {
    //定义数组,用于存储集合的元素
    private Object[] elementData;
    //定义变量,用于记录数组的个数
    private int size;
    //定义空数组,用于在创建集合对象的时候给elementData初始化
    private Object[] emptyArray = {};
    //定义常量,用于记录集合的容量
    private final int DEFAULT_CAPACITY = 10;

    //构造方法
    public MyArrayList(){
        //给elementData初始化
        elementData = emptyArray;
    }

    //定义add方法
    public boolean add(E e){
        //将来再调用的时候需要判断是否需要扩容
        grow();
        //将元素添加到集合
        elementData[size++] = e;
        return true;
    }

    //简单扩容
    private void grow(){
        //判断集合存储元素的数组是否等于emptyArray
        if(elementData == emptyArray){
            //第一次扩容
            elementData = new Object[DEFAULT_CAPACITY];
        }

        //核心算法 1.5倍
        //如果size==集合存元素数组的长度,就需要扩容
        if(size == elementData.length){
            //先定义变量记录老容量
            int oldCapacity = elementData.length;
            //核心算法 1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //创建一个新的数组,长度就newCapacity
            Object[] obj = new Object[newCapacity];
            //拷贝元素
            System.arraycopy(elementData, 0, obj, 0, elementData.length);
            //把新数组的地址赋值给elementData
            elementData = obj;
        }
    }

    //转换方法
    public String toString(){
        //建议对集合进行判断,如果没有内容直接返回 "[]"
        if(size == 0){
            return "[]";
        }

        //创建StringBuilder
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        //循环遍历数组
        for (int i = 0; i < size; i++) {
            //判断i是否等于size-1
            if(i == size-1){
                //要追加元素,还需要追加]
                sb.append(elementData[i]).append("]");
            }else{
                sb.append(elementData[i]).append(",").append(" ");
            }
        }
        //把sb中的所有数据转成一个字符串,且返回
        return sb.toString();
    }

    //修改方法
    public E set(int index, E element) {
        //建议先对方法的参数索引进行判断
        checkIndex(index);
        //把index索引对应的元素取出来
        E value = (E) elementData[index];
        //替换元素
        elementData[index] = element;
        return value;
    }

    private void checkIndex(int index) {
        if(index < 0 || index >= size){
            //制造一个异常
            throw  new IndexOutOfBoundsException("索引越界了!");
        }
    }

    //删除方法
    public E remove(int index) {
        //校验索引
        checkIndex(index);
        //取出元素
        E value = (E) elementData[index];
        //计算出要移动元素的个数
        int numMoved = size - index - 1;
        //判断要移动的个数是否大于0
        if (numMoved > 0){
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        }
        //把最后一个位置上的元素置为null
        elementData[--size] = null;
        return value;
    }

    //根据索引获取元素
    public E get(int index){
        //调用方法校验索引
        checkIndex(index);
        //直接从elementData数组中获取元素且返回
        return (E) elementData[index];
    }

    //获取集合的长度
    public int getSize(){
        return size;
    }
}