深入了解ArrayList
1.数据结构
可变数组：List接口是可调整大小的数组实现，而数组一旦初始化长度就不可以发生改变。
增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。
查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。
2.继承关系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
3.ArrayList构造方法
ArrayList()
ArrayList<String> list = new ArrayList<String>();
源码分析：
/**
* 空参构造ArrayList()
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 默认初始容量，长度10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 默认容量的空数组，长度为0
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 真正存储数组元素的数组
*/
transient Object[] elementData;
/**
* 集合大小
*/
private int size;
结论：
空参构造方法创建集合对象并没有做初始化大小的操作，仅仅给容器赋予了一个空的object数组，所以当ArrayList list = new ArrayList();的时候，容器的初始大小是0、
ArrayList(Collection<? extends E> c)
构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。
public ArrayList(Collection<? extends E> c) {
//将构造中的集合对象转成数组,且将数组的地址赋值给一个object类型的数组
Object[] a = c.toArray();
//将object类型数组的长度赋值给集合长度size,且判断是否不等于0
if ((size = a.length) != 0) {
//判断构造中的集合对象和ArrayList是否为不一样的类型
if (c.getClass() == ArrayList.class) {
//将构造中的集合对象赋值给elementData
elementData = a;
} else {
//使用Arrays的copyOf方法进行元素的拷贝
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
//用空数组代替
elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList.toArray():将集合转数组的方法
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
Arrays数组工具类：
public class Arrays {
@SuppressWarnings("unchecked")
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")
//三元运算符判断,不管结果如何都创建一个新数组
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//将数组内容拷贝到copy该数组中
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
//返回拷贝元素成功后的数组
return copy;
}
}
例如：
public static void main(String[] args) {
ArrayList<Integer> list1 = new ArrayList<Integer>();
list1.add(1);
list1.add(2);
list1.add(3);
ArrayList<Number> list2 = new ArrayList<>(list1);
for (Number number : list2) {
System.out.println(number);
}
}
ArrayList(int initialCapacity)
/**
* 构造具有指定初始容量的空列表。
*/
ArrayList<String> list = new ArrayList<String>(6);
源码分析：
public ArrayList(int initialCapacity) {
//判断初始容量initialCapacity是否大于0
if (initialCapacity > 0) {
//创建一个数组,且指定长度为initialCapacity
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果initialCapacity容量为0，把EMPTY_ELEMENTDATA的地址赋值给elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {
//都不满足抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
结论：
通过ArrayList 构造方法参数创建指定长度的数组，当ArrayList<String> list = new ArrayList<String>(6)时，将初始化创建长度为6的数组容器。
4.add()
add(E e)
将指定的元素追加到此列表的末尾。
public boolean add(E e) {
//调用方法对内部容量进行校验
ensureCapacityInternal(size + 1); // Increments modCount!!
//当前素组索引size值对应添加元素
elementData[size++] = e;
return true;
}
//多次容量校验
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//返回计算出来的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//判断存数据的数组是否等于空容量的数组，new ArrayList()时，elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA；
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//返回默认容量和最小容量中的最大值，用于第一次扩容
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//返回最小容量
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//实际修改集合次数++
modCount++;
//判断最小容量 - 数组长度是否大于 0
if (minCapacity - elementData.length > 0)
//将计算出来的容量传递给核心扩容方法
grow(minCapacity);
}
private void grow(int minCapacity) {
//记录数组的实际长度,此时elementData没有存储元素,长度为0
int oldCapacity = elementData.length;
//核心扩容算法 原容量的1.5倍
// >> n ：除以2的n次幂指数
// >> 1：右移 ，除以2，即原来数组长度+原来长度一半，也就是1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
//判断新容量 - 最小容量是否小于 0, 如果是第一次调用add方法必然小于
if (newCapacity - minCapacity < 0)
//将最小容量赋值给新容量
newCapacity = minCapacity;
//判断新容量-最大数组大小 是否>0
//private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//计算出一个超大容量
newCapacity = hugeCapacity(minCapacity);
//创建一个新数组,将新数组的地址赋值给elementData
elementData = Arrays.copyOf(elementData, newCapacity);
}
//计算出一个超大容量
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add(int index, E element)
在此列表中的指定位置插入指定的元素。
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("11");
list.add("22");
list.add(1, "33");
//[11, 33, 22]
System.out.println(list);
}
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 rangeCheckForAdd(int index) {
//超出集合最大长度10 || 小于0 抛出异常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//不是第一次new arrayList(),不会执行
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//直接返回最小容量3
return minCapacity;
}
//多次容量校验
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
//增量++
modCount++;
//此时，最小容量3-集合容量10 <0 ，不执行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
addAll(Collection<? extends E> c)
按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("11");
list.add("22");
list.add("33");
ArrayList<String> list1 = new ArrayList<>();
list1.addAll(list);
}
public boolean addAll(Collection<? extends E> c) {
//把集合的元素转存到Object类型的数组中
Object[] a = c.toArray();
//记录数组的长度
int numNew = a.length;
//检验是否要扩容,且让增量++
ensureCapacityInternal(size + numNew);
//将a数组的元素拷贝到elementData数组中
System.arraycopy(a, 0, elementData, size, numNew);
//集合的长度+=a数组的长度
size += numNew;
//a数组的长度不等于0,即添加成功
return numNew != 0;
}
/**
* src - 源数组。
* srcPos - 源数组中的起始位置。
* dest - 目标数组。
* destPos - 目的地数据中的起始位置。
* length - 要复制的数组元素的数量。
*/
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
addAll(int index, Collection<? extends E> c)
将指定集合中的所有元素插入到此列表中，从指定的位置开始。
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("11");
list.add("22");
ArrayList<String> list1 = new ArrayList<>();
list1.add("33");
list1.add("44");
//[33, 11, 22, 44]
list1.addAll(1,list);
}
public boolean addAll(int index, Collection<? extends E> c) {
//索引校验
rangeCheckForAdd(index);
//添加集合转数组
Object[] a = c.toArray();
//记录添加集合长度
int numNew = a.length;
//校验集合是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
//记录将要移动元素的个数 : numMoved=集合真是长度-要存储索引位置
int numMoved = size - index;
//如果移动元素个数大于0，则调用arraycopy（）进行元素移动
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//真正将数据源添加到集合中
System.arraycopy(a, 0, elementData, index, numNew);
//当前集合对象长度+添加集合长度
size += numNew;
//添加集合长度！=0，添加成功
return numNew != 0;
}
/**
* src - 源数组。
* srcPos - 源数组中的起始位置。
* dest - 目标数组。
* destPos - 目的地数据中的起始位置。
* length - 要复制的数组元素的数量。
*/
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
5.set()
set(int index, E element) : 用指定的元素替换此列表中指定位置的元素。
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("11");
list.add("22");
list.add("33");
String value = list.set(2, "44");
}
public E set(int index, E element) {
//索引校验
rangeCheck(index);
//取出index对应的元素,且赋值给oldValue
E oldValue = elementData(index);
//将element直接覆盖index对应的元素
elementData[index] = element;
//返回被覆盖的元素
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
6.get()
get(int index) : 返回此列表中指定位置的元素。
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("11");
list.add("22");
String value = list.get(1);
}
public E get(int index) {
//索引校验
rangeCheck(index);
//根据索引取出集合元素返回
return elementData(index);
}
7.remove()
remove(int index)
remove(int index) : 删除该列表中指定位置的元素。
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("11");
list.add("22");
list.add("33");
list.remove(1);
}
public E remove(int index) {
//索引校验
rangeCheck(index);
//实际修改增量++
modCount++;
//取出将要删除索引对应元素
E oldValue = elementData(index);
//计需要移动元素个数
int numMoved = size - index - 1;
//>0，拷贝
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将源集合最后一个元素置为null
elementData[--size] = null; // clear to let GC do its work
//返回被删除的元素
return oldValue;
}
remove(Object o)
从列表中删除指定元素的第一个出现（如果存在）。
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("11");
list.add("22");
list.add("33");
list.remove("22");
}
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;
//拷贝
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将集合最后一个元素置为null
elementData[--size] = null; // clear to let GC do its work
}
8.iterator()
iterator() : 以正确的顺序返回该列表中的元素的迭代器。
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("11");
list.add("22");
list.add("33");
//获取迭代器
Iterator<String> it = list.iterator();
//遍历集合
while (it.hasNext()) {
String s = it.next();
System.out.println(s);
}
}
ArrayList
public Iterator<E> iterator() {
//创建Itr对象
return new Itr();
}
ArrayList集合内部类Itr
private class Itr implements Iterator<E> {
//要返回的下一个元素的索引,即光标指向
int cursor; // index of next element to return
//返回的最后一个元素的索引;-1如果没有
int lastRet = -1; // index of last element returned; -1 if no such
//集合实际修改次数赋值给预期修改次数，初始化Itr对象时，该值就是集合size
int expectedModCount = modCount;
Itr() {}
//光标指向索引是否不等于集合的size
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
//光标指向赋值给i
int i = cursor;
//大于集合的size就说明没有元素
if (i >= size)
throw new NoSuchElementException();
//集合存储数据数组的地址赋值给该方法的局部变量
Object[] elementData = ArrayList.this.elementData;
//光标指向索引大于集合size，即产生并发修改异常
if (i >= elementData.length)
throw new ConcurrentModificationException();
//光标自增
cursor = i + 1;
//取出元素返回
return (E) elementData[lastRet = i];
}
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();
}
}
@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();
}
}
9.并发修改异常
1.删除集合末尾元素
删除集合末尾元素，将产出java.util.ConcurrentModificationException并发修改异常
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("11");
list.add("22");
list.add("33");
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
if(s.equals("33")) {
list.remove("33");
}
}
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
//删除最后一个元素时，cursor：3，而size因为remove（）为：2，返回true
public boolean hasNext() {
return cursor != size;
}
//删除最后一个元素后，执行next（），调用checkForComodification（），发生异常
public E next() {
checkForComodification();
int i = cursor;
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) {
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
}
原因：
1.集合调用add方法的时候,实际修改次数会自增，同理删除集合元素时实际修改次数也会自增
2.而在获取迭代器的时候,集合只会执行一次将实际修改集合的次数赋值给预期修改集合的次数
2.删除集合倒数第二个位置元素
当要删除的元素在集合的倒数第二个位置的时候,不会产生java.util.ConcurrentModificationException并发修改异常
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("11");
list.add("22");
list.add("33");
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
if(s.equals("22")) {
list.remove("22");
}
}
}
//删除22后，在执行hasNext（），此时cursor：2，sieze因remove（）后为2，直接返回false，不会执行next（）；
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
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];
}
原因:
1.调用hasNext方法的时候,光标的值和集合的长度一样,返回false。
2.不会调用next方法获取集合的元素,既然不会调用next方法那么底层就不会产生并发修改异常
3.迭代器对象删除
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("11");
list.add("22");
list.add("33");
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
if(s.equals("33")) {
it.remove("33");
}
}
}
ArrayList内部类方法
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();
}
}
ArrayList
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;
}
原因：
1.迭代器调用remove方法删除元素,底层真正还是调用集合自己的删除方法来删除元素，实际修改次数自增
2.在迭代器调调用remove方法中会每次都给预期修改次数的变量赋值，从而保证了实际修改次数与预期修改次数一致
10.toString()
返回此集合的字符串表示形式。 字符串表示由集合的元素的列表按照它们的迭代器返回的顺序包含在方括号（ “[]” ）中。 相邻元素由字符”, “
（逗号和空格）分隔。 元素被转换为字符串由String.valueOf(Object) 。
AbstractCollection
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(' ');
}
}
11.clear()
clear() ： 从列表中删除所有元素。
public void clear() {
//实际修改次数自增
modCount++;
//把数组每一个位置都置为null,让GC回收
for (int i = 0; i < size; i++)
elementData[i] = null;
//集合长度置为0
size = 0;
}
12.contains()
contains(Object o) : 如果此列表包含指定的元素，则返回 true 。
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;
}
13.isEmpty()
isEmpty() : 如果此列表不包含元素，则返回 true 。
public boolean isEmpty() {
//根据集合的长度返回对应的结果
return size == 0;
}
14.标记性接口
RandomAccess、Cloneable、Serializable三个是标记性接口
1.RandomAccess
实现该接口的类支持快速随机访问。主要目的是允许通用算法更改其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性能。
随机访问比顺序访问快
测试ArrayList
public static void main(String[] args) {
//创建ArrayList集合 添加10W条数据
List<String> list = new ArrayList<String>();
for (int i = 0; i < 100000; i++) {
list.add(i + "");
}
//测试随机访问时间
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("随机访问用时: " + (endTime - startTime));
//测试顺序访问时间
startTime = System.currentTimeMillis();
Iterator<String> it = list.iterator();
while (it.hasNext()) {
it.next();
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问用时: " + (endTime - startTime));
}
随机访问用时: 4
顺序访问用时: 7
测试LinkedList
public static void main(String[] args) {
//创建LinkedList集合 添加10W条数据
List<String> list = new LinkedList<String>();
for (int i = 0; i < 100000; i++) {
list.add(i + "");
}
//测试随机访问时间
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("随机访问用时: " + (endTime - startTime));
//测试顺序访问时间
startTime = System.currentTimeMillis();
Iterator<String> it = list.iterator();
while (it.hasNext()) {
it.next();
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问用时: " + (endTime - startTime));
}
随机访问用时: 30978
顺序访问用时: 4
为什么LinkedList随机访问比顺序访问慢这么多？
其一：LinkedList没有实现RandomAccess接口
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
其二：LinkedList源码分析
随机访问时：每次LinkedList对象调用get方法获取元素,都会执行以下代码
public E get(int index) {
//检验是否有效
checkElementIndex(index);
return node(index).item;
}
node(index)
Node<E> node(int index) {
//每次被调用都会根据集合size进行折半动作
//判断get方法中的index是小于集合长度的一半还是大于一半
if (index < (size >> 1)) {
//如果小于就从链表的头部往后找
Node<E> x = first;
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;
}
}
顺序访问时：
LinkedList继承AbstractSequentialList
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
AbstractSequentialList继承AbstractList
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
public Iterator<E> iterator() {
return listIterator();
}
}
AbstractList实现了List接口的listIterator
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
public ListIterator<E> listIterator() {
return listIterator(0);
}
}
List
ListIterator<E> listIterator();
LinkedList重写listIterator接口
public ListIterator<E> listIterator(int index) {
//检查索引位置
checkPositionIndex(index);
//返回ListItr对象
return new ListItr(index);
}
ListItr是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;
}
public boolean hasNext() {
//如果nextIndex < 集合的长度,就说明还有元素,可以进行next
return nextIndex < size;
}
public E next() {
//检查集合实际修改次数和预期次数是否一样
checkForComodification();
//再次判断是否有元素
if (!hasNext())
throw new NoSuchElementException();
//将链表的第一个元素赋值给lastReturned
lastReturned = next;
//将下一个元素赋值给next
next = next.next;
//nextIndex++
nextIndex++;
//返回第一个元素
return lastReturned.item;
}
Node<E> node(int index) {
//获取迭代器的时候进行折半动作
//在获取迭代器的时候index 一定是0,if条件成立
if (index < (size >> 1)) {
Node<E> x = first;
//循环条件不成立,不会执行 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;
}
}
}
使用场景
/**
* 判断list是否实现RandomAccess接口
* 是：随机遍历迭代
* 否：使用顺序迭代
*/
if(list instanceof RandomAccess) {
//随机访问
for (int i = 0; i < list.size(); i++) {
Object object = list.get(i);
}
}else{
//顺序访问
for (Object object : list) {
}
}
2.Cloneable
当一个类实现Cloneable接口来指示Object.clone() 方法，该方法对于该类的实例进行字段的复制是合法的。
在不实现 Cloneable 接口的实例上调用对象的克隆方法会导致异常 CloneNotSupportedException 被抛出。
克隆就是依据已经有的数据，创造一份新的完全一样的数据拷贝
Cloneable源码：
public interface Cloneable {
}
克隆的前提条件
被克隆对象所在的类必须实现Cloneable接口
必须重写clone方法
浅克隆
基本数据类型可以完全复制，引用数据类型不可以，当引用对象的值发生改
变时，被克隆对象引用对象的值也将跟随改变
public class Student implements Cloneable{
/**
* 姓名
*/
private String name;
/**
* 年龄
*/
private int age;
/**
* 车辆
*/
private Car car;
public Student() {
}
public Student(String name, int age, Car car) {
this.name = name;
this.age = age;
this.car = car;
}
@Override
public Object clone() throws CloneNotSupportedException {
return (Student) super.clone();
}
}
引用对象Car
public class Car{
private String carName;
public Car(String carName) {
this.carName = carName;
}
public String getCarName() {
return carName;
}
public void setCarName(String carName) {
this.carName = carName;
}
}
public static void main(String[] args) throws CloneNotSupportedException {
Car car = new Car("宝马");
//创建学生对象
Student stu1 = new Student("小白", 22, car);
//调用clone的方法进行数据的拷贝
Object stu2 = stu1.clone();
System.out.println(stu1 == stu2);
System.out.println(stu1);
System.out.println(stu2);
//更改stu1对象的内容
stu1.setAge(33);
car.setCarName("奔驰");
System.out.println(stu1);
System.out.println(stu2);
}
false
Student{name='小白', age=22, car=Car{carName='宝马'}}
Student{name='小白', age=22, car=Car{carName='宝马'}}
Student{name='小白', age=33, car=Car{carName='奔驰'}}
Student{name='小白', age=22, car=Car{carName='奔驰'}}
深克隆
深拷贝,不能简单的调用父类的clone()方法
@Override
public Object clone() throws CloneNotSupportedException {
//return super.clone(); 深拷贝,不能简单的调用父类的方法
//先克隆出来一个学生对象
Student stu = (Student) super.clone();
//调用Car类中的克隆方法,克隆一个car对象
Car car = (Car) this.car.clone();
//将克隆出来的car赋值给stu对象的成员变量
stu.setCar(car);
//需要把stu返回
return stu;
}
引用对应实现Cloneable接口并重新clone()方法
public class Car implements Cloneable{
@Override
protected Object clone() throws CloneNotSupportedException {
return super.clone();
}
}
false
Student{name='小白', age=22, car=Car{carName='宝马'}}
Student{name='小白', age=22, car=Car{carName='宝马'}}
Student{name='小白', age=33, car=Car{carName='奔驰'}}
Student{name='小白', age=22, car=Car{carName='宝马'}}
ArrayList中clone的使用
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("11");
list.add("22");
list.add("33");
//调用克隆方法
ArrayList<String> arrayList = (ArrayList<String>) list.clone();
//false
System.out.println(arrayList == list);
//[11, 22, 33]
System.out.println(arrayList);
//[11, 22, 33]
System.out.println(list);
}
ArrayList中clone()：
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);
}
}
super.clone()：
protected native Object clone() throws CloneNotSupportedException;
Arrays.copyOf(elementData, size)：
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
copyOf(original, newLength, original.getClass())：
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;
}
3.Serializable
类的序列化由实现java.io.Serializable接口的类启用。 不实现此接口的类将不会使任何状态序列化或反序列化。 可序列化类的所有子类型都是可序列化的。 序列化接口没有方法或字段，仅用于标识可串行化的语义。
Serializable源码
public interface Serializable {
}
序列化与反序列化：
序列化:将对象的数据写入到文件(写对象)
反序列化:将文件中对象的数据读取出来(读对象)
测试
public class Student implements Serializable{
/**
* 姓名
*/
private String name;
/**
* 年龄
*/
private Integer age;
public Student() {
}
public Student(String name, Integer age) {
this.name = name;
this.age = age;
}
//getter() setter() toString()
}
public class SerializableTest{
public static void main(String[] args) throws Exception {
//写数据
writeObject();
//读数据
readObject();
}
/**
* 序列化
* 将对象数据写入到文件
*
* @throws IOException
*/
private static void writeObject() throws IOException {
//创建对象操作流
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("Serializable.txt"));
Student student = new Student("小白", 22);
//调用对象操作流写对象的方法,将对象的数据写入到文件
oos.writeObject(student);
//关闭流
oos.close();
}
/**
* 反序列化
* 将文件的数据读取出来
*
* @throws IOException
* @throws ClassNotFoundException
*/
private static void readObject() throws IOException, ClassNotFoundException {
//创建对象操作流
ObjectInputStream ois = new ObjectInputStream(new FileInputStream("Serializable.txt"));
//调用方法读取一个对象
Student student = (Student) ois.readObject();
//关闭流
ois.close();
//输出读取到对象的数据
System.out.println(student);
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/137075.html
