List的主要实现类为:AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector.
大多数情况我们实现List这个接口时使用的是ArrayList这个实现类,ArrayList类是List 接口的大小可变数组的实现,所以ArrayList的字面意思就是“数组列表”的意思。ArrayList实现了List接口所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于 Vector 类,除了此类是不同步的。)
下面就从ArrayList的使用和内部实现几个方面来深入学习一下ArrayList:
1.ArrayList初始化
使用ArrayList之前需要先实例化,代码如下:
List list=new ArrayList(); 或 ArrayList list=new ArrayList();
一般情况下我们都是使用默认构造方法来实例ArrayList,ArrayList的默认构造方法源代码如下:
//ArrayList内部是以一个对象数组形式实现,transient作用是放弃序列化 private transient Object[] elementData; /** * 构造一个空的list时,初始容量为10 */ public ArrayList() { this(10); } /** * 构造一个空的list时,初始容量为指定值 */ public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); this.elementData = new Object[initialCapacity]; }
当我们利用默认构造方法实例化一个 ArrayList时,看到默认构造方法中调用了另一个重构方法,并指定了其默认大小为10,也就是说在不指定 ArrayList大小时,其内部实现数组的默认长度为10。
当然我们也可以在实例化时指定ArrayList的大小:
int size=20; List list=new ArrayList(size); 或 ArrayList list=new ArrayList(size);
实例化时指定ArrayList大小的好处就是减少其内部数组因元素个数超出数组大小时进行扩容所消耗掉的性能。
2.ArrayList的成员变量
ArrayList类只有两个成员变量:elementData与size:
/** * 用来存储ArrayList实例所添加的元素 * ArrayList的 capacity(容量)等于该数组的长度 */ private transient Object[] elementData; /** * ArrayList的size (也就是ArrayList实例所含有的元素个数). */ private int size;
size很好理解,就是ArrayList的长度大小,也可理解为ArrayList中已添加的元素个数,这里需要注意:ArrayList允许添加为null的元素,所以null也会占用一份空间。
elementData就是ArrayList的内部数组实现,它是一个一维对象数组。当通过add方法向ArrayList中添加元素时,这些元素就会被依次存储于elementData这个数组中。
elementData既然是数组,它必然拥有长度length,那么这个数组的长度是否等于ArrayList的size?
这里就需要了解一些ArrayList的相关设计概念:
首先作为ArrayList的内部实现数组elementData具备一定的长度(初始值为10),此长度又被称为capacity(容量)。
而每一个ArrayList实例又具有一个size,此size是该实例的列表长度,这其中capacity永远等于数组elementData的长度,并永远大于等于列表size。
所以capacity可以理解为ArrayList的容纳能力,而size可以理解为已使用的空间大小。
下面举一个生动的例子可能更好理解这两个概念:
我们可以把ArrayList理解为上图中的容器,这个容器初始的大小是10,容器的大小也就是上面所说的capacity。
此时我们使用这个容器,往容器中填充元素。其中所占用的空间就可以理解为size。
无论桶是空的还是正好盛满了水,容器的大小(capacity)都是不变的,而其中size会随着填充元素数量增加而增加,但最终只可能等于容器大小。
3.ArrayList的“可变大小”
之前已经重复了解了ArrayList的capacity与size两者的不同与所代表的意义。初始化的ArrayList容量为10,但是当我想填充超过10或更多的元素时怎么办?
原来的容器的大小是无法满足这个需求的,只有更换一个更大的容器来才容纳更多的元素。那么ArrayList又是如何实现这部分的呢?
首先需要先了解ArrayList添加元素的过程和处理方式,这样才能了解到以上两个问题的解决方法。
添加元素是通过add方法来完成的,所以我们要先分析下它的源码,以下是add方法的源代码:
/** * 添加指定元素至list末尾 */ public boolean add(E e) { ensureCapacity(size + 1); // 增加modCount elementData[size++] = e; return true; }
add方法虽简单却比较重要,在添加元素至elementData数组前先要调用ensureCapacity方法来判断现elementData数组是否已经无法再添加新元素,如果还没有满则直接返回,如果已经满了则需要对elementData数组进行扩容,扩容后添加新元素。
之前已经了解到在初始化 ArrayList时我们可以指定其内部的数组长度,也就是 initialCapacity。只有在使用ArrayList,往里面添加元素时 size的值才会不断增加,直到与 capacity相等为止。
当 elementData所有索引位置均被填满元素的时候,此时的size=capacity。当再往其中添加新的元素时,此时原数组已经无法添加就需要扩充数组大小以满足新元素的添加。
ensureCapacity方法的作用就是在必要时扩容elementData数组:
/** * 增加这个ArrayList实例的capacity,如果必要的话确保它可以容纳minCapacity数量的元素 */ public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3) / 2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }
方法中 oldCapacity就是原数组的大小,minCapacity就是新数组最小的大小,也就是容纳所有元素所需的数组长度,如果 minCapacity已经大于了现使用数组的长度,则证明需要扩容。
将添加过程分成几个流程会更好的理解:
1)新建一个ArrayList实例,默认capacity为10:
List list=new ArrayList();
此时该实例内部如图:
list内部数组elementData的length与capacity为10,list的size为0。
2)此时不断往list里添加元素,当元素个数不超过10时,elementData数组的大小并不会变化,当添加到第11个元素时:
List list=new ArrayList(); list.add(1); ...添加 list.add(10); //添加10个元素后,此时capacity=10,size=10 //添加第11个元素 list.add(11); //此时capacity=16,size=11 ...添加 list.add(21); //当添加至第21个元素时,此时capacity=31,size=21
可以看到capacity的增加幅度并不是每次都相同的,它是根据int newCapacity = (oldCapacity * 3) / 2 + 1;这个算法来计算的(原数组大小乘3再除以2,然后结果加1),这样做最大的优点就是在满足一定容量的基础上,然后根据我们现有的数组长度去计算一个较为合适的增长幅度,这样可以在保证一定效率的情况下尽量满足元素的添加。
所以说ArrayList的每次add操作的开销上并不一定是相同的,它会有一定的线性增长过程,只有程序员更主动的去规划ArrayList的长度范围才能更好的避免这一问题。
4.获取元素
ArrayList通过get方法获得指定index位置的元素内容,因为我们已经知道ArrayList的内部实现是数组,所以每次get方法调用只是返回该下标下的数组元素而已:
public E get(int index) { RangeCheck(index);//检查index值是否越界 return (E) elementData[index];//直接返回该下标下的数组元素内容 }
在获取元素之前会先判断指定的index下标是否越界,通过校验之后返回该位置的元素内容。
5.移除元素
通过对ArrayList内部结构及实现方式的了解,当容器不足以容纳新元素时会进行扩容,当如果我们移除元素之后容器是否会“减容”呢?
最直接的办法就是查看源代码,下面是remove的源代码:
/** * 从列表中移除指定位置的元素,然后所有后续元素左移(下标减1) */ public E remove(int index) { //检查是否越界 RangeCheck(index); modCount++; //原index位置元素 E oldValue = (E) elementData[index]; //位移至 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index + 1, elementData, index, numMoved); elementData[--size] = null; // Let gc do its work //返回原index位置元素 return oldValue; }
remove方法中核心的部分就是System.arraycopy(elementData, index + 1, elementData, index, numMoved);这段代码,这段代码的作用就是从指定源数组中复制一个数组,复制从指定的位置开始,到目标数组的指定位置结束。从 src
引用的源数组到 dest
引用的目标数组,数组组件的一个子序列被复制下来。被复制的组件的编号等于 length
参数。源数组中位置在 srcPos
到 srcPos+length-1
之间的组件被分别复制到目标数组中的 destPos
到 destPos+length-1
位置。
如果参数 src
和 dest
引用相同的数组对象,则复制的执行过程就好像首先将 srcPos
到 srcPos+length-1
位置的组件复制到一个带有 length
组件的临时数组,然后再将此临时数组的内容复制到目标数组的 destPos
到 destPos+length-1
位置一样。
arraycopy(Object src, int srcPos, Object dest, int destPos, int length)也就是说remove是一个移除指定index位置元素并将index后续元素位置左移的过程,而原数组elementData的length大小并不会改变,整个过程如下图所示:
相关推荐
自定义实现的ArrayList数据结构,有大量注释以及编写思路,帮助新手用Java语言来实现数据结构
用java自己实现的arrayList,比较详细,有助于初学者理解arrayList的基本概念和基础用法
虽然JavaScript原生不支持ArrayList,但我们可以利用数组(Array)对象来实现类似的功能。下面将详细介绍如何使用JavaScript来实现基础的ArrayList功能,并探讨在没有参数重载(overload)的情况下如何处理方法的...
ArrayList和LinkedList是List接口的两种主要实现,它们各有优缺点,适用于不同的场景。此外,匿名类的概念在Java中用于简化代码结构,尤其是在实现接口时。 1. **List接口** List接口继承自Set接口,它不仅提供了...
- **存储方式**:`List`接口的实现(如`ArrayList`和`Vector`)是有序的,而`Map`接口的实现(如`HashTable`和`HashMap`)是键值对形式,通过键来查找值。 - **数据访问**:`ArrayList`和`Vector`支持通过索引访问...
在Java编程语言中,ArrayList是Java集合框架的重要组成部分,它属于List接口的一个具体实现,用于存储可变大小的有序对象列表。在这个“ArrayList实现对产品CRUD”的项目中,我们将探讨如何利用面向对象编程(OOP)...
ArrayList是Java集合框架中常用的动态数组,它是List接口的一个实现,允许存储包括null在内的所有元素。ArrayList的主要特点是通过数组来存储元素,提供了丰富的操作方法,包括添加、删除、修改和查询等。下面是...
相比之下,List是C# 2.0引入的泛型集合,它实现了IList接口,提供类型安全的数据存储。由于List知道它将存储哪种类型的数据,因此无需进行显式的类型转换,这极大地提高了代码的可读性和安全性。List同样使用动态...
ArrayList是Java集合框架中List接口的一个具体实现,它继承了AbstractList抽象类,并实现了List、RandomAccess、Cloneable和Serializable接口。ArrayList的核心特点是其内部基于动态数组的数据结构,即使用Object...
ArrayList和LinkedList是两种常用的List实现类。ArrayList实现了可变大小的数组,它允许所有元素,包括null。ArrayList没有同步。size、isEmpty、get、set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个...
在Java编程中,ArrayList是一个常用的集合类,它继承自AbstractList并实现了List接口。ArrayList以动态数组的形式存储数据,提供了一种高效的方式来管理和操作对象序列。在这个场景中,我们使用ArrayList来实现用户...
ArrayList<User> userList = new ArrayList(); ``` 接着,我们创建一个自定义的Adapter,它会把ArrayList的数据绑定到ListView的各个视图(ViewHolder)上。Adapter通常继承自BaseAdapter,包含四个核心方法:`...
在.NET Framework中,`ArrayList`实现了`ICollection`和`IList`接口,这意味着它支持列表的基本功能,如添加、删除元素等。 #### 二、如何使用ArrayList? 创建一个`ArrayList`实例非常简单: ```csharp ...
下面,我们将深入探讨如何用C语言实现ArrayList及其相关的知识点。 首先,`Array.c`文件通常会包含ArrayList的核心实现,包括数据结构定义、初始化、添加元素、删除元素、查找元素等函数。在C语言中,我们可以通过...
ArrayList是Java编程语言中常用的集合类之一,它继承自AbstractList并实现了List接口。ArrayList以对象数组的形式存储数据,提供了动态增长的能力,便于增删改查操作。在处理大量数据时,排序是常见的需求,本篇文章...
ArrayList是Java中最常用的List实现类,它提供了高效的插入、删除和遍历元素的方法。ArrayList基于数组实现,故插入和删除元素时需要移动数组元素,性能较慢。但是ArrayList的优点是可以随机访问元素,使用索引来...
在探讨 JDK 7.0 中 ArrayList 的底层实现原理之前,首先需要了解 ArrayList 作为 Java 集合框架中 List 接口的动态数组实现类的基本概念。ArrayList 提供了一种存储有序、可重复、允许为 null 的数据结构,并且该...
首先,ArrayList是Java集合框架中List接口的一个非常重要的实现。它允许包含重复的元素,也允许插入null值,这是区别于Java集合中的另一个List接口实现类LinkedList的重要特点。ArrayList内部通过一个数组来保存其...
常见的List实现类有ArrayList和LinkedList。 **ArrayList类** `ArrayList`是基于数组实现的List,它提供了一个动态增长的数组来存储元素。由于其底层是数组,所以它的随机访问(通过索引)速度非常快。但是,插入和...
本文将针对新手,详细讲解如何手写一个精简版的`List`和`ArrayList`,帮助大家更好地理解JDK源码中的实现原理。 首先,我们要明白`List`是一个接口,它继承自`Collection`接口,并规定了元素的有序性和可重复性。`...