`
g21121
  • 浏览: 693841 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

List实现之ArrayList

 
阅读更多

        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 参数。源数组中位置在 srcPossrcPos+length-1 之间的组件被分别复制到目标数组中的 destPosdestPos+length-1 位置。

        如果参数 srcdest 引用相同的数组对象,则复制的执行过程就好像首先将 srcPossrcPos+length-1 位置的组件复制到一个带有 length 组件的临时数组,然后再将此临时数组的内容复制到目标数组的 destPosdestPos+length-1 位置一样。

arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

 
也就是说remove是一个移除指定index位置元素并将index后续元素位置左移的过程,而原数组elementData的length大小并不会改变,整个过程如下图所示:


 
        6.ArrayList转化成数组
        通过ArrayList中的toArray方法可以很方便的将List转换成数组形式,返回的数组是按适当顺序(从第一个到最后一个元素,也就是ArrayList中元素的添加顺序)返回包含此列表中所有元素的数组。

        由于此列表不维护对返回数组的任何引用,,因而它将是“安全的”。(换句话说,此方法必须分配一个新的数组)。因此,调用者可以自由地修改返回的数组。

        此方法担当基于数组的 API 和基于 collection 的 API 之间的桥梁。

        下面是一段ArrayList与数组转换的实例:

List list = new ArrayList();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
list.add("6");
//将ArrayList转换成数组
String[] strArray = (String[]) list.toArray(new String[list.size()]);
for (String str : strArray) {
	System.out.println(str);
}
//打印结果
1
2
3
4
5
6

        通过toArray方法返回的数组是全新创建的,所以修改此返回数组不会影响到原ArrayList。

 

        7.ArrayList的复制

        通过ArrayList中的clone方法可以复制 ArrayList 实例的浅表副本(不复制这些元素本身)。

        因为ArrayList的clone方法是浅表复制方法,所以只会复制ArrayList这一级实例,而不会复制ArrayList中更下一级的对象,通过以下代码可以比较直观的了解到这一点:

ArrayList<User> list1 = new ArrayList<User>();
ArrayList<User> list2;
User u1 = new User("john");
User u2 = new User("lily");
User u3 = new User("tom");
list1.add(u1);
list1.add(u2);
list1.add(u3);
// 此时克隆ArrayList
list2 = (ArrayList) list1.clone();
for (int i = 0, j = list1.size(); i < j; i++) {
	System.out.println(list1.get(i) == list2.get(i));
}
//修改其中一个对象的属性值
u2.setName("lucy");
System.out.println("-------------------");
for (int i = 0, j = list1.size(); i < j; i++) {
	System.out.println("list1:" + list1.get(i).getName() + "    list2:" + list2.get(i).getName());
//打印结果
true
true
true
-------------------
list1:john    list2:john
list1:lucy    list2:lucy
list1:tom    list2:tom
}

        至于浅表复制和深层复制感兴趣的可以查看一些相关的资料,这里就不做过多介绍了。

 

        8.ArrayList的序列化

        ArrayList经常会被用于系统间的数据传递,所以ArrayList实现java.io.Serializable接口可以被序列话也是顺利成章。

        但是细心的朋友应该会发现,ArrayList只有两个成员变量:size和elementData,其中elementData是用于存储数据的数组,所以elementData在传递过程中应该被序列化,然而“出乎意料”的是elementData却被transient关键字所修饰。

        transient关键字的作用就是阻止被修饰的属性被序列化,那elementData无法被序列化,我们岂不是得不到ArrayList中的元素了吗?

        其实不然,一个类是否被序列化可以使用以下两种方法之一:

        1.最简单的方法就是实现 Serializable接口,序列化时,调用java.io.ObjectOutputStream的defaultWriteObject方法,将对象序列化;反之读取也是调用的defaultReadObject默认方法。这种方法的好处就是程序员和使用者不必去关心序列化内部的细节,Java会自动完成这一切。

        缺点也很明显,就是无法根据特殊情景去自定义相关细节,而且此种方式中被transient所修饰的属性是不会被序列化的,也就是读取方无法获取该属性写入时的状态。

        2.另一种方式就是实现Serializable接口,并同时提供了writeObject(java.io.ObjectOutputStream s)方法。序列化时,会直接调用该类的writeObject方法。而不再是ObjectOutputStream的defaultWriteObject方法。此时被transient修饰的字段,是否会被序列化,取决于writeObject方法中对其的处理。

        这种方式的优点就是可以根据不同需求去自定义序列化处理流程,缺点就是需要重写writeObject与readObject方法以便调用。

 

        ArrayList就是采用的第二种序列化方式,下面是ArrayList中重写的两个方法:

/**
 * 保存ArrayList实例的状态至数据流中
 */
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
	// 写入元素个数和任何隐藏的属性
	int expectedModCount = modCount;
	s.defaultWriteObject();

	// 写入数组长度
	s.writeInt(elementData.length);

	// 按顺序写入所有元素
	for (int i = 0; i < size; i++)
		s.writeObject(elementData[i]);

	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}

}

/**
 * 从数据流中重建ArrayList实例
 */
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
	// Read in size, and any hidden stuff
	s.defaultReadObject();

	// Read in array length and allocate array
	int arrayLength = s.readInt();
	Object[] a = elementData = new Object[arrayLength];

	// Read in all elements in the proper order.
	for (int i = 0; i < size; i++)
		a[i] = s.readObject();
}

        两个方法并不复杂,以writeObject为例:

        首先,方法中调用了defaultWriteObject默认方法,此时被 transient所修饰的 elementData 数组并不会被写入。

        然后,方法主动将数组长度写入。

        最后,按照顺序将 elementData中已添加的元素依次写入。

需要注意的是,在将 elementData数组中元素依次写入的过程中,for循环中i小于的是ArrayList的size,而不是 elementData本身的长度。

        这一点也比较好理解,虽然 ArrayList内部使用的是数组 elementData作为元素存储,但是 elementData并不一定会被全部利用,也就是说 elementData中小于size的部分是已经添加元素的部分,其余都是null。

        所以在设计ArrayList时将其内部数组 elementData声明为transient也是出于这方面的考虑,只有被使用的部分才会去被序列化,这样效率与空间都得到了最大的利用。

 

        至此ArrayList相关部分知识与结构基本已经清晰,希望大家在工作和学习过程中更进一步,更深一层次的去了解某些看似简单的东西,下一篇LinkedList。

3
4
分享到:
评论

相关推荐

    自定义实现的ArrayList

    自定义实现的ArrayList数据结构,有大量注释以及编写思路,帮助新手用Java语言来实现数据结构

    用java自己实现的arrayList

    用java自己实现的arrayList,比较详细,有助于初学者理解arrayList的基本概念和基础用法

    JavaScript 实现基础 ArrayList 功能

    虽然JavaScript原生不支持ArrayList,但我们可以利用数组(Array)对象来实现类似的功能。下面将详细介绍如何使用JavaScript来实现基础的ArrayList功能,并探讨在没有参数重载(overload)的情况下如何处理方法的...

    java基础--list(ArrayList、LinkedList、匿名类).docx

    ArrayList和LinkedList是List接口的两种主要实现,它们各有优缺点,适用于不同的场景。此外,匿名类的概念在Java中用于简化代码结构,尤其是在实现接口时。 1. **List接口** List接口继承自Set接口,它不仅提供了...

    经典讲解List和ArrayList和Vector和HashTable和HashMap区别

    - **存储方式**:`List`接口的实现(如`ArrayList`和`Vector`)是有序的,而`Map`接口的实现(如`HashTable`和`HashMap`)是键值对形式,通过键来查找值。 - **数据访问**:`ArrayList`和`Vector`支持通过索引访问...

    ArrayList实现对产品CRUD

    在Java编程语言中,ArrayList是Java集合框架的重要组成部分,它属于List接口的一个具体实现,用于存储可变大小的有序对象列表。在这个“ArrayList实现对产品CRUD”的项目中,我们将探讨如何利用面向对象编程(OOP)...

    ArrayList的实现原理

    ArrayList是Java集合框架中常用的动态数组,它是List接口的一个实现,允许存储包括null在内的所有元素。ArrayList的主要特点是通过数组来存储元素,提供了丰富的操作方法,包括添加、删除、修改和查询等。下面是...

    arraylist 和 list<T> 效率对比

    相比之下,List是C# 2.0引入的泛型集合,它实现了IList接口,提供类型安全的数据存储。由于List知道它将存储哪种类型的数据,因此无需进行显式的类型转换,这极大地提高了代码的可读性和安全性。List同样使用动态...

    List集合之ArrayList

    ArrayList是Java集合框架中List接口的一个具体实现,它继承了AbstractList抽象类,并实现了List、RandomAccess、Cloneable和Serializable接口。ArrayList的核心特点是其内部基于动态数组的数据结构,即使用Object...

    List、ArrayList、Vector及map、HashTable、HashMap分别的区别

    ArrayList和LinkedList是两种常用的List实现类。ArrayList实现了可变大小的数组,它允许所有元素,包括null。ArrayList没有同步。size、isEmpty、get、set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个...

    用ArrayList实现用户信息的添加,删除,更新,查询

    在Java编程中,ArrayList是一个常用的集合类,它继承自AbstractList并实现了List接口。ArrayList以动态数组的形式存储数据,提供了一种高效的方式来管理和操作对象序列。在这个场景中,我们使用ArrayList来实现用户...

    android arraylist 实现 listview

    ArrayList&lt;User&gt; userList = new ArrayList(); ``` 接着,我们创建一个自定义的Adapter,它会把ArrayList的数据绑定到ListView的各个视图(ViewHolder)上。Adapter通常继承自BaseAdapter,包含四个核心方法:`...

    arraylist用法

    在.NET Framework中,`ArrayList`实现了`ICollection`和`IList`接口,这意味着它支持列表的基本功能,如添加、删除元素等。 #### 二、如何使用ArrayList? 创建一个`ArrayList`实例非常简单: ```csharp ...

    用C语言模拟ArrayList

    下面,我们将深入探讨如何用C语言实现ArrayList及其相关的知识点。 首先,`Array.c`文件通常会包含ArrayList的核心实现,包括数据结构定义、初始化、添加元素、删除元素、查找元素等函数。在C语言中,我们可以通过...

    arrayList排序

    ArrayList是Java编程语言中常用的集合类之一,它继承自AbstractList并实现了List接口。ArrayList以对象数组的形式存储数据,提供了动态增长的能力,便于增删改查操作。在处理大量数据时,排序是常见的需求,本篇文章...

    Java容器类List、ArrayList、Vector及map、HashTable应用

    ArrayList是Java中最常用的List实现类,它提供了高效的插入、删除和遍历元素的方法。ArrayList基于数组实现,故插入和删除元素时需要移动数组元素,性能较慢。但是ArrayList的优点是可以随机访问元素,使用索引来...

    源码解析jdk7.0集合:ArrayList的底层实现原理.pdf

    在探讨 JDK 7.0 中 ArrayList 的底层实现原理之前,首先需要了解 ArrayList 作为 Java 集合框架中 List 接口的动态数组实现类的基本概念。ArrayList 提供了一种存储有序、可重复、允许为 null 的数据结构,并且该...

    深入Java集合学习系列(三):ArrayList实现原理

    首先,ArrayList是Java集合框架中List接口的一个非常重要的实现。它允许包含重复的元素,也允许插入null值,这是区别于Java集合中的另一个List接口实现类LinkedList的重要特点。ArrayList内部通过一个数组来保存其...

    Map+List+ArrayList+LinkedList Java源码

    常见的List实现类有ArrayList和LinkedList。 **ArrayList类** `ArrayList`是基于数组实现的List,它提供了一个动态增长的数组来存储元素。由于其底层是数组,所以它的随机访问(通过索引)速度非常快。但是,插入和...

    手写精简版List和ArrayList,适合新手入门学习jdk源码demo

    本文将针对新手,详细讲解如何手写一个精简版的`List`和`ArrayList`,帮助大家更好地理解JDK源码中的实现原理。 首先,我们要明白`List`是一个接口,它继承自`Collection`接口,并规定了元素的有序性和可重复性。`...

Global site tag (gtag.js) - Google Analytics