数组
2019-04-20 本文已影响0人
觥筹啊觥筹
数组结构
一. 内存 特征 原理
1. 数组的内存空间
int[] arr = new int[5];
- 每个 int 元素占4个 字节 (在不同机器上，如单片机,32/64位操作系统中，int占用大小不同) ，在java中int占用4个字节，
数组内存示意.png
_address:某一具体数组内存空间的地址
base_address:内存块的首地址
data_type_size:数据类型大小；int占用4个字节,double为8个；
arr[i]_address = base_address + i * data_type_size
2. 若数组下标从1开始
arr[i]_address = base_address + (i-1)*data_type_size
- 每次寻址过程中，CPU都要多进行一次减法指针运算
内存结构如图
特征：数组其元素空间大小根据由数组类型决定
原理：
arr[i]_address = base_address + i * data_type_size
二. 时间复杂度
1. 查询/修改
数组根据下标来查询 公式为
arr[i]_address = base_address + i * data_type_size
- base_address ： 由内存提供精确值
- data_type_size : 由数组类型提供精确值
- 所以：arr[i]_address(第i个元素的内存地址)可以确定
其中，未知的元素只有 i 公式中的其他元素都为常数 并且i也是一个精确的数字，即常数，所以查询操作的时间复杂度为：
2. 插入/删除
-
数组的长度为k,要插入元素的位置为n，如果 n>=k，则只进行一次插入操作，最好时间复杂度为
-
如果n<=k，数组需要将n~k内的元素全都往后移一位，其复杂度为
-
因为n<=k，并且出现在每个位置的概率都相同，n插入的位置最多有k种情况，
n=1时，要操作k-1次,n=2时要操作k-2次，要操作的次数总和=k-n
平均时间复杂度为：
三.ArrayList
1.add()
//元素数据，他就是ArrayList底层的数组
private transient Object[] elementData;
public boolean add(E e) {
//size+1 当前数组长度+1
ensureCapacityInternal(size + 1); // Increments modCount!!
//将新元素添加到数组中（该数组可能被扩容了，也可能没有）
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//判定数组是否为空
if (elementData == EMPTY_ELEMENTDATA) {
//和默认长度10比较，返回较大的
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//传入将要添加的元素的下标
ensureExplicitCapacity(minCapacity);
}
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
int oldCapacity = elementData.length;
//新的数组容量 = 旧的数组容量+旧的数组容量的一半
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);
}
2.get()
public E get(int index) {
//检查下表长度
rangeCheck(index);
//获取元素
return elementData(index);
}
private void rangeCheck(int index) {
//若下标不存在，则抛出索引越界异常
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
四. 手写数组封装类
package aritch;
/**
* create by lyuweigh
* date 2019 2019/4/20 21:26
* description <>
*/
import java.util.Arrays;
/**
* 功能分析:
* 1. 插入数据
* 在指定位置插入数据
*
* 2. 删除指定位置的数据
*
* 3. 查询数据
* 查询指定位置的数据
* 打印所有数据
*
* 数组有 长度, 数据, 数组包装类有元素个数
*/
public class ArrayDemo<E> {
//1. 定义一个默认长度 初始化容量
private int initCapacity = 10;
//2. 定义一个数组容器,用于存放数据
private Object element[];
//3.保存元素的个数
private int size;
@Override
public String toString() {
return "Arraydemo{" +
"element=" + Arrays.toString(element) +
'}';
}
public int getSize() {
return size;
}
//默认初始化
public ArrayDemo() {
element = new Object[initCapacity];
}
//创建指定长度的数组
public ArrayDemo(int initCapacity) {
this.initCapacity = initCapacity;
element = new Object[initCapacity];
}
/**
* 插入元素,默认在末尾
* @param data
* @return
*/
public int add(E data) {
//1.检查数组长度够不够
checkElementSize(size+1);
System.out.println("插入");
add(size, data);
return size;
}
/**
* 插入元素到指定的位置中
* @param index
* @param data
* @return
*/
public int add(int index, E data) {
//检查要插入的位置是否在数组的承受范围内
checkIndexBoundary(index);
element[index] = data;
System.out.println("指定插入");
return size++;
}
/**
* 删除元素,返回被删除的元素
* @param index
* @return
*/
public E remove(int index) {
checkIndexBoundary(index);
E old = (E) element[index];
//要移动元素的个数 -1 指令因为数组后面减少了一个
int numMoved = element.length - index - 1;
/**
* 从即将要被删除的元素的后一个位置开始复制
* 复制到被删除的元素的位置上(就是位移操作了),位移所有要移动的元素的个数
*/
System.arraycopy(element, index + 1, element, index, numMoved);
System.out.println("删除元素");
return old;
}
/**
* 获取指定位置的元素
* @param index
* @return
*/
public E get(int index) {
//检查这个index在不在数组中
checkIndexBoundary(index);
System.out.println("获取元素");
return (E) element[index];
}
/**
* 检查要操作的下标是否在当前数组边界中
* @param index
*/
private void checkIndexBoundary(int index) {
if (index > element.length) {
throw new IndexOutOfBoundsException();
}
}
/**
* 检查数组长度够不够,不够就自动扩容一倍
* @param i
*/
private void checkElementSize(int i) {
if (i - element.length > 0) {
moreCoarse();
}
}
/**
* 数组扩容方法
*/
private void moreCoarse() {
int oldCapacity= element.length;
//比较好看的除以2操作 >>
int newCapacity = element.length +(element.length>>1);
Object[] newArray = new Object[newCapacity];
System.arraycopy(element, 0, newArray, 0, element.length);
element = newArray;
System.out.println("扩容");
}
}
