动态数组1

95 阅读 0 评论 63 点赞

我是靠谱客的博主时尚玉米，这篇文章主要介绍动态数组1，现在分享给大家，希望可以做个参考。

动态数组实现线性表

什么是线性表：

线性表，由零个或多个数据元素组成的有限序列。就像排队一样，只有第一个由唯一的后继，最后一个有唯一的前驱，其他的都有唯一的前驱和后继。

线性表的顺序存储结构

指的是用一段地址连续的存储单元依次存储线性表的数据元素。对线性表进行增删该查。
用顺序存储结构实现List；

成员变量：

复制代码

1
2
3
4
    private static int DEFULT_SIZE=10;
	private E[] data;   //存储数据元素的容器
	private int size;   //线性表的有效元素的个数

构造函数：
1 默认无参的
2 有参的构造函数

复制代码

1
2
3
4
5
6
7
8
9
10
public ArrayList(){
		this.data = (E[]) new Object[DEFULT_SIZE];
		this.size = 0;
	}
	public ArrayList(int capacity){
		this.data = (E[]) new Object[capacity];
		this.size=0;
	}

添加元素：
在指定角标处添加元素e，首先判断是否角标是否越界，然后在判断是否容器已经满了，如果满了，就需要进行扩容（扩容为原来的两倍）。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void add(int index, E e) {
		if(index<0||index>size){
			throw new ArrayIndexOutOfBoundsException("add添加元素异常");
		}
		if(size==data.length){
			resize(2*data.length);
		}
		for(int i=size-1;i>= index;i--){
			data[i+1]=data[i];
		}
		data[index]=e;
		size++;
		
	}

删除元素：
删除也需要先进行对角标越界，进行判定，然后进行删除指定角标处的元素，需要把删除角标处的后一个向前覆盖，再删除后进行，判定是否进行缩容，缩小为原来的一半。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public E remove(int index) {
		// TODO Auto-generated method stub
		if(index<0||index>size-1){
			throw new ArrayIndexOutOfBoundsException("remove角标越界");
		}
		E e = get(index);
		for(int i=index+1;i<=size-1;i++){
			data[i-1] = data[i];
		}
		size--;
		//判断是否缩容
		if(data.length > DEFULT_SIZE&&size <= data.length/4){
			resize(data.length/2);
		}
		return e;
	}