`
g21121
  • 浏览: 684188 次
  • 性别: 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的基本概念和基础用法

    List集合之ArrayList

    ArrayList集成AbstractList抽象类,实现了List、RandomAccess、Cloneable、java.io.Serializable这四个接口,其中我们可以看到,实现了Cloneable和Serializable接口就代表着ArrayList是支持克隆和序列化的,这里有个...

    ArrayList实现对产品CRUD

    用oop思想实现对ArrayListCRUD,操作的是产品对象,很适合初学者研究。

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

    用ArrayList来实现用户信息的添加,删除,更新,查询.实现比较好.

    Java学生成绩管理系统实例(ArrayList)

    实现一个学生成绩管理的简单系统。要求可以添加、删除、修改、查询成绩 创建界面相关的接口:将菜单中显示的内容定义成若干字符串常量,放入一个接口Menu中以便使用 TestDemo(主类) import java.util.ArrayList; ...

    ArrayList和Linkedlist1

    1.List是接口类,ArrayList和LinkedList是List的实现类 2.ArrayList是动态数组(顺序表)的数据结构 3.LinkedList

    ArrayList.txt

    2、实现了ICollection和List接口 3、灵活的设置了数组的大小 当我们不知道到底有多少个数据元素的时候,就可以使用ArrayList; 如果我们知道数据集合有多少个元素,就用数组; 二、如何构建ArrayList 1、...

    List实现类中的ArrayList、Vector、LinkedList

    List list = new ArrayList();可以把接口的好处5体现出来,如果ArrayList()不满足需求,直接更换就可以。 接口的好处: 1.程序的耦合度降低 2.更自然的使用多态 3.设计与实现完全分离 4.更容易搭建程序框架 5.更容易...

    javalist数据结构-Java数据结构-------List.pdf

    javalist数据结构_Java数据结构-------List 三种List:ArrayList,Vector,LinkedList 类继承关系图 ArrayList和Vector通过数组实现,⼏乎使⽤了相同的算法;区别是ArrayList不是线程安全的,Vector绝⼤多数⽅法做了...

    Java进阶--深入理解ArrayList实现原理

    ArrayList就是动态数组,用MSDN中的说法,就是Array的复杂版本,它提供了动态的增加和减少元素,实现了Collection和List接口,可以灵活的设置数组的大小。要注意的是ArrayList并不是线程安全的,因此一般建议在单...

    Java ArrayList

    InitArray自己编写的一个JAVA用的集合类,试试效果如何。

    Android ArrayList关键字查询.rar

    Android ArrayList关键字查询可实现 listview列表查询关键字

    java关键字ArrayList详解

    ArrayList是Java中的一种常见的数据结构,它实现了List接口,是线程不安全的动态数组。它的容量可以自动增长,因此可以方便地插入、删除和查找数据,是Java集合框架中广泛使用的一种结构。 ArrayList的优势在于灵活...

    js实现ArrayList功能附实例代码

    1.ArrayList方法摘要 构造方法摘要 ArrayList() 构造一个初始容量为 10 的空列表。 ArrayList(Collection&lt;? extends E&gt; c) 构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器...

    ii0#book-3#ArrayList 、 LinkedList 、 Vector 的底层实现和区别1

    Java基础之集合List-ArrayList、LinkedList、Vector的底层实现和区别ArrayList底层实际是采用数组实现的(并且该数组的类型是

    容器之ArrayList与HashMap底层实现

    老规矩先上框架图: ...import java.util.List; /** * 测试Collection接口中的方法 */ public class TestArraylist { public static void main(String[] args) { test03(); } public static void test0

    java实现innerjoin关联算法

    现在需要根据一个输入的字符"list1.column1=list2.column2,list1.column3=list3.column4"(不是固定的)来实现inner join关系的控制,即list1中的map和list2中map通过key值column1和column2关联,同时list1中的map和...

    对java基础集合部分(List、HashMap、HashSet、ArrayList等)底层源码的分析与总结

    这篇集合总结一共包括十二节,介绍了一些接口和实现类的底层源码以及基本的增加、删除元素等的操作(包括List、Map、Set接口、ArrayList、Vector、LinkedList、HashSet、TreeSet、HashMap、TreeMap等实现类)。...

Global site tag (gtag.js) - Google Analytics