JAVA如何实现线性表顺序存储结构ArrayList

伊谢尔伦

发布时间：2016-11-21 11:14:26

1881人浏览过

来源于php中文网

原创

集合arraylist底层结构使用的是数组，主要实现的方法有增删改查，其中核心的部分是当增加一个元素时候的数组扩容处理。不多说，直接上代码：

/**
 * ArrayList底层使用数组结构，暴露方法，增删改查 其中元素增加，需要判断数组的长度
 */
public class MyArrayList {
private Object[] array;// 存放元素的数组
private Object[] EMPTY_ARRAY = {};// 空数组
private static final int DEFAULT_CAPACITY = 8;// 默认数组长度
private int size;// 数组中元素的个数
private int modSize;// 线性表修改的次数
public MyArrayList() {
array = EMPTY_ARRAY;// 默认是给个空数组还是给个8个空间的数组呢？
}
public MyArrayList(int initCapacity) {
if (initCapacity < 0) {// 传入的数量为负数，抛出异常
throw new IllegalArgumentException("参数错误:" + initCapacity);
} else if (initCapacity == 0) {// 空数组
array = EMPTY_ARRAY;
} else {
array = new Object[initCapacity];
}
}
public MyArrayList(Collection c) {
Object[] obj = c.toArray();
if ((size = obj.length) != 0) {// 将Collection中的数据拷贝出来，防止污染
System.arraycopy(obj, 0, array, 0, size);
} else {
array = EMPTY_ARRAY;
}
}
/**
* 添加一个元素到线性表尾部->先判断数组大小和元素个数是否相同－》相同的话，需要扩容
* 
* @param e
* @return
*/
public boolean add(E e) {
array = judgeIsGrow();
array[size] = e;
size++;
modSize++;
return true;
}
// 判断是否扩容
private Object[] judgeIsGrow() {
if (size == array.length) {
// 确定新数组的大小－－》new出来－－》将原来数组的数据拷贝到新数组中
int newSize = 0;
if (size == 0) {
newSize = DEFAULT_CAPACITY;
} else {
newSize = size < Integer.MAX_VALUE / 2 ? size << 1 : Integer.MAX_VALUE;
}
Object[] newArray = new Object[newSize];
System.arraycopy(array, 0, newArray, 0, size);
array = newArray;
}
return array;
}
/**
* 在第index位置插入一个元素
* 
* @param index
* @param e
* @return
*/
public boolean add(int index, E e) {
checkArgument(index);
array = judgeIsGrow();
Object[] newObj = new Object[array.length];
// 将array数组中的元素拷贝到新数组中
System.arraycopy(array, 0, newObj, 0, index);
System.arraycopy(array, index, newObj, index + 1, size- index);
newObj[index] = e;
array = newObj;
size++;
modSize++;
return true;
}
// 参数检查
private void checkArgument(int index) {
if (index < 0) {
throw new IllegalArgumentException("参数错误:" + index);
} else if (index > size) {
throw new IllegalArgumentException("超过数组长度，参数错误:" + index);
}
}
/**
* 删除第index个元素
* 
* @param index
* @return
*/
@SuppressWarnings("unchecked")
public E remove(int index) {
Object[] newObj = new Object[array.length];
E obj = (E) array[index];
// 将array数组中的元素拷贝到新数组中
System.arraycopy(array, 0, newObj, 0, index);
System.arraycopy(array, index + 1, newObj, index, size - index - 1);
array = newObj;
size--;
modSize++;
return obj;
}
@SuppressWarnings("unchecked")
public E get(int index) {
return (E) array[index];
}
public void set(int index, E e) {
array[index] = e;
}
public int size() {
return size;
}
public static void main(String[] args) {
MyArrayList list = new MyArrayList<>();
for (int i = 0; i < 10; i++) {
list.add("data "+i);
}
list.add(2,"add23");
list.add(11,"dddd");
list.remove(3);
list.set(9, "dajdfljfl");
int size = list.size();
for (int i = 0; i < size; i++) {
System.out.println("元素："+(i+1)+" == " + list.get(i));
}
}
}

最后打印结果为：

元素：1 == data 0

元素：2 == data 1

元素：3 == add23

立即学习“Java免费学习笔记（深入）”；

元素：4 == data 3

元素：5 == data 4