数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组
具有相同类型数据的集合。
数组的特点:
1.数组是相同数据类型的集合。(int类型的数组不能放double类型)
2.数组中各元素的存储是有先后顺序的,它们在内存中按照这个顺序连续存放到一起。内存地址连续。
3. 数组获取元素的时间复杂度为 O(1)- 实现数组列表
package array_list; /** * @author cv master * @date 2022/12/6 9:59 */ public interface List<E> { boolean add(E e); E remove(int index); E get(int index); }
1. 初始化 ArrayList 阶段,如果不指定大小,默认会初始化一个空的元素。这个时候是没有默认长度的。 2. 那么什么时候给初始化的长度呢?是在首次添加元素的时候,因为所有的添加元素 操作,也都是需要判断容量,以及是否扩容的。那么在 add 添加元素时统一完成这个操作。 3. 之后就是随着元素的添加,容量是会出现不足。当容量不足的是,需要进行扩容操作。同时还需要把旧数据迁移到新的数组上。另外数据的迁移算是一个比较耗时的操 作。
package array_list; import java.util.Arrays; /** * @author cv master * @date 2022/12/6 10:00 */ public class ArrayList<E> implements List<E> { /** * 默认初始化空间 **/ private static final int DEFAULT_CAPACITY = 10; /** * 空元素 **/ private static final Object[] DEFAULT_CAPACITY_EMPTY_ELEMENT_DATA = {}; /** * ArrayList 元素数据缓存区 **/ transient Object[] elementData; /** * List集合元素数量 **/ private int size; public ArrayList() { this.elementData = DEFAULT_CAPACITY_EMPTY_ELEMENT_DATA; } @Override public boolean add(E e) { //确保内部容量 int minCapacity = size + 1; if (elementData == DEFAULT_CAPACITY_EMPTY_ELEMENT_DATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //判断扩容操作 if (minCapacity - elementData.length > 0) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } elementData=Arrays.copyOf(elementData, newCapacity); } elementData[size++] = e; return true; } @Override public E remove(int index) { E element = (E) 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 element; } @Override public E get(int index) { return (E) elementData[index]; } @Override public String toString() { return "ArrayList{" + "elementData=" + Arrays.toString(elementData) + ", size=" + size + '}'; } }
- 这是一份简化后的 ArrayList##add 操作
- ArrayList 的元素删除。
就是在确定出元素位置后,使用 System.arraycopy 拷贝数据
方式移动数据,把需要删除的元素位置覆盖掉。 此外它还会把已经删除的元素设置为 null 一方面让我们不会在读取到这个元素,另 外一方面也是为了 GC。package array_list; import org.junit.Test; import org.slf4j.Logger; import org.slf4j.LoggerFactory; /** * @author cv master * @date 2022/12/6 10:34 */ public class ArrayListTest { private final Logger logger = LoggerFactory.getLogger(ArrayListTest.class); @Test public void test_array_list() { List<String> list = new ArrayList<>(); list.add("01"); logger.info(list.toString()); list.add("02"); list.add("03"); list.add("04"); list.add("05"); list.add("06"); list.add("07"); list.add("08"); list.add("09"); list.add("10"); list.add("11"); list.add("12"); logger.info(list.toString()); list.remove(9); logger.info(list.toString()); System.out.println(list.get(1)); } }
标签:元素,int,ArrayList,elementData,list,add,数组,Array From: https://www.cnblogs.com/luorongxin/p/16954789.html