欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java ArrayList 实现实例讲解

程序员文章站 2024-03-12 16:20:44
 arraylist概述:  arraylist是基于数组实现的,是一个动态数组,其容量能自动增长,类似于c语言中的动态申请内存,动态增长内存。...

 arraylist概述: 

arraylist是基于数组实现的,是一个动态数组,其容量能自动增长,类似于c语言中的动态申请内存,动态增长内存。

    arraylist不是线程安全的,只能用在单线程环境下,多线程环境下可以考虑用collections.synchronizedlist(list l)函数返回一个线程安全的arraylist类,也可以使用concurrent并发包下的copyonwritearraylist类。

    arraylist实现了serializable接口,因此它支持序列化,能够通过序列化传输,实现了randomaccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问,实现了cloneable接口,能被克隆。

   每个arraylist实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向arraylist中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造arraylist时指定其容量。在添加大量元素前,应用程序也可以使用ensurecapacity操作来增加arraylist实例的容量,这可以减少递增式再分配的数量。 

   注意,此实现不是同步的。如果多个线程同时访问一个arraylist实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。

下面对java arraylist做一个记录和总结吧

public class arraylist<e> {
  /**
   * 存放集合的元素 
   * 
   */
  private transient object[] elementdata;
  /** 元素的大小 */
  private int size;

定义了一个泛型类,一个object的数组和一个私有变量来记录该集合的元素数量,原文多了一个私有变量,我也不知道干嘛用的,作者也没解释也没提及到,我没使用也没事

/**
   * 根据指定大小初始化
   * @param initialcapacity
   */
  public arraylist(int initialcapacity){
    super();
    if(initialcapacity<=0){
      //抛异常
      throw new illegalargumentexception("初始化参数不能小于0");
    }else{
      //初始化数组
      this.elementdata=new object[initialcapacity];
    }
  }
  /**
   * 默认初始化
   */
  public arraylist(){
    this(10);
  }
  /**
   * 根据一个集合类初始化
   * @param c 一个必须继承了collection接口的类
   */
  public arraylist(collection<? extends e> c){
    //初始化
    elementdata=c.toarray();
    size=elementdata.length;
    //如果不是任意类型的数组就转换objec类型
    if (elementdata.getclass() != object[].class){
      elementdata=arrays.copyof(elementdata,size, object[].class);
    }
  }

3个初始化方法,根据默认大小进行数组的初始化,给定大小初始化和传递一个继承了collection集合接口的类进行转换赋值初始化

/**
   * 扩容集合
   * @param mincapacity
   */
  public void ensurecapacity(int mincapacity){
    /** 当前数组的大小 */
    int oldcapacity = elementdata.length; 
    if (mincapacity > oldcapacity) {
      /**
       * olddata 虽然没有被使用,但是这是关于内存管理的原因和arrays.copyof()方法不是线程安全
       * olddata在if的生命周期内引用elementdata这个变量,所以不会被gc回收掉
       * 当arrays.copyof()方法在把elementdata复制到newcapacity时,就可以防止新的内存或是其他线程分配内存是elementdata内存被侵占修改
       * 当结束是离开if,olddata周期就结束被回收
       */
      object olddata[] = elementdata; 
      int newcapacity = (oldcapacity * 3)/2 + 1; //增加50%+1
        if (newcapacity < mincapacity) 
          newcapacity = mincapacity; 
     //使用arrays.copyof把集合的元素复制并生成一个新的数组
     elementdata = arrays.copyof(elementdata, newcapacity); 
    } 
  }

这是一个核心的方法,集合的扩容,其实是对数组的扩容,mincapacity集合的大小,进行对比判断是否应该进行扩容,使用了arrays.copyof()方法进行扩容,

原文有进行详细的解释,这个方法把第一个参数的内容复制到一个新的数组中,数组的大小是第二个参数,并返回一个新的数组,关于olddata的变量上文有详细的注释

 /**
   * 检查索引是否出界
   * @param index
   */
  private void rangecheck(int index){
    if(index > size || index < 0){
      throw new indexoutofboundsexception("下标超出,index: " + index + ", size: " +size);
    }
  }

一个下标的检索是否出 1 /**

* 添加元素
   * 将指定的元素添加到集合的末尾
   * @param e 添加的元素
   * @return
   */
  public boolean add(e e){
    ensurecapacity(size+1);
    elementdata[size]=e;
    size++;
    return true;
  }

添加元素,先进行扩容,在赋值,然后元素加一,注意 size+1 字段size并没有加一,这里进行的是算术的运算,所以在后面才需要进行自增

/**
   * 添加元素
   * 将元素添加到指定的位置
   * @param index 指定的索引下标
   * @param element 元素
   * @return
   */
  public boolean add(int index, e element){
    rangecheck(index);
    ensurecapacity(size+1);
    // 将 elementdata中从index位置开始、长度为size-index的元素, 
    // 拷贝到从下标为index+1位置开始的新的elementdata数组中。 
    // 即将当前位于该位置的元素以及所有后续元素右移一个位置。
    system.arraycopy(elementdata, index, elementdata, index+1, size-index);
    elementdata[index]=element;
    size++;//元素加一
    return true;
  }

这里不同的是 system.arraycopy(elementdata, index, elementdata, index+1, size-index);

这是一个c的内部方法,详细的原文有解释,这里就不说了,这个也是整个arraylist的核心所在,也arrays.copyof()的内部实现原理

/**
   * 添加全部元素
   * 按照指定collection的迭代器所返回的元素顺序,将该collection中的所有元素添加到此列表的尾部。 
   * @param c
   * @return
   */
  public boolean addall(collection < ? extends e>c){
    object[] newelement=c.toarray();
    int elementlength=newelement.length;
    ensurecapacity(size+elementlength);
    //从newelement 0的下标开始,elementlength个元素,elementdata size的下标 
    system.arraycopy(newelement, 0, elementdata, size, elementlength);
    size+=elementlength;
    return elementlength!=0;
  }

基本上其他方法都只是根据不同的情况进行不同的处理,比如通过接口把数据对象传递进来然后获取长度进行扩容,在把数据使用system,arraycopy复制到新的数组中

/**
   * 指定位置,添加全部元素
   * @param index 插入位置的下标
   * @param c 插入的元素集合
   * @return
   */
  public boolean addall(int index, collection<? extends e> c){
    if(index > size || index < 0){
      throw new indexoutofboundsexception("index: " + index + ", size: " +size);
    }
    object[] newelement=c.toarray();
    int elementlength=newelement.length;
    ensurecapacity(size+elementlength);
    int nummoved=size-index;
    //判断插入的位置是否在数组中间
    if(nummoved>0){
      //把index插入位置的后面的所有元素往后移
      //elementdata index下标开始的nummoved个元素插入到elementdata 的index+elementlength位置
      system.arraycopy(elementdata, index, elementdata, index+elementlength, nummoved);
    }
    //把newelement里从0开始的elementlength个元素添加到elementdata index开始的位置
    system.arraycopy(newelement, 0, elementdata, index, elementlength); 
    size += elementlength; 
    return elementlength != 0;
  }
  
  /**
   * 指定下标赋值
   * @param index
   * @param element
   * @return
   */
  public e set(int index,e element){
    rangecheck(index);
    e oldelement=(e)elementdata[index];
    elementdata[index]=element;
    return oldelement;
  }
  
  /**
   * 根据下标取值
   * @param index
   * @return
   */
  public e get(int index){
    rangecheck(index);
    return (e)elementdata[index];
  }
  
  /**
   * 根据下标移除元素
   * @param index 
   */
  public e remove(int index){
    rangecheck(index);
    e oldelement=(e)elementdata[index];
    /** 移除的下标后面的元素数量 */
    int nummoved=size-index-1;
    //如果在数组范围内就进行移动
    if(nummoved>0)
      system.arraycopy(elementdata, index+1, elementdata, index, nummoved);
    //移除
    elementdata[--size]=null;
    return oldelement;
  }
  
  /**
   * 根据元素移除
   * @param obj
   * @return
   */
  public boolean remove(object obj){
    //arraylist允许存放null,所以也要进行判断处理
    if(obj==null){
      for(int index=0;index<size;index++){
        if(elementdata[index]==null){
           remove(index);
           return true;
        }
      }
    }else{
      for(int index=0;index<size;index++){
        if(obj.equals(elementdata[index])){
           remove(index);
           return true;
        }
      }
    }
    return false;
  }
  
  /**
   * 根据下标移除指定范围内的元素
   * @param fromindex 开始
   * @param toindex 结束
   */
  protected void removerange(int fromindex, int toindex){
    rangecheck(fromindex);
    rangecheck(toindex);
    //要移动的元素数
    int nummoved = size - toindex; 
    //把toindex后面的元素移动到fromindex
    system.arraycopy(elementdata, toindex, elementdata, fromindex, nummoved);
    //要移除的元素数量
    int newsize=size-(toindex-fromindex);
    while(size!=newsize){
      elementdata[--size]=null;
    } 
  }
  
  /**
   * 把数组容量调整到实际的容量
   */
  public void trimtosize(){
    int leng=elementdata.length;
    if(size<leng){
      object[] old=elementdata;
      elementdata=arrays.copyof(elementdata, size);
    }
  }
  /**
   * 把集合元素转换成数组
   * @return
   */
  public object[] toarray(){
    return arrays.copyof(elementdata, size);
  }
  
  public <t>t[] toarray(t[] a){
    if(a.length<size){
      return (t[]) arrays.copyof(elementdata,size, a.getclass());
    }
    //把集合元素复制到a数组中
    system.arraycopy(elementdata, 0, a, 0, size);
     if (a.length > size){
       for(int index=size;index<a.length;index++){
         a[index] = null;
       }
     }
     return a; 
  }

基本上都是对数组进行操作和使用c的方法进行赋值移动等,详细的可以查看原文,原文中除了那个私有变量外也没多少问题,代码可以完美运行,这李要注意的和难点就会是system,arraycopy和arrayist.copy()这2个方法
和在扩容方法里olddata这个变量的使用,这个变量真的很好,一开始我也不知道为什么要这么使用,在原文的末尾会进行解释。

以上所述是小编给大家介绍的java arraylist 实现实例讲解,希望对大家有所帮助