什么是动态数组？
大家都清楚，java中的数组在创建的时候是需要传入固定大小值的，如果我们添加的数据过多就会角标越界。
动态数组内部是通过java自带的数组来实现的。当添加数据时发现数据个数已经超过了当前数组的最大长度，创建当前数组两倍大小的数组再存储。当数据个数小于总长度的1/4时，为了节省空间，缩小为原来长度的1/2，用户调用无感知就好像我们这个数组可以无限存储数据一样。
1.创建动态数组类
public class Array<E> {
private E[] data;//真正记录数据的数组
private int size;//记录当前一共有多少数据
public Array(int capacity) {
data = (E[]) new Object[capacity];
}
public Array() {
this(10);
}
/**
* 获取当前数组大小
* @return
*/
public int getSize() {
return size;
}
/**
* 判断当前数组是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 获取数组容量
* @return
*/
public int getCapacity(){
return data.length;
}
@Override
public String toString() {
StringBuilder stringBuffer =new StringBuilder();
stringBuffer.append(String.format("capacity: %d ,size: %d [",getCapacity(),getSize()));
for (int i = 0; i < size; i++) {
if(i!=size-1){
stringBuffer.append(data[i]+",");
}else{
stringBuffer.append(data[i]+"]");
}
}
return stringBuffer.toString();
}
}
以上代码创建个动态数组，然后内部是通过java数组来实现的存储，默认创建大小是10，也可以自定义传初始大小。然后是添加了一些简单的方法。
new Object[]的时候一定不能导包，因为org.omg.CORBA.Object 下也有个Object类,如果你是提示输入的话最好看清楚包。
2.增加添加数据的方法
/**
* 指定index位置添加数据，其实就是把index位置以后的数据向后平移一个下标。然后再把E添加到index位置
*
* @param index
* @param e
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("角标越界");
}
//如果当前数组已经没有空间去存储更多的数据，需要扩容
if (size == getCapacity()) {
resize(getCapacity() * 2);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
/**
* 重新设置数组大小
* @param newCapacity
*/
public void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* 数组首添加元素
* @param e
*/
public void addFirst(E e){
add(0,e);
}
/**
* 数组尾添加元素
* @param e
*/
public void addLast(E e){
add(size,e);
}
3.增加删除元素的方法，删除指定位置的元素，其实就是把指定位置以后的所有内容都向前移动一个角标。
/**
* 删除制定位置元素，其实就是index位置以后的元素都向前移动一个下标
*
* @param index
* @return
*/
public E delete(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("角标越界");
}
for (int i = index; i < size; i++) {
data[i] = data[i + 1];
}
//释放内存
data[size] =null;
size--;
//这里也许您会有疑问，为什么不是小于1/2的时候去设置呢？
// 如果说在边界条件下正好我们的数据为原来数据的1/2,然后我们缩容数组大小，
// 下次我们再次增加的时候发现数组容量又不足，我们又需要扩容，频繁这样操作就会，
// 多次执行创建新数组的操作。所以在内容小于1/4时我们再去缩容是比较理性的。
if (size < getCapacity() / 4 && getCapacity() / 2 != 0) {
resize(getCapacity() / 2);
}
return data[index];
}
/**
* 删除首元素
* @return
*/
public E deleteFirst(){
return delete(0);
}
/**
* 删除尾元素
* @return
*/
public E deleteLast(){
return delete(size-1);
}
4.更新指定位置元素
public void update(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("角标越界");
}
data[index] = e;
}
5.查找指定位置元素
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("角标越界");
}
return data[index];
}
public E getFirst(){
return get(0);
}
public E getLast(){
return get(size-1);
}
6.是否包含某个元素
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
7.查找元素的位置
public int findIndex(E e){
for (int i = 0; i < size; i++) {
if(e.equals(data[i])){
return i;
}
}
return -1;
}
8.删除指定元素
public void deleteElement(E e){
int index = findIndex(e);
if(index!=-1){
delete(index);
}
}
所有代码
public class Array<E> {
private E[] data;//真正记录数据的数组
private int size;//记录当前一共有多少数据
public Array(int capacity) {
data = (E[]) new Object[capacity];
}
public Array() {
this(10);
}
public Array(E[] arr){
data = (E[])new Object[arr.length];
for(int i =0; i<arr.length;i++){
data[i] = arr[i];
}
size = arr.length;
}
/**
* 获取当前数组大小
*
* @return
*/
public int getSize() {
return size;
}
/**
* 判断当前数组是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 获取数组容量
*
* @return
*/
public int getCapacity() {
return data.length;
}
/**
* 指定index位置添加数据，其实就是把index位置以后的数据向后平移一个下标。然后再把E添加到index位置
*
* @param index
* @param e
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("角标越界");
}
//如果当前数组已经没有空间去存储更多的数据，需要扩容
if (size == getCapacity()) {
resize(getCapacity() * 2);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
/**
* 重新设置数组大小
*
* @param newCapacity
*/
public void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* 数组首添加元素
*
* @param e
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 数组尾添加元素
*
* @param e
*/
public void addLast(E e) {
add(size, e);
}
/**
* 删除制定位置元素，其实就是index位置以后的元素都向前移动一个下标
*
* @param index
* @return
*/
public E delete(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("角标越界");
}
for (int i = index; i < size; i++) {
data[i] = data[i + 1];
}
//释放内存
data[size] = null;
size--;
//这里也许您会有疑问，为什么不是小于1/2的时候去设置呢？
// 如果说在边界条件下正好我们的数据为原来数据的1/2,然后我们缩容数组大小，
// 下次我们再次增加的时候发现数组容量又不足，我们又需要扩容，频繁这样操作就会，
// 多次执行创建新数组的操作。所以在内容小于1/4时我们再去缩容是比较理性的。
if (size < getCapacity() / 4 && getCapacity() / 2 != 0) {
resize(getCapacity() / 2);
}
return data[index];
}
/**
* 删除首元素
*
* @return
*/
public E deleteFirst() {
return delete(0);
}
/**
* 删除尾元素
*
* @return
*/
public E deleteLast() {
return delete(size - 1);
}
/**
* 更新指定位置元素
*
* @param index
* @param e
*/
public void update(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("角标越界");
}
data[index] = e;
}
/**
* 查找指定位置元素
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("角标越界");
}
return data[index];
}
public E getFirst(){
return get(0);
}
public E getLast(){
return get(size-1);
}
public int findIndex(E e){
for (int i = 0; i < size; i++) {
if(e.equals(data[i])){
return i;
}
}
return -1;
}
/**
* 是否包含某个元素
* @param e
* @return
*/
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
/**
* 删除指定元素
* @param e
*/
public void deleteElement(E e){
int index = findIndex(e);
if(index!=-1){
delete(index);
}
}
public void swap(int i,int j){
if(i<0 || i>=size ||j<0 ||j>=size){
throw new IllegalArgumentException("index error");
}
E temp = data[i];
data[i] = data[j];
data[j] = temp;
}
@Override
public String toString() {
StringBuilder stringBuffer = new StringBuilder();
stringBuffer.append(String.format("capacity: %d ,size: %d [", getCapacity(), getSize()));
for (int i = 0; i < size; i++) {
if (i != size - 1) {
stringBuffer.append(data[i] + ",");
} else {
stringBuffer.append(data[i] + "]");
}
}
return stringBuffer.toString();
}
}
| 方法 | 时间复杂度 |
|---|---|
| addLast() | O(1) |
| addFirst() | O(n) |
| removeFist() | O(n) |
| removeLast() | O(1) |
| update(index) | O(1) |
| contains() | O(n) |
扩容操作
在添加和删除元素时，会出现一种情况：扩容。根据实现的代码可以看出resize方法的时间复杂度在最坏的情况下为O(n)。但是它并不是每次添加或删除元素就会进行扩容，那么它出现的概率是多少呢？
在代码中，我们数组默认的长度为10，也就是在经过11次addLast操作后会触发resize，总共了进行了21次基本操作。也就是说，每一次addLast操作，约等于2次基本操作（21 / 11 ≈ 2）。以此可以推出：假设长度为n，n+1次addLast会触发resize，进行基本操作的次数为2，这样均摊计算的话，resize的时间复杂度为O(1)。很显然，均摊计算（amortized time complexity）比计算最坏情况有意义。
复杂度震荡
当我们调用addLast后，需要resize，此时，addLast的时间复杂度为O(n)，紧接着，我们又调用removeLast，又会触发resize，removeLast的时间复杂度为O(n);不停地这样操作就造成了复杂度的震荡。也就是removeLast时，resize被触发的过于着急。解决这个问题的关键点就在于什么时候缩容。我们可以在当前元素个数为数组长度的1/4时才去缩容，这样能保证缩完容后再马上去调用addLast也不会马上resize。
网友评论