A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© zby_allan 中级黑马   /  2015-8-12 21:37  /  895 人查看  /  5 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

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

  2. import java.util.ArrayList;
  3. import java.util.Date;
  4. import java.util.List;

  5. /**
  6. * 自己实现的ArrayList(深入理解ArrayList底层结构)
  7. * Created by za on 2015/7/15.
  8. */
  9. public class MyArrayList {
  10.     //ArrayList底层是一个Object类型的数组
  11.     private Object[] elementData;
  12.     //ArrayList的尺寸
  13.     private int size;
  14.     //提供一个查询size的方法
  15.     public int size() {
  16.         return  size;
  17.     }
  18.     //默认无参构造器,默认初始容量为10
  19.     public MyArrayList() {
  20.         this(10);
  21.     }
  22.     //带参构造器,参数为初始容量
  23.     public MyArrayList(int initialCapacity) {
  24.         //如果初始容量小于0,则抛出异常
  25.         if (initialCapacity < 0) {
  26.             try {
  27.                 throw new Exception();
  28.             } catch (Exception e) {
  29.                 e.printStackTrace();
  30.             }
  31.         }
  32.         //如果不小于0,则构建一个Object[]数组,长度为初始容量
  33.         elementData = new Object[initialCapacity];
  34.     }
  35.     //add方法之一:在数组最后加入元素
  36.     public void add(Object obj) {
  37.         //容量检查:如果加入元素数量超出数组容量,将数组扩容
  38.         //将扩容封装一个方法ensureCapacityInternal
  39.         ensureCapacityInternal(size + 1);
  40.         //把传进来的对象放入数组的下一个位置,放完后size自增1
  41.         elementData[size++] = obj;
  42.     }
  43.     //add方法之二:在指定位置加入元素
  44.     public void add(int index, Object obj) {
  45.         //索引越界检查
  46.         rangeCheck(index);
  47.         //容量检查
  48.         ensureCapacityInternal(size + 1);
  49.         //在指定位置插入一个元素,要先将该位置往后到最后的所有元素后移一位
  50.         //一共要移多少个元素
  51.         int numMoved = size - index;
  52.         System.arraycopy(elementData, index, elementData, index + 1, numMoved);
  53.         //把要添加的元素写入index位置
  54.         elementData[index] = obj;
  55.         //size加1
  56.         size++;
  57.     }

  58.     //isEmpty方法
  59.     public boolean isEmpty() {
  60.         //如果size==0,则为空
  61.         return size == 0;
  62.     }

  63.     //get方法
  64.     public Object get(int index) {
  65.         //根据索引返回相应位置元素
  66.         //判断,如果index小于0或者大于等于size(size是从1开始)
  67.         //将该判断封装为一个边界检查的方法rangeCheck(int index)
  68.         rangeCheck(index);
  69.         return elementData[index];
  70.     }
  71.     //remove方法之一:删除指定位置的对象,并返回该对象
  72.     public Object remove(int index) {
  73.         //删除指定位置的对象
  74.         rangeCheck(index);
  75.         Object oldValue = get(index);
  76.         //移除的原理是,找到下标位置后,把这个位置后的所有元素向前移一位
  77.         //再把最后的一位设为空,把size减1
  78.         //前移操作要利用arraycopy,其中的前移的元素个数需要如下计算
  79.         int numMoved = size - index - 1;
  80.         if (numMoved > 0) {
  81.             //从原数组的第index+1个开始数numMoved个元素,拷贝到第index位置开始
  82.             System.arraycopy(elementData, index + 1, elementData, index, numMoved);
  83.         }
  84.         //size减1,并将最后一个位置设为空
  85.         elementData[--size] = null;
  86.         return oldValue;
  87.     }

  88.     //remove方法之二:删除指定值的对象,如果删除了返回true,如果没有该对象返回false
  89.     public boolean remove(Object obj) {
  90.         //删掉指定的对象,首先判定该值是否为空,如果为空
  91.         if (obj == null) {
  92.             // 遍历数组
  93.             for (int index = 0; index < size; index++)
  94.                 //如果某个位置为空
  95.                 if (elementData[index] == null) {
  96.                     //封装一个方法fastRemove,删除指定位置的对象
  97.                     //并将后面的对象依次前移
  98.                     fastRemove(index);
  99.                     //最后返回true
  100.                     return true;
  101.                 }
  102.         //如果该值不为空
  103.         } else {
  104.             for (int index = 0; index < size; index++)
  105.                 //判定是否和数组里的某个对象值相等
  106.                 if (obj.equals(elementData[index])) {
  107.                     //删除指定位置的对象,并返回true
  108.                     fastRemove(index);
  109.                     return true;
  110.                 }
  111.         }
  112.         //否则,就返回false
  113.         return false;
  114.     }
  115.     //set方法:传入要设置的位置和要设置的对象
  116.     public Object set(int index, Object obj) {
  117.         //越界检查
  118.         rangeCheck(index);
  119.         //把原值赋给oldValue
  120.         Object oldValue = get(index);
  121.         //把该位置替换为传入的参数obj
  122.         elementData[index] = obj;
  123.         //返回oldValue
  124.         return oldValue;
  125.     }
  126.     //clear方法
  127.     public void clear() {
  128.         //使用foreach遍历ArrayList,移除所有对象

  129.     }

  130.     //数组扩容(查询数组容量是否够用,如果不够用就扩容)
  131.     private void ensureCapacityInternal(int arrListCapacity) {
  132.         if (arrListCapacity >= elementData.length) { //如果超出容量
  133.             //数组的扩容其实是建立一个新数组然后将原数组数据进行拷贝
  134.             //建立一个新数组,容量为原数组容量2倍+1
  135.             Object[] newArr = new Object[arrListCapacity * 2 + 1];
  136.             //把原数组的所有元素拷贝至新数组的起始位置
  137.             System.arraycopy(elementData, 0, newArr, 0, elementData.length);
  138.             //把新数组定义为elementData
  139.             elementData = newArr;
  140.         }
  141.     }


  142.     //查询下标是否越界方法
  143.     private void rangeCheck(int index) {
  144.         if (/*index < 0 ||*/ index >= size) {
  145.             try {
  146.                 throw new Exception();
  147.             } catch (Exception e) {
  148.                 e.printStackTrace();
  149.             }
  150.         }
  151.     }

  152.     //快速删除方法:删除数组中指定位置的元素并将后面的元素依次前移
  153.     private void fastRemove(int index) {
  154.         rangeCheck(index);
  155.         int numMoved = size - index - 1;
  156.         System.arraycopy(elementData, index + 1, elementData, index, numMoved);
  157.         elementData[--size] = null;
  158.     }

  159.     //测试
  160.     public static void main(String[] args) {
  161.         MyArrayList list = new MyArrayList();
  162.         list.add("Hello");
  163.         list.add(new Date());
  164.         list.add(new Person());
  165.         list.add("aaa");
  166.         list.add(100);
  167.         list.add(27.123);
  168.         list.add("LongTime".toCharArray());

  169.         //list.add(3, new String("add"));
  170.         list.clear();
  171.         System.out.println(list.size());
  172.         //System.out.println(list.get(3));

  173.         //遍历数组
  174.         for (int i = 0; i < list.size(); i++) {
  175.             System.out.print(list.get(i) + ", ");
  176.         }
  177.     }

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

5 个回复

倒序浏览
慢慢看。。。。。。。。。。。先ping
回复 使用道具 举报
是的,谢谢,add方法也解释了为什么list底层是数组,却可以改变长度
回复 使用道具 举报
写得很棒, 加入收藏
回复 使用道具 举报
赞一下!值得学习!
回复 使用道具 举报
wygsqsj 来自手机 中级黑马 2015-8-13 21:53:55
地板
楼主学的很深刻,赞一个
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马