Java容器ArrayList知识点总结

作者:苏生 时间:2023-09-05 17:46:04 

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<? extends E> 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<? extends E> 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<? extends E> 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<E>*/{
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://segmentfault.com/a/1190000015015669

标签:Java,ArrayList
0
投稿

猜你喜欢

  • Android中解决页签手指按下从左到右滑动的bug

    2021-06-04 19:22:40
  • android6.0权限动态申请框架permissiondispatcher的方法

    2023-07-31 10:51:57
  • Java 单例模式的实现资料整理

    2022-05-29 21:27:33
  • 实例讲解建立Android项目

    2023-10-04 17:41:20
  • 解决Intellij IDEA 使用Spring-boot-devTools无效的问题

    2023-09-17 20:49:47
  • Android沉浸式状态栏的实现代码

    2023-08-21 05:52:08
  • C#实现文字转语音功能

    2022-06-18 13:07:59
  • SpringBoot-RestTemplate实现调用第三方API的方式

    2022-12-29 09:49:56
  • 解决SpringMVC项目连接RabbitMQ出错的问题

    2022-12-22 13:05:51
  • Spring Bean的初始化和销毁实例详解

    2023-10-28 05:56:04
  • 使用windows控制台调试服务的方法

    2023-08-19 03:34:30
  • 深度解析Java中ArrayList的使用

    2023-06-16 23:26:01
  • Android table布局开发实现简单计算器

    2021-07-15 13:05:28
  • mybatis QueryWrapper的条件构造之apply、last、select解析

    2022-02-12 17:32:51
  • Mybatis SqlSessionFactory与SqlSession详细讲解

    2021-12-24 22:42:56
  • C#实现计算年龄的简单方法汇总

    2022-12-26 01:12:41
  • Java进阶知识之反射的概念与获取方法

    2023-12-09 19:09:14
  • C++实现softmax函数的面试经验

    2023-06-16 02:07:47
  • SpringBoot-JPA删除不成功,只执行了查询语句问题

    2022-09-10 04:13:55
  • Java创建和启动线程的两种方式实例分析

    2023-12-05 08:26:59
  • asp之家 软件编程 m.aspxhome.com