[论坛提问] 自己实现的List容器

从过完年开始考虑报名，一直自学到现在，总算把基础知识差不多学了一遍。当然准确地说是学了好几遍了，Java里最核心的面向对象就搞了很长时间才理解。相信自学的同学都学了容器了，其实平常使用我们只需要了解容器的特性和使用方法就好了，但我还是花了一些时间去看了看容器的源码，一个是可以加深理解，另一个也对形成Java的编程思维有所帮助。下面是我自己实现的一个不带泛型的List容器，底层通过数组实现的。这里就跟大家分享一下。

package JavaCollections;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
/**
* 自己实现的ArrayList（深入理解ArrayList底层结构）
* Created by za on 2015/7/15.
*/
public class MyArrayList {
//ArrayList底层是一个Object类型的数组
private Object[] elementData;
//ArrayList的尺寸
private int size;
//提供一个查询size的方法
public int size() {
return size;
}
//默认无参构造器，默认初始容量为10
public MyArrayList() {
this(10);
}
//带参构造器，参数为初始容量
public MyArrayList(int initialCapacity) {
//如果初始容量小于0，则抛出异常
if (initialCapacity < 0) {
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
//如果不小于0，则构建一个Object[]数组，长度为初始容量
elementData = new Object[initialCapacity];
}
//add方法之一：在数组最后加入元素
public void add(Object obj) {
//容量检查：如果加入元素数量超出数组容量，将数组扩容
//将扩容封装一个方法ensureCapacityInternal
ensureCapacityInternal(size + 1);
//把传进来的对象放入数组的下一个位置，放完后size自增1
elementData[size++] = obj;
}
//add方法之二：在指定位置加入元素
public void add(int index, Object obj) {
//索引越界检查
rangeCheck(index);
//容量检查
ensureCapacityInternal(size + 1);
//在指定位置插入一个元素，要先将该位置往后到最后的所有元素后移一位
//一共要移多少个元素
int numMoved = size - index;
System.arraycopy(elementData, index, elementData, index + 1, numMoved);
//把要添加的元素写入index位置
elementData[index] = obj;
//size加1
size++;
}
//isEmpty方法
public boolean isEmpty() {
//如果size==0，则为空
return size == 0;
}
//get方法
public Object get(int index) {
//根据索引返回相应位置元素
//判断，如果index小于0或者大于等于size（size是从1开始）
//将该判断封装为一个边界检查的方法rangeCheck(int index)
rangeCheck(index);
return elementData[index];
}
//remove方法之一：删除指定位置的对象，并返回该对象
public Object remove(int index) {
//删除指定位置的对象
rangeCheck(index);
Object oldValue = get(index);
//移除的原理是，找到下标位置后，把这个位置后的所有元素向前移一位
//再把最后的一位设为空，把size减1
//前移操作要利用arraycopy，其中的前移的元素个数需要如下计算
int numMoved = size - index - 1;
if (numMoved > 0) {
//从原数组的第index+1个开始数numMoved个元素，拷贝到第index位置开始
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
}
//size减1，并将最后一个位置设为空
elementData[--size] = null;
return oldValue;
}
//remove方法之二：删除指定值的对象，如果删除了返回true，如果没有该对象返回false
public boolean remove(Object obj) {
//删掉指定的对象，首先判定该值是否为空，如果为空
if (obj == null) {
// 遍历数组
for (int index = 0; index < size; index++)
//如果某个位置为空
if (elementData[index] == null) {
//封装一个方法fastRemove，删除指定位置的对象
//并将后面的对象依次前移
fastRemove(index);
//最后返回true
return true;
}
//如果该值不为空
} else {
for (int index = 0; index < size; index++)
//判定是否和数组里的某个对象值相等
if (obj.equals(elementData[index])) {
//删除指定位置的对象，并返回true
fastRemove(index);
return true;
}
}
//否则，就返回false
return false;
}
//set方法：传入要设置的位置和要设置的对象
public Object set(int index, Object obj) {
//越界检查
rangeCheck(index);
//把原值赋给oldValue
Object oldValue = get(index);
//把该位置替换为传入的参数obj
elementData[index] = obj;
//返回oldValue
return oldValue;
}
//clear方法
public void clear() {
//使用foreach遍历ArrayList，移除所有对象
}
//数组扩容（查询数组容量是否够用，如果不够用就扩容）
private void ensureCapacityInternal(int arrListCapacity) {
if (arrListCapacity >= elementData.length) { //如果超出容量
//数组的扩容其实是建立一个新数组然后将原数组数据进行拷贝
//建立一个新数组，容量为原数组容量2倍+1
Object[] newArr = new Object[arrListCapacity * 2 + 1];
//把原数组的所有元素拷贝至新数组的起始位置
System.arraycopy(elementData, 0, newArr, 0, elementData.length);
//把新数组定义为elementData
elementData = newArr;
}
}
//查询下标是否越界方法
private void rangeCheck(int index) {
if (/*index < 0 ||*/ index >= size) {
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
}
//快速删除方法：删除数组中指定位置的元素并将后面的元素依次前移
private void fastRemove(int index) {
rangeCheck(index);
int numMoved = size - index - 1;
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = null;
}
//测试
public static void main(String[] args) {
MyArrayList list = new MyArrayList();
list.add("Hello");
list.add(new Date());
list.add(new Person());
list.add("aaa");
list.add(100);
list.add(27.123);
list.add("LongTime".toCharArray());
//list.add(3, new String("add"));
list.clear();
System.out.println(list.size());
//System.out.println(list.get(3));
//遍历数组
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + ", ");
}
}
}

复制代码

我已经尽可能对每个重要操作都进行了注释，相信已经比较清晰了。这个List实现的功能并不完善，效率也没有优化，而且还不带泛型。所以并没有什么实用价值，仅作为对容器底层的最初步理解。希望各位多提宝贵意见。后续还有LinkedList，Map等等，我也会抽空编辑好发上来。

小燕小男_爱情 · 小燕小男_爱情

慢慢看。。。。。。。。。。。先ping

孟茹 · 孟茹

是的，谢谢，add方法也解释了为什么list底层是数组,却可以改变长度

3174918418

写得很棒, 加入收藏

shuguang · shuguang

赞一下!值得学习!

wygsqsj · wygsqsj

楼主学的很深刻，赞一个

帐号		自动登录	找回密码
密码			加入黑马

[论坛提问] 自己实现的List容器

5 个回复

黑马土豪金