资讯专栏INFORMATION COLUMN

Java知识点总结(Java容器-ArrayList)

xzavier / 1686人阅读

摘要:知识点总结容器知识点总结容器底层实现是数组,访问元素效率高查询快,插入修改删除元素慢与相比,它效率高,但线程不安全。

Java知识点总结(Java容器-ArrayList)

@(Java知识点总结)[Java, Java容器, JavaCollection, JavaList]

ArrayList

底层实现是数组,访问元素效率高 (查询快,插入、修改、删除元素慢)

与LinkedList相比,它效率高,但线程不安全。

ArrayList数组是一个可变数组,可以存取包括null在内的所有元素

每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小

随着向ArrayList中不断增加元素,其容量自动增长

在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这样可以减少递增式再分配的数量。

所以如果我们明确所插入元素的多少,最好指定一个初始容量值,避免过多进行扩容操作而浪费时间、效率

源码分析 底层使用数组实现
transient  Object[] elementData;
构造方法
private  static final int DEFAULT_CAPACITY = 10;
private  static final Object[] EMPTY_ELEMENTDATA = {};
private  static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA  = {};
transient  Object[] elementData;
private  int size;
 
// 构造一个空列表
public  ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA ;
    }
 
// 构造一个指定初始容量的空列表
public  ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
 
 
// 构造一个指定Collection元素的列表,这些元素按照Connection元素的迭代返回顺序进行排列
public  ArrayList(Collection c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
 
存储
// 在列表的指定位置的元素用element替代,并且返回该位置原来的元素
public  E set(int index, E element) {
        rangeCheck(index); // 检查数组容量,抛出:IndexOutOfBoundsException
 
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
 
// 在列表的尾部添加指定元素
public  boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 数组扩容
        elementData[size++] = e;
        return true;
    }
 
// 在列表的指定位置添加元素
public  void add(int index, E element) {
        rangeCheckForAdd(index);
 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
 
        // src:源数组,srcPro:源数组中的起始位置
        // dest:目标数组,destPost:目标数组的起始位置,length:要复制的数组元素数量
              // 将当前位于该位置的元素以及所有后续元素后移一个位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 用element替换index位置的元素
        elementData[index] = element;
        size++;
    }
 
//  在列表的尾部添加Connection中的元素,元素顺序按照Connection迭代器返回的顺序
public  boolean addAll(Collection c) {
        Object[] a = c.toArray();  // 转化为一个数组
 
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
 
        // Increments modCount!!
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
 
//  在列表的指定位置添加Connection中的元素,元素顺序按照Connection迭代器返回的顺序
public  boolean addAll(int index, Collection c) {
        rangeCheckForAdd(index);
 
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
 
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
 
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
 
读取
// 移除此列表指定位置上的元素
public  E remove(int index) {
        rangeCheck(index);
 
        modCount++;
        E oldValue = elementData(index);
 
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
 
        return oldValue;
    }
 
// 移除此列表中的某个元素
public  boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
 
private  void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }
 

数组扩容

每当向数组中添加元素时,都需要去检查添加元素后元素的个数是否超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。

public  void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA )      
            ? 0 : DEFAULT_CAPACITY;
 
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
 
private  void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
 
        ensureExplicitCapacity(minCapacity);
    }
 
private  void ensureExplicitCapacity(int minCapacity) {
        modCount++;
 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 
private  void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
 
private  static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
 
手写ArrayList
public  class MyArrayList /*implements List*/{
  private transient Object[] elementData;
  private int size; //元素个数
  
  public MyArrayList(){
    this(10);
  }
 
  public MyArrayList(int initialCapacity) {
    if (initialCapacity<0) {
      try {
        throw new Exception();
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
    elementData = new  Object[initialCapacity];
  }
  
  public int size() {
    return size;
  }
  
  public boolean isEmpty(){
    return size == 0;
  }
  //根据index删掉对象
  public void remove(int index) throws Exception {
    rangeCheck(index);
    int numMoved = size-index-1;
    if (numMoved > 0) {
      System.arraycopy(elementData, index+1, elementData, index, numMoved);
    }
    elementData[--size] = null;
  }
  //删掉对象
  public boolean remove(Object obj) throws Exception {
    for (int i = 0; i < size; i++) {
      if (get(i).equals(obj)) {
        remove(i);
      }
      return true;
    }
    return true;
  }
  //修改元素
  public Object  set(int  index , Object obj ) throws Exception{
    rangeCheck(index);
    Object oldValue = elementData[index];
    elementData[index] = obj;
    return oldValue;
  }
  //在指定位置插入元素
  public void add(int index,Object obj) throws Exception {
    rangeCheck(index);
    ensureCapacity();
    System.arraycopy(elementData, index, elementData, index+1, size-index);
    elementData[index] = obj;
    size ++;
  }
  public void add(Object object) {
    ensureCapacity();
    /*elementData[size] = object;
    size ++;*/
    elementData[size++] = object; //先赋值,后自增
  }
  
  public Object get(int  index) throws Exception {
    rangeCheck(index);
    return elementData[index];
  }
  public void rangeCheck(int index) throws Exception {
    if (index<0 || index >=size) {
      throw new Exception();
    }
  }
  //扩容
  public  void  ensureCapacity() {
    //数组扩容和内容拷贝
    if (size==elementData.length) {
      //elementData = new  Object[size*2+1]; 这么写原来数组里的内容丢失
      Object[] newArray = new  Object[size*2+1];
      //拷贝数组里的内容
      /*for (int i = 0; i < newArray.length; i++) {
        newArray[i] = elementData[i];
      }*/
      System.arraycopy(elementData, 0, newArray, 0, elementData.length);
      elementData = newArray;
    }
  }
  // 测试
  public static void main(String[] args) {
    MyArrayList myArrayList = new MyArrayList(3);
    myArrayList.add("111");
    myArrayList.add("222");
    myArrayList.add("333");
    myArrayList.add("444");
    myArrayList.add("555");
    
    try {
      myArrayList.remove(2);
      myArrayList.add(3, "新值");
      myArrayList.set(1, "修改");
    } catch (Exception e1) {
      // TODO Auto-generated catch block
      e1.printStackTrace();
    }
    System.out.println(myArrayList.size());
    for (int i = 0; i < myArrayList.size(); i++) {
      try {
        System.out.println(myArrayList.get(i));
      } catch (Exception e) {
        e.printStackTrace();
      }
    }
  }
}


文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/69509.html

相关文章

  • Java识点总结Java容器-Vector)

    摘要:知识点总结容器知识点总结容器与相似,但是是同步的。所以说是线程安全的动态数组。如果集合中的元素的数目大于目前集合数组的长度时,增长率为目前数组长度的而增长率为目前数组长度的如过在集合中使用数据量比较大的数据,用有一定的优势。 Java知识点总结(Java容器-Vector) @(Java知识点总结)[Java, Java容器, JavaCollection, JavaList] Vec...

    mgckid 评论0 收藏0
  • Java识点总结Java容器-LinkedList)

    摘要:知识点总结容器知识点总结容器底层实现是双向循环链表,所以增删元素效率高,查询慢。若只对单条数据插入或删除,的速度反而优于。但若是批量随机的插入删除数据,的速度大大优于因为每插入一条数据,要移动插入点及之后的所有数据。 Java知识点总结(Java容器-LinkedList) @(Java知识点总结)[Java, Java容器, JavaCollection, JavaList] Lin...

    LuDongWei 评论0 收藏0
  • Java识点总结Java容器-List)

    摘要:知识点总结容器知识点总结容器接口为直接接口。对于而已,我们一般都是避免使用将当做首选,毕竟对于集合元素而已我们都是进行遍历,只有当程序的性能因为的频繁插入和删除而降低时,再考虑 Java知识点总结(Java容器-List) @(Java知识点总结)[Java, Java容器, JavaCollection, JavaList] [toc] List List接口为Collection直...

    xuhong 评论0 收藏0
  • Java集合总结【面试题+脑图】,将识点一网打尽!

    摘要:而在集合中,值仅仅是一个对象罢了该对象对本身而言是无用的。将这篇文章作为集合的总结篇,但觉得没什么好写就回答一些面试题去了,找了一会面试题又觉得不够系统。 前言 声明,本文用的是jdk1.8 花了一个星期,把Java容器核心的知识过了一遍,感觉集合已经无所畏惧了!!(哈哈哈....),现在来总结一下吧~~ 回顾目录: Collection总览 List集合就这么简单【源码剖析】 Ma...

    yearsj 评论0 收藏0
  • Week 2 - Java 容器 - 详细剖析 List 之 ArrayList, Vector,

    摘要:底层使用的是双向链表数据结构之前为循环链表,取消了循环。快速随机访问就是通过元素的序号快速获取元素对象对应于方法。而接口就是用来标识该类支持快速随机访问。仅仅是起标识作用。,中文名为双端队列。不同的是,是线程安全的,内部使用了进行同步。 前言 学习情况记录 时间:week 2 SMART子目标 :Java 容器 记录在学习Java容器 知识点中,关于List的需要重点记录的知识点。...

    MartinDai 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<