java数据结构与算法学习笔记（2）——数组及ArrayList

 

从概念上可知，数组属于线性表（逻辑上一一对应关系），数组在物理内存上采用顺序存储结构。当创建一个数组的时候，就必须确定它的大小，系统会在内存中开辟一块连续的空间，用来保存数组。

优点：可根据索引快速的查找元素。

缺点：大小不可变。（确切应该讲，不能往一个放满元素的数组里再添加新的元素）

 

ArrayList正是保留了数组可以快速查找的优势，同时，又弥补了数组在创建后，要往数组添加元素的弊端。

其实，要往一个已经放满元素的数组里面再添加一个元素，也是可以实现的，即创建一个比原数组容量大一的新数组，将数组中的元素“搬”到新数组，再将新的元素也放入新数组，最后将新数组赋给原数组即可。（这也是用数组的方式实现ArrayList的基本方法）

 

int[] oldArray = {1,2,3,4};
int[] newArray = new int[oldArray.length+1];
for(int t =0;t<oldArray.length;t++){
	newArray[t] = oldArray[t];
}/*这里不能直接用newArray=oldArray; 因为这样newArray的大小会变成 跟oldArray一样了。 */  

System.out.println(newArray.length);
newArray[oldArray.length] = 5;

oldArray = newArray;

通过这样的方法，我们可以简单的实现自己的ArrayList。

 

 

public class MyArrayList {

	private static Object array[] = new Object[0];
	
	//得到队列的大小
	public int getLength(){
		return array.length;
	}
	//根据索引得到元素
	public Object get(int index){
		return array[index];
	}
	
	public void add(Object obj){
		Object o[] = new Object[(array.length+1)];
		
		for(int t=0;t<array.length;t++){
			o[t]=array[t];
		}
		o[array.length] = obj;
		array = o;
	}
	
	public void add(int index, Object obj){
		Object o[] = new Object[(array.length+1)];
		
		for(int t=0;t<index;t++){
			o[t]=array[t];
		}
		o[index] = obj;
		for(int t=index+1;t<o.length;t++){
			o[t]=array[t-1];
		}
		array = o;
	}
	
	/**
	 * 查找队列中是否存在obj元素
	 * @param obj：要查找的元素对象
	 * @return ：返回元素第一次出现的索引位置，若不含该元素则返回-1
	 */
	public int indexOf(Object obj){
		for(int t=0;t<array.length;t++){
			if(array[t].equals(obj)){
				return t;
			}
		}
		return -1;
	}
}

 

 

 

以上便是自己用数组实现的简单的ArrayList。

这样子，我们不但保留了数组可以根据索引快速查找的优势，同时，还可以随时往里面添加元素，不过添加元素的效率应该还是没有链表的效率高的，因为需要创建一个新的数组，还要进行“搬迁”的工作，实在麻烦。

 

 

=============================================

下面请教一下大家怎么称呼ArrayList的？

 

 

一开始学Java的时候，就一直把ArrayList称之为“队列”（也不知道对不对）。

ArrayList，以其称之为队列，倒不如叫做“可增长的数组”好了（个人看法）。

现在反倒觉得不恰当了，因为ArrayList根本也没继承队列Queue接口。而且，list在百度词典上有着“链表，表”的含义，完全没有“队列”这个意思。

同时，根据百度百科的定义：“队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。”ArrayList跟队列实在是风马牛不相干呀。

另外，LinkedList则是同时继承了Queue接口跟List接口。

 

 

PS：这篇文档，我反复的更改字体格式，甚至拷到Word中更改完再复制回来，但始终就是发表后，跟我预览的完全不一样...不知道是不是我电脑有问题，还是人品有问题。如造成您的阅读困扰，请谅解！！！

 

 

评论

4 楼 蛋呢823 2011-04-05  

arne3166 写道

赞一个。
javaeye来了这么久，我喜欢这里的氛围，高手云集，而且不拖泥带水，然而有一点近于苛刻的地方就是对新手不太能容忍。我比较喜欢看别人总结的东西，也喜欢自己总结东西，但很怕被踩，因为自己被否定了，并且踩的人不告诉你为什么，这是对于别人的不尊重。
我在这里赞赏博主的总结和分享精神和学习态度。对于内容的深度，没有得到大牛的肯定，被踩了5次可以看出来，但我挺一下，希望javaeye里面的大牛都高抬贵脚，或者能指出真正不足的地方，才能显示你的实力，否则，走开，这不是你看的东西。

赞楼主的总结和分享精神。。。。

感谢你~  作为小菜，深有同感。

3 楼 arne3166 2011-04-04  

赞一个。
javaeye来了这么久，我喜欢这里的氛围，高手云集，而且不拖泥带水，然而有一点近于苛刻的地方就是对新手不太能容忍。我比较喜欢看别人总结的东西，也喜欢自己总结东西，但很怕被踩，因为自己被否定了，并且踩的人不告诉你为什么，这是对于别人的不尊重。
我在这里赞赏博主的总结和分享精神和学习态度。对于内容的深度，没有得到大牛的肯定，被踩了5次可以看出来，但我挺一下，希望javaeye里面的大牛都高抬贵脚，或者能指出真正不足的地方，才能显示你的实力，否则，走开，这不是你看的东西。

赞楼主的总结和分享精神。。。。

2 楼 蛋呢823 2011-03-15  

裴小星 写道

不过JDK里的ArrayList实现，并非每次增加一个元素，
默认情况下初始大小为10，一旦发现容量不足，
就增加为原来的 (n * 3) /2 + 1 个元素(取整)。
如果仍然达不到要求的大小，则将大小设置为所要求的大小。

if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    elementData = (E[])new Object[newCapacity];
    System.arraycopy(oldData, 0, elementData, 0, size);
}

这样一来，就避免了频繁创建数组。不过 3/2 这个比例，不知道是怎么估算出来的。

收获很多，O(∩_∩)O谢谢

1 楼 裴小星 2011-03-15  

不过JDK里的ArrayList实现，并非每次增加一个元素，
默认情况下初始大小为10，一旦发现容量不足，
就增加为原来的 (n * 3) /2 + 1 个元素(取整)。
如果仍然达不到要求的大小，则将大小设置为所要求的大小。

if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    elementData = (E[])new Object[newCapacity];
    System.arraycopy(oldData, 0, elementData, 0, size);
}

这样一来，就避免了频繁创建数组。不过 3/2 这个比例，不知道是怎么估算出来的。