从过完年开始考虑报名,一直自学到现在,总算把基础知识差不多学了一遍。当然准确地说是学了好几遍了,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等等,我也会抽空编辑好发上来。
|
|