数据结构-线性表:数组
一、概述
线性表是由 N 个元素组成的有序排列,也是最常见的一种数据结构,主要包括:数组 和 链表
二、数组结构
1. 描述
数组是一种存储单元连续,用来存储固定大小元素的线性表。Java 中对应的集合实现如:ArrayList
2. 特征
- 一致性:数组只能保存相同数据类型元素,元素的数据类型可以是任何相同的数据类型。
- 有序性:数组中的元素是有序的,通过下标访问。
- 不可变性:数组一旦初始化,则长度(数组中元素的个数)不可变。
3. 分析
< 此处使用 集合 ArrayList 来讲解数组 >
- 添加元素源码分析
// ArrayList 的add方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity); // 若集合为空,则判度add后的容量是否超过默认容量10
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // modCount主要用来记录集合被修改的次数,详细作用请参考源码介绍
// overflow-conscious code
if (minCapacity - elementData.length > 0) // 判断是否需要扩容
grow(minCapacity);
}
// 扩容动作 minCapacity:至少需要的容量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // 原数组长度
// 进行扩容,扩大为原来的1.5倍,那为什么不直接*1.5呢,因为位操作速度更快
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) // 一次扩容后,检查扩容后的容量是否够用
newCapacity = minCapacity; // 若还是不够用,则容量直接为 上面计算后的最小容量 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 static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
// 因为ArrayList底层数据结构为数组,所以下面申请内存空间时,若没有足够的连续内存空间,将会抛出OOM异常,即使内存足够
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); // 申请内存空间,若没有连续的内存空间,则会抛出OOM
// 将原数组拷贝到新的空间
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
// 申请新的数组
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
添加元素总结:添加元素伴随着创建新数组,再将老的数组拷贝到新的数组中
- 删除元素源码分析
public E remove(int index) { // 假设共有5个元素,现在移除第二个元素,即:index=1、size=5
rangeCheck(index); // 检查索引是否越界
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1; // numMoved=3
if (numMoved > 0) // 拷贝到新数组中
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work 让GC来回收该部分资源
return oldValue;
}
删除元素总结:删除元素伴随着创建新数组,再将老的数组拷贝到新的数组中
三、总结
数组结构基于索引下标进行查找,因此查找操作块,增删会判随着新数组的创建和数组的拷贝,增删较慢。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于