yifanzheng
commented
2 years ago 实现一个动态扩容的数组
/**
* 自定义数组
* <p>
* 1. 支持动态扩容；
* 2. 支持根据数组下标进行随机访问操作；
*
* @author star
*/
public class Array<T> {
/**
* 整型data保存数据
*/
private T[] data;
/**
* 数组容量
*/
private int capacity;
/**
* 数组实际大小
*/
private int size;
public Array(int capacity) {
this.data = (T[]) new Object[capacity];
this.capacity = capacity;
// 初始大小为 0，即没有数据
this.size = 0;
}
public Array() {
// 默认容量 10
this(10);
}
public int size() {
return size;
}
public int capacity() {
return capacity;
}
public T get(int index) {
checkIndex(index);
return data[index];
}
/**
* 在数组末尾添加元素
*
* @param elem 元素
*/
public void add(T elem) {
add(size, elem);
}
/**
* 在指定下标处添加元素
*
* @param index 下标
* @param elem 元素
*/
public void add(int index, T elem) {
checkIndexForAdd(index);
// 如果当前数组大小与容量相同，则进行扩容
if (size == capacity) {
// 扩容为原来的 2 倍
growSize(capacity << 1);
}
int numMoved = size - index;
System.arraycopy(data, index, data, index + 1, numMoved);
data[index] = elem;
size++;
}
/**
* 删除并返回元素
*
* @param index 下标
* @return 返回删除的元素
*/
public T remove(int index) {
checkIndex(index);
T removed = data[index];
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(data, index + 1, data, index, numMoved);
}
data[--size] = null;
return removed;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array size = %d, capacity = %d \n", size, data.length));
builder.append('[');
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append(']');
return builder.toString();
}
private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
private void checkIndexForAdd(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
}
private void growSize(int newCapacity) {
this.capacity = newCapacity;
data = Arrays.copyOf(data, newCapacity);
}
}
数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
线性表（Linear List）：就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。 连续的内存空间和相同类型的数据：使数组具有随机访问能力，但是数组的操作变得低效，比如在数组中删除或插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。
随机访问数组中元素的寻址公式：
练习