ArrayList学习笔记

标签：index int ArrayList elementData 笔记 学习 public size

目录

• 1、继承关系
  • 1.1、Serializable 标记性接口
  • 1.2、Cloneable 标记性接口
  • 1.3、RandomAccess 标记性接口
• 2、属性
• 3、构造方法
  • 3.1、无参构造方法-ArrayList()
  • 3.2、有参构造方法-ArrayList(int initialCapacity)
  • 3.3、有参构造方法-ArrayList(Collection<? extends E> c)
• 4、方法
  • 4.1、添加方法-add
  • 4.2、删除方法-remove
  • 4.3、修改方法-set
  • 4.4、查找方法-get
  • 4.5、转换方法
• 5、迭代器
• 6、面试题
  • 6.1、ArrayList 和 LinkedList区别 ？
  • 6.2、 ArrayList插入或删除元素一定比LinkedList慢么?
  • 6.3、ArrayList是线程安全的么？
  • 6.4、已知成员变量集合存储N个用户名称，在多线程的环境下,使用迭代器读取集合数据的同时，如何保证还可以正常的写入数据到集合?
  • 6.5、如何复制某个ArrayList到另一个ArrayList中去？

视频学习地址：https://www.bilibili.com/video/BV1gE411A7H8/

1、继承关系

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    
}

1.1、Serializable 标记性接口

1、介绍

类通过实现 java.io.Serializable 接口以启用其序列化功能。

未实现此接口的类将无法使其任何状态序列化或反序列化。

可序列化类的所有子类型本身都是可序列化的。

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

反序列化：将文件中对象的数据读取出来(读对象)

不实现 Serializable 接口，序列化运行时就会抛出异常：NotSerializableException

2、源码

// 序列化接口中没有方法或字段，仅用于标识可序列化的语义。
public interface Serializable {
}

3、示例

关于 serialVersionUID：

为保证 serialVersionUID 值【跨不同的 java 编译器实现】的一致性，序列化类必须显式声明一个明确的 serialVersionUID 值。

还强烈建议使用 private 修饰符显示声明 serialVersionUID（如果可能），原因是这种声明仅应用于直接声明类 -- serialVersionUID 字段作为继承成员没有用处。

数组类不能声明一个明确的 serialVersionUID，因此它们总是具有默认的计算值，但是数组类没有匹配 serialVersionUID 值的要求。

• Student 类

import java.io.Serializable;
 
public class Student implements Serializable {
	private static final long serialVersionUID = 1014100089306623762L;
	private String name;
	private Integer age;

	public Student() {
	}

	public Student(String name, Integer age) {
		this.name = name;
		this.age = age;
	}

	@Override
	public String toString() {
		// 优化toString()方法
		StringBuilder sb = new StringBuilder();
		sb.append("Student[name='")
				.append(this.name)
				.append("\', age=")
				.append(this.age)
				.append("]");
		return sb.toString();
	}

	/*@Override
	public String toString() {
		return "Student{" +
				"name='" + name + '\'' +
				", age=" + age +
				'}';
	}*/

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public Integer getAge() {
		return age;
	}

	public void setAge(Integer age) {
		this.age = age;
	}
}

• 测试类

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

public class Application {
   public static void main(String[] args) throws IOException, ClassNotFoundException {
      ArrayList<Student> studentList = new ArrayList<Student>();
      studentList.add(new Student("张三", 18));
      studentList.add(new Student("李四", 3));
      studentList.add(new Student("王五", 8));
      studentList.add(new Student("赵六", 28));

      writeObject(studentList);
      readObject();
   }

   public static void writeObject(List list) throws IOException {
      ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("StudentList.txt"));
      // 注意：这里写对象(集合)只需要写一次
      oos.writeObject(list);
       // 关闭流
      oos.close();
   }

   public static void readObject() throws IOException, ClassNotFoundException {
      ObjectInputStream ois = new ObjectInputStream(new FileInputStream("StudentList.txt"));
      Object object = ois.readObject();
      // 对读出的对象进行向下强制转型
      ArrayList<Student> studentList = (ArrayList<Student>)object;
      // 遍历list集合输出下内容
      for (int i = 0, listSize = studentList.size(); i < listSize; i++) {
         Student student = studentList.get(i);
         System.out.println(student);
      }
      // 关闭流
      ois.close();
   }
}

1.2、Cloneable 标记性接口

1、介绍

此类实现了 Cloneable 接口，以指示 Object.clone() 方法可以合法地对该类实例进行按字段复制。

如果在没有实现 Cloneable 接口的实例上调用 Object 的 clone 方法，则会导致抛出异常：

CloneNotSupportedException

克隆的前提条件：

• 被克隆的对象所在的类必须实现 Cloneable 接口
• 必须重写 Object 类中的 clone 方法，修改方法权限为 public

实现此接口的类应该使用公共方法重写 Object.clone（重写默认是受保护的）。

2、源码

// 注意，此接口不包含 clone 方法，调用的是 Object 中的 clone 方法
public interface Cloneable {
}

3、浅拷贝和深拷贝

拷贝分类

• 引用拷贝：两个不同的引用指向同一个对象。

• 对象拷贝

  • 浅拷贝
  • 深拷贝

浅拷贝：浅拷贝会在堆上创建一个新的对象（区别于引用拷贝），被拷贝对象内部的基本类型值会被完全复制过去，内部的引用类型仅仅只是复制它引用的地址值，没有再针对内部的对象再创建一个新的对象，而是拷贝对象和被拷贝对象共享同一个内部对象。

深拷贝：深拷贝会完全复制整个对象，包括内部的引用类型对象。

4、举例：浅拷贝

• Student 类

public class Student implements Cloneable{
	private int id;
	private String name;
	private Teacher teacher;

	// 浅拷贝
	@Override
	public Student clone() throws CloneNotSupportedException {
		return (Student)super.clone();
	}

	// 省略 getter/setter 全参/无参构造方法
}

• Teacher 类

public class Teacher implements Cloneable{
	private int id;
	private String name;


	// 浅拷贝
	@Override
	public Teacher clone() throws CloneNotSupportedException {
		return (Teacher)super.clone();
	}
    
	// 省略 getter/setter 全参/无参构造方法
}

• 测试浅拷贝

Teacher teacher1 = new Teacher(1001, "慢羊羊");
Student student1 = new Student(2001, "喜羊羊", teacher1);
// 从 student1 里克隆一个对象：student2
Student student2 = student1.clone();

System.out.println("比较两个对象的地址值：" + (student1 == student2));
System.out.println("student1的地址值：" + student1);
System.out.println("student2的地址值：" + student2);

System.out.println("比较两个对象里内部对象的地址值：" + (student1.getTeacher() == student2.getTeacher()));
System.out.println("student1里的teacher地址值：" + student1.getTeacher());
System.out.println("student2里的teacher地址值：" + student2.getTeacher());

5、举例：深拷贝

对 Student 类中的 clone 方法进行修改，其他类不变

public class Student implements Cloneable{
	private int id;
	private String name;
	private Teacher teacher;

	@Override
	public Student clone() throws CloneNotSupportedException {
		Student student = (Student)super.clone();
		// 深拷贝，对内部引用对象继续拷贝
		student.setTeacher((Teacher) (student.getTeacher().clone()));
		return student;
	}
	// 省略 getter/setter 全参/无参构造方法
}

测试结果：

比较两个对象的地址值：false
student1的地址值：com.test.Student@78c03f1f
student2的地址值：com.test.Student@5ec0a365
比较两个对象里内部对象的地址值：true
student1里的teacher地址值：com.test.Teacher@4fe3c938
student2里的teacher地址值：com.test.Teacher@4fe3c938

• 测试浅拷贝

Teacher teacher1 = new Teacher(1001, "慢羊羊");
Student student1 = new Student(2001, "喜羊羊", teacher1);
// 从 student1 里克隆一个对象：student2
Student student2 = student1.clone();

System.out.println("比较两个对象的地址值：" + (student1 == student2));
System.out.println("student1的地址值：" + student1);
System.out.println("student2的地址值：" + student2);

System.out.println("比较两个对象里内部对象的地址值：" + (student1.getTeacher() == student2.getTeacher()));
System.out.println("student1里的teacher地址值：" + student1.getTeacher());
System.out.println("student2里的teacher地址值：" + student2.getTeacher());

测试结果：

比较两个对象的地址值：false
student1的地址值：com.test.Student@78c03f1f
student2的地址值：com.test.Student@5ec0a365
比较两个对象里内部对象的地址值：false
student1里的teacher地址值：com.test.Teacher@4fe3c938
student2里的teacher地址值：com.test.Teacher@5383967b

1.3、RandomAccess 标记性接口

实现了该接口的话，使用普通的 for 循环来遍历，性能更高。例如：ArrayList。

而没有实现该接口的话，使用 Iterator 来迭代，这样性能更高，例如：linkedList。

所以这个标记性只是为了让我们知道我们用什么样的方式去获取数据性能更好。

2、属性

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// ======================常量======================
// 版本号
private static final long serialVersionUID = 8683452581122892189L;
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 所有指定初始化为0的数组均会指向这个空数组，注意是static
private static final Object[] EMPTY_ELEMENTDATA = {};
// 所有不指定大小的初始化数组均会指向这个空数组，注意是static
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 最大数组大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
// ======================成员变量======================
// 实际存储数据的数据
transient Object[] elementData; 
// 实际存储元素的大小
private int size; 
}

3、构造方法

ArrayList 有三个构造方法

3.1、无参构造方法-ArrayList()

public ArrayList() {
    // 将默认空数组对象赋值给 elementData，还未赋予默认容量 10
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

3.2、有参构造方法-ArrayList(int initialCapacity)

// 创建指定初始容量的集合
public ArrayList(int initialCapacity) {
    // 指定值大于0，直接创建，若直接指定Integer.MAX_VALUE，则会内存溢出
    if (initialCapacity > 0) {
        // 创建一个指定容量的数组，赋值给 elementData
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) { // 指定初始容量为0
        this.elementData = EMPTY_ELEMENTDATA;
    } else { // 指定值小于0，抛出非法容量异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

3.3、有参构造方法-ArrayList(Collection<? extends E> c)

// 根据实现了Collecion接口或者子接口创建集合
public ArrayList(Collection<? extends E> c) {
    // 转换为数组，并让a指向该数组
    Object[] a = c.toArray();
    if ((size = a.length) != 0) { // 数组大小不为0
        if (c.getClass() == ArrayList.class) { // 是否都为ArrayList类型
            elementData = a; // 都为ArrayList，elementData直接指向a
        } else {
            // 类型不同，转换为Object[]，之后进行数组拷贝（浅拷贝）
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {// 数组大小为0，指向空数组对象
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

Arrays.copyOf 源码

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    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;
}

System.arraycopy 源码

/**
*	
 */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

4、方法

4.1、添加方法-add

方法名	作用
public boolean add(E e)	将元素追加到列表末尾
public void add(int index, E element)	将元素插入到列表的指定位置
public boolean addAll(Collection<? extends E> c)	将集合中的所有元素追加到列表末尾
public boolean addAll(int index, Collection<? extends E> c)	将集合中的所有元素插入到列表中，从指定位置开始插入

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

// 添加单个元素
public boolean add(E e) {
    // 确保内部容量够用 size + 1 已有的个数+新添加的一个
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将元素添加到末尾，然后再size++
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 如果为空，指定指定默认容量，否则容量为 size+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 当前数组为默认空数组，也就是当前数组没有指定初始容量且是第一次添加值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 第一次添加值size+1=1，设置为默认容量10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 不是第一次添加值，返回容量为 size+1
    return minCapacity;
}

// 判断 elementData 数组长度是否够用
private void ensureExplicitCapacity(int minCapacity) {
    // 修改次数+1
    modCount++;
	// 最小容量 小于 当前数组的长度 -> 当前数组容量不够用
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        // 进行扩容
        grow(minCapacity);
}

// 扩容方法
private void grow(int minCapacity) {
    // overflow-conscious code
    // 扩容前的数组长度赋值给 oldCapacity
    int oldCapacity = elementData.length;
    // 新的数组长度为原来的1.5倍赋值给 newCapacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 1、适用于显式指定集合大小为0，oldCapacity = 0，newCapacity = 0
    // minCapacity = 0 + 1，newCapacity < minCapacity
    // 2、要添加的集合大小要大于当前集合长度的0.5倍
    if (newCapacity - minCapacity < 0)
        // 最小可以容量 = （原容量 + 1）/ (原集合容量+要添加集合容量) 
        newCapacity = minCapacity;
    // 集合长度的1.5倍超过允许的最大数组长度
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        // 获取超大数组长度
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 最小容量通常接近数组实际长度
    // 使用数组工具类进行浅拷贝，根据源数组创建一个指定长度的数组，把值复制过去
    // 将新数组的地址赋值给 elementData
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    // 容量为负，抛出内存错误
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果大于最大数组长度，则返回int的最大值，否则返回允许的最大数组长度
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

插入指定位置的元素：void add(int index, E element)

// 向指定位置中插入元素
public void add(int index, E element) {
    // 检查插入的位置是否合法：[0, size-1] 之间
    rangeCheckForAdd(index);
	// 确保容量是否够用
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 数组复制(浅克隆)，整体向后移一个元素
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 将要插入的元素添加到指定位置，覆盖原来的值
    elementData[index] = element;
    // 数组长度+1
    size++;
}

// 检查要添加元素的位置是否合法
private void rangeCheckForAdd(int index) {
    // 索引值 > 集合大小 或者 索引值 < 0 抛出异常，合法范围：[0,size-1]
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

添加一个集合：boolean addAll(Collection<? extends E> c)

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;
    // 要插入的数组长度不为0，就代表添加成功
    return numNew != 0;
}

添加集合到指定位置：boolean addAll(int index, Collection<? extends E> c)

public boolean addAll(int index, Collection<? extends E> c) {
    // 检查插入的位置是否合法：[0, size-1] 之间
    rangeCheckForAdd(index);
	// 将要插入的集合转换成数组
    Object[] a = c.toArray();
    // 把数组长度赋值给 numNew
    int numNew = a.length;
    // 确保 原数组长度+要插入的数组长度 是否够用
    ensureCapacityInternal(size + numNew);  // Increments modCount
	// numMoved：代表要移动元素的个数 例：[2, 5, 3] index:1 size:3
    // numMoved = size - index
    int numMoved = size - index;
    // 移动元素的个数 ＞ 0
    if (numMoved > 0)
        // 将指定位置处的元素及之后整体向后移
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
	// 将待添加数组中的元素复制到原数组中，从index位置开始
    System.arraycopy(a, 0, elementData, index, numNew);
    // 修改数组长度
    size += numNew;
    // 要插入的数组长度不为0，就代表添加成功
    return numNew != 0;
}

4.2、删除方法-remove

方法名	作用
public E remove(int index)	删除指定索引处的元素
public boolean remove(Object o)	删除指定的元素
public boolean removeAll(Collection<?> c)	从此列表中移除指定集合中包含的所有元素
public void clear()	清空所有的元素

删除指定索引处的元素：E remove(int index)

// 删除指定索引处的元素
public E remove(int index) {
    // 检查索引值是否合法
    rangeCheck(index);
	// 修改次数+1
    modCount++;
    // elementData(index)：获取指定索引处的元素，并进行强制转型
    E oldValue = elementData(index);
	// numMoved：代表要向前移动元素的个数
    int numMoved = size - index - 1;
    // 如果移动元素的个数>0
    if (numMoved > 0)
        // 从index+1开始，移动到index位置，移动numMoved个元素
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将末尾的元素置为 null，方便垃圾回收
    elementData[--size] = null; // clear to let GC do its work
	// 返回被删除的元素
    return oldValue;
}

// 检查索引值是否合法
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 获取指定索引处的元素，并进行强制转型
E elementData(int index) {
    return (E) elementData[index];
}

删除指定的元素：boolean remove(Object o)

public boolean remove(Object o) {
    // 这里可以看出arrayList是可以存放null值的
    if (o == null) { 
        // 遍历数组，查找null值，找到null值的索引，调用fastRemove删除
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                // 根据索引快速删除
                fastRemove(index);
                return true;
            }
    } else {// 同理，不为null，遍历数组，判断值是否相等
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    // 数组中没有该元素，返回false
    return false;
}

// 快速删除指定索引处的元素，以下同 remove(int index) 基本一致
// index ∈ [0, size-1]，不需校验
private void fastRemove(int index) {
    // 修改次数+1
    modCount++;
    // numMoved：代表要向前移动元素的个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 数组元素从index+1开始，以后的元素整体前移一位，移动元素的个数为：numMoved
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 集合长度-1，把最后的元素设置为null
    elementData[--size] = null; // clear to let GC do its work
}

boolean removeAll(Collection<?> c)：从此列表中移除指定集合中包含的所有元素

// removeAll：移除两个集合交集的部分，保留原集合剩下的部分：A -（A ∩ B）
public boolean removeAll(Collection<?> c) {
    // 检查该对象是否为null
    Objects.requireNonNull(c);
    // 批量删除
    return batchRemove(c, false);
}

// retainAll：保留两个集合中的交集部分（A ∩ B）
public boolean retainAll(Collection<?> c) {
    // 检查该对象是否为null
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

// =================Objects类中的静态方法  ↓ =================
public static <T> T requireNonNull(T obj) {
    if (obj == null)
        throw new NullPointerException();
    return obj;
}
// =================Objects类中的静态方法 ↑ =================

// batchRemove()方法的两个用途：
// 1、当 complement 为 false 时：A -（A ∩ B）
// 2、当 complement 为 true 时：（A ∩ B）
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0; // r 用来控制循环次数，w 用来记录两个集合交集的个数
    // modified 用来记录是否修改过
    boolean modified = false;
    try {
        // 遍历源集合
        for (; r < size; r++)
            // 如果 complement = false，找出 c 集合有，但源集合没有的元素
            if (c.contains(elementData[r]) == complement)
                // 将c集合中没有的元素，源集合中有的，从头开始填充元素
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // 如果c.contains()抛出异常，把剩下的数据复制到源数组
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        // 排除交集的部分，源集合中还有元素，将剩下的元素置为null
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            // 修改的次数为 集合大小减去交集个数
            modCount += size - w;
            // 交集的个数赋值给 size
            size = w;
            // modified 置为 ture，表示已修改过
            modified = true;
        }
    }
    return modified;
}

清空集合中的所有元素：void clear()

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

4.3、修改方法-set

方法名	作用
public E set(int index, E e)	修改指定索引处的元素
public void trimToSize()	修剪到集合实际大小

修改指定索引处的元素： E set(int index, E e)

public E set(int index, E element) {
    // 检查索引是否合法
    rangeCheck(index);
	// 获取旧的值
    E oldValue = elementData(index);
    // 赋新值
    elementData[index] = element;
    // 返回旧的值
    return oldValue;
}

修剪到集合实际大小：void trimToSize()

public void trimToSize() {
    modCount++;
    // 集合中元素的个数 < 存放元素数组的大小
    if (size < elementData.length) {
        // 如果 size == 0，elementData 指向空数组
        // 否则 使用数组工具类复制 size 大小的数组 赋值给 elementData
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

4.4、查找方法-get

方法名	作用
public E get(int index)	获取指定索引处的元素
public int indexOf(Object o)	从头开始查找指定元素的索引
public int lastIndexOf(Object o)	从尾开始查找指定元素的索引
public boolean contains(Object o)	判断集合中是否包含该元素
public int size()	获取集合实际存放元素的个数
public boolean isEmpty()	判断集合中是否有元素

获取指定索引处的元素：E get(int index)

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

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

E elementData(int index) {
    return (E) elementData[index];
}

从头开始查找指定元素的索引：int indexOf(Object o)

public int indexOf(Object o) {
    // 如果元素是 null,也进行遍历操作
	// 因为集合中有可能够会存储 null
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else { // 查找的元素不为 null
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    // 如果没有走if,也没有走else,那么就说明o该元素在集合中不存在
    return -1;
}

从尾开始查找指定元素的索引：int lastIndexOf(Object o)

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    // 如果没有走if,也没有走else,那么就说明o该元素在集合中不存在
    return -1;
}

结论：底层也是通过循环遍历集合，取出一个个的元素和要找的元素进行比较

判断集合中是否包含该元素：boolean contains(Object o)

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

获取集合实际存放元素的个数：int size()

public int size() {
    return size;
}

判断集合中是否有元素：boolean isEmpty()

public boolean isEmpty() {
    return size == 0;
}

4.5、转换方法

方法名	作用
public String toString()	把集合所有数据转换成字符串
public Object[] toArray()	返回包含此列表中所有元素的数组
public <T> T[] toArray(T[] a)	返回包含此列表中所有元素的数组，并指定返回数组的运行时类型

ArrayList 的爷爷类 AbstractCollection 中的 toString() 方法

public String toString() {
    Iterator<E> it = iterator();
    if (! it.hasNext())
        return "[]";

    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = it.next();
        /*此处比较 e == this 是因为集合中加入自己的话会无限循环导致栈溢出，如果发现集合中的元素是自己就输出一个字符串即可。this指当前对象，也就是list，判断取出的元素是否为当前对象，避免无限循环*/
        sb.append(e == this ? "(this Collection)" : e);
        if (! it.hasNext())
            return sb.append(']').toString();
        sb.append(',').append(' ');
    }
}

返回包含此列表中所有元素的数组：Object[] toArray()

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
// Arrays.copyOf()方法
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

返回包含此列表中所有元素的数组： T[] toArray(T[] a)

返回数组的运行时类型是指定数组的运行时类型。

如果指定的数组能容纳列表，则将该列表返回此处。

否则，将分配一个具有指定数组的运行时类型和此列表大小的新数组。

public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

5、迭代器

// 返回一个在此列表上的顺序迭代器
public Iterator<E> iterator() {
    return new Itr();
}

// ArrayList 的内部类 Itr
private class Itr implements Iterator<E> {
    // 要返回的下一个元素的索引 初始值为0
    int cursor;       // index of next element to return
    // 返回的最后一个元素的索引； -1 如果没有
    int lastRet = -1; // index of last element returned; -1 if no such
    // 将实际修改集合次数 赋值 给预期修改次数
	// 在迭代的过程中,只要实际修改次数和预期修改次数不一致就会产生并发修改异常
	// 由于 expectedModCount 是 Itr 的成员变量,那么只会被赋值一次!!!
    int expectedModCount = modCount;

    Itr() {}

    // 下一个元素的索引 != 集合实际大小 就还有元素
    public boolean hasNext() {
        return cursor != size;
    }
    
	// 获取元素的方法
    @SuppressWarnings("unchecked")
    public E next() {
        // 每次获取元素,会先调用该方法校验 预期修改次数是否 == 实际修改次数
        checkForComodification();
        // 把下一个元素的索引赋值给 i
        int i = cursor;
        // i>= size ：代表没有元素了
        if (i >= size)
            throw new NoSuchElementException();
        // 让局部变量elementData数组指向将外部类的elementData数组
        Object[] elementData = ArrayList.this.elementData;
        // 如果下一个元素的索引大于数组的长度，抛出并发修改异常
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // 下一个元素的索引自增+1
        cursor = i + 1;
        // 返回下一个元素的索引，并进行强制向下转型
        return (E) elementData[lastRet = i];
    }

    // 移除元素的方法
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        // 调用该方法，校验 预期修改次数是否 == 实际修改次数
        checkForComodification();
        try {
            // 调用外部类的remove方法，移除lastRet = i处的元素
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            // 把实际修改的次数再次赋值给预期修改的次数
            // 那么这个时候不管集合自身是否删除成功
		    // 那么实际修改次数和预期修改次数又一致了,所以并不会产生并发修改异常
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        // 预期修改次数是否 == 实际修改次数，不等于抛出并发修改异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

结论:

1、迭代器的 remove 方法底层调用的还是集合自身的 remove 方法删除元素

2、之所以不会产生并发修改异常，其原因是因为在迭代器的 remove 方法中会再次将 集合实际修改次数赋值给预期修改次数

总结

1）arrayList可以存放null。

2）arrayList本质上就是一个elementData数组。

3）arrayList区别于数组的地方在于能够自动扩展大小，其中关键的方法就是gorw()方法。

4）arrayList中removeAll(collection c)和clear()的区别就是removeAll可以删除批量指定的元素，而clear是全是删除集合中的元素。

5）arrayList由于本质是数组，所以它在数据的查询方面会很快，而在插入删除这些方面，性能下降很多，有移动很多数据才能达到应有的效果

6）arrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环。

6、面试题

6.1、ArrayList 和 LinkedList区别 ？

ArrayList 与 LinkedList 都是 List 接口的实现类，都是线程不安全。

ArrayList和LinkedList的区别如下：

• ArrayList的实现是基于数组，LinkedList的实现是基于双向链表。
• 对于随机访问（get、set），ArrayList 优于 LinkedList，ArrayList 是基于数组实现，可以根据下标以 O(1) 时间复杂度对元素进行随机访问。而 LinkedList 是基于双向链表实现，查找某个元素需要遍历，时间复杂度是 O(n)
• 对于插入（add）和删除（remove）操作，LinkedList 优于 ArrayList，因为当元素被添加到LinkedList 任意位置的时候，不需要像 ArrayList 那样扩容和移动元素。
• LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
• LinkedList 不仅实现了 list 接口，还实现了 Deque 接口，是基于链表的栈或者队列，与之对应的是 ArrayDeque 基于数组的栈或者队列

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

根据索引删除元素

测试案例：

如果新添加的元素未超出数组大小限制且往尾部插入，那效率肯定比LinkedList快，但是如果超出了数组大小限制那么就会触发扩容机制并执行数组拷贝，那么效率就很低

public static void main(String[] args) {
    //创建ArrayList集合对象
    ArrayList<String> arrayList = new ArrayList<String>();
    //添加500W个元素
    for (int i = 0; i < 500_0000; i++) {
        arrayList.add(i + "号元素");
    }

    //获取开始时间
    long startTime = System.currentTimeMillis();
    //根据索引删除ArrayList集合元素
    //删除索引50000对应的元素
    String value = arrayList.remove(116_0000);
    //获取结束时间
    long endTime = System.currentTimeMillis();

    System.out.println(value);
    System.out.println("ArrayList集合删除元素的时间: " + (endTime - startTime));

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

测试结果：

1160000号元素
ArrayList集合删除元素的时间: 5
1160000号元素
LinkedList集合删除元素的时间: 35

结论：

1、数组删除元素确实要比链表慢，慢在需要创建新数组，还有比较麻烦的数据拷贝，但是在ArrayList 底层不是每次删除元素都需要扩容，因此在这个方面相对于链表来说数组的性能更好

2、LinkedList 删除元素之所以效率并不高，其原理在于底层先需要对整个集合进行折半的动作，然后又需要对集合进行遍历一次，这些操作导致效率变低

6.3、ArrayList是线程安全的么？

ArrayList 不是线程安全的。

解决办法：

1、对需要同步的方法进行加锁（也叫同步代码块）

synchronized (this){}

2、更换线程安全的集合 Vector

3、使用集合工具类 Collections 把 List 集合变成一个线程安全的集合

Collections.synchronizedList(list);

注：局部变量不需要加锁，成员变量或者用于共享的变量才需要加锁！

每条线程中的局部变量都属于各自的线程，别的线程无法访问，不需要加锁。

而成员变量有可能会被共享，需要加锁。

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

使用读写分离集合（CopyOnWriteArrayList）保证在读的同时正常写入数据，读和写混合操作才建议使用。

• 测试

import java.util.concurrent.CopyOnWriteArrayList;

//线程任务类
class CollectionThread implements Runnable {
	private static ArrayList<String> list = new ArrayList<String>();
    // 使用读写分离集合保证在读的同时正常写入数据
	// private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
	static {
		list.add("Jack");
		list.add("Lucy");
		list.add("Jimmy");
	}

	@Override
	public void run() {
		for (String value : list) {
			System.out.println(value);
			//在读取数据的同时又向集合写入数据
			list.add("coco");
		}
	}
}

//测试类
public class ReadAndWriteTest {
	public static void main(String[] args) {
		//创建线程任务
		CollectionThread ct = new CollectionThread();
		//开启10条线程
		for (int i = 0; i < 10; i++) {
			new Thread(ct).start();
		}
	}
}

6.5、如何复制某个ArrayList到另一个ArrayList中去？

• 使用 clone() 方法
• 使用 ArrayList 构造方法
• 使用 addAll 方法

ArrayList<String> list = new ArrayList<>();
list.add("hello");
list.add("java");
list.add("go");
// 使用ArrayList的构造器
ArrayList<String> anotherList = new ArrayList<>(list);
System.out.println(anotherList);

// 使用ArrayList的clone方法（List接口中没有实现Object的clone方法）
ArrayList<String> cloneList = (ArrayList<String>) list.clone();
System.out.println(cloneList);

// 使用ArrayList的addAll方法
ArrayList<String> list2 = new ArrayList<>();
list2.addAll(list);
System.out.println(list2);

标签：index,int,ArrayList,elementData,笔记,学习,public,size
From： https://www.cnblogs.com/sunzhongjie/p/17153371.html