Java集合 之 动态数组

注意：首先本程序是根据javaeye博主：java_mzd，对里面的代码进行改进，改进的地方如下：

 

1、如何创建动态数组，并且为用户提供了动态扩展数组长度的接口

2、修改在数组指定位置添加元素

3、该数组适应于多线程环境

4、为该类添加删除一个元素的方法

 

 该类的优点：

                  1. 顺序表因为采用顺序存储形式，所以内部使用数组来存储数据
                  2.因为存储的具体对象类型不一定，所以采用泛型操作
                  3.数组操作优点：1.通过指针快速定位到下表，查询快速
 缺点：
                  1、当操作中超过容量时，则需要重新声明数组，并且复制当前所有数据

 

public class ArrayList<E> {
	private Object[] data = null;// 用来保存此队列中内容的数组
	private int current;// 保存当前为第几个元素的指标
	private int capacity;// 表示数组大小的指标
	/***
	 * 扩展数组的长度 ，也就是动态创建数组，默认扩展的长度为10
	 */
	private int extendLength;

	/**
	 * 如果初始化时，未声明大小，则默认为10
	 */
	public ArrayList() {
		this(10);
	}

	/**
	 * 初始化线性表，并且声明保存内容的数组大小
	 * @param initalSize
	 */
	public ArrayList(int initalSize) {
		if (initalSize < 0) {
			throw new RuntimeException("数组大小错误:" + initalSize);
		} else {
			this.data = new Object[initalSize];
			this.current = 0;
			capacity = initalSize;
			extendLength = 10;
		}
	}

	/**
	 * 添加元素的方法 添加前，先确认是否已经满了
	 * @param e
	 * @return
	 */
	synchronized public boolean add(E e) {
		ensureCapacity(current);// 确认容量
		this.data[current] = e;
		current++;
		return true;
	}

	/**
	 * 确认系统当前容量是否满足需要,如果满足，则不执行操作 如果不满足，增加容量
	 * @param cur 当前个数
	 */
	private void ensureCapacity(int cur) {
		if (cur == capacity) {
			// 如果达到容量极限，增加extendLength的容量，复制当前数组
			this.capacity = this.capacity + extendLength;
			Object[] newdata = new Object[capacity];
			System.arraycopy(this.data, 0, newdata, 0, this.capacity
					- extendLength);
			this.data = newdata;
		}
	}

	/**
	 * 得到指定下标的数据
	 * @param index
	 * @return
	 */
	public E get(int index) {
		validateIndex(index);
		return (E) this.data[index];
	}

	/**
	 * 返回当前队列大小
	 * @return
	 */
	public int size() {
		return this.current;
	}

	/**
	 * 更改指定下标元素的数据为e
	 * @param index 
	 * @param e
	 * @return
	 */
	public boolean set(int index, E e) {
		validateIndex(index);
		synchronized(data){
			this.data[index] = e;
		}
		return true;
	}

	/**
	 *  验证当前下标是否合法，如果不合法，抛出运行时异常
	 * @param index 下标
	 */
	private void validateIndex(int index) {
		if (index < 0 || index > current) {
			throw new RuntimeException("数组index错误：" + index);
		}
	}

	/**
	 * 在指定下标位置处插入数据e
	 * @param index 指定数组的位置，从 0 开始
	 * @param e 需要插入的数据
	 * @return 
	 */
	synchronized public boolean insert(int index, E e) {
		validateIndex(index);
		ensureCapacity(current);
		Object[] tem = new Object[current+1];// 用一个临时数组作为备份
		//开始备份数组
//		for (int i = 0; i < current; i++) {
//			if (i < index) {
//				tem[i] = this.data[i];
//			} else if (i == index) {
//				tem[i] = e;
//			} else if (i > index) {
//				tem[i] = this.data[i - 1];
//			}
//		}
		if(index<=0){
			System.arraycopy(data,0,tem,1 , current);
			tem[index]=e;
		}else if(index<=current-1){
			System.arraycopy(data,0,tem,0,index);
			tem[index]=e;
			System.arraycopy(data,index, tem, index+1,current-index);
		}else{
			System.arraycopy(data,0,tem,0,current);
			tem[index]=e;
		}
		current++;
		this.data = tem;
		return true;
	}
	/****
	 * 从数组中删除一个元素
	 * @param e 要删除的元素
	 * @return 如果待删除的元素在数组中没有找到，就返回false,否则返回true
	 */
	public boolean FromArrayDelete(E e) {
		synchronized (data) {
			int n = -1;
			for (int i = 0; i < current; i++) {//在数组中寻找待删除的元素
				if (data[i] == e) {
					n = i;
					break;
				}
			}
			if (n < 0)//如果在数组中没有找到返回false
				return false;
			Object temp[] = new Object[current - 1];
			int j = 0;
			for (int i = 0; i < current; i++) {
				if (i != n)//j++的原因就是，过滤掉删除元素的那个位置
					temp[j++] = data[i];
			}
			current--;
			capacity--;
			data = temp;
			return true;
		}
	}

	public int getExtendLength() {
		return extendLength;
	}

	/***
	 * 可以设置一次性扩展数组的长度
	 * @param extendLength 设置的长度
	 */
	synchronized public void setExtendLength(int extendLength) {
		this.extendLength = extendLength;
	}

	public int getCurrent() {
		return current;
	}

}

 

评论

9 楼 walter_hu 2010-12-12  

原来是思路有些不同 呵呵~

8 楼 walter_hu 2010-12-12  

LZ的数组的扩容时机，我感觉有些不理解...

7 楼 只想做麻雀 2010-12-10  

goolcona 写道

还有一个问题，不知道Object[E]的这个E是否允许重新被指向其他对象：
Object[] data，get方法返回的是 E ，如果E是数组或者集合之类的对象，可以在外部 E e = get() 后， e = anotherE(); 这时因为不是基本数据类型，private Object[index] 指向的e这个对象也被更改了；
如果本身就只是一个存放对象的话那么是没有问题的。

所以说lz讲下这个类的应用场景最好。

恕我愚昧啊，在外部 E e = get() 后， e = anotherE();，怎么会影响到Object[index] 指向的e这个对象！？

如果我改动这个对象当然会影响到，改变e的引用和Object[index]指向的无关啊。

6 楼 he_wen 2010-12-09  

谢谢你，我已经明白了，需要同一个锁保证同步的数据类存可见，我这样用确实危险。。。

5 楼 jbon 2010-12-09  

好好看看同步吧

4 楼 he_wen 2010-12-09  

请问你一下这两个方法没有必然的联系，那么就不能用两个不同的锁吗？还是不明白，能不能举个例子，谢谢。。。

多虑了，肯定是只能存放一种类型了了，谢谢你的想法。。。

3 楼 goolcona 2010-12-09  

锁的持有者是对象，synchronized public void setExtendLength()加锁的对象是类产生的对象，针对这个类就是 ArrayList a = new ArrayList() a这个对象；
synchronized (data) 这个锁的对象是data，两个锁的对象不同；

还有一个问题，不知道Object[E]的这个E是否允许重新被指向其他对象：
Object[] data，get方法返回的是 E ，如果E是数组或者集合之类的对象，可以在外部 E e = get() 后， e = anotherE(); 这时因为不是基本数据类型，private Object[index] 指向的e这个对象也被更改了；
如果本身就只是一个存放对象的话那么是没有问题的。

所以说lz讲下这个类的应用场景最好。

2 楼 he_wen 2010-12-09  

public boolean FromArrayDelete(E e) {  synchronized (data) {，
请问一下问题在哪里，可以让我好好改正谢谢。。。

1 楼 goolcona 2010-12-09  

1)lz写下这个类的应用场景吧，没想出比java.util.ArrayList好在哪里；
2)public boolean FromArrayDelete(E e) {  synchronized (data) {
这个锁是有问题的。