1.概述
先来看一下Android中常见数据结构的继承关系结构图，如下图所示：
Collection.png
Map.png
红色的表示接口，黑色的表示实现类。可以看到分为两大接口，Collection和Map。其中Collection可以看做是value的集合，Map可以看做（key, value）的集合。List和Set是继承Collection的子接口，List、Set和Map及他们各自的实现类都是开发中常用的。当然，除了上图所示的Java提供的api外，Android也提供了一些更适用于移动平台的数据结构api以减小内存消耗，提高性能。本系列博文准备分为4个部分来介绍Android中的数据结构：
①List接口及其实现类
②Set接口及其实现类
③Map接口及其实现类
④Android中用来代替HashMap的数据结构api：SparseArray和ArrayMap
本文主要介绍了第一部分，List接口的三个实现类：ArrayList、LinkedList和Vector
2.ArrayList
ArrayList是List接口动态数组的实现方式。数组的特点是其中的元素在内存中的地址是连续的。所以ArrayList的优点在于get、set的效率高，时间复杂度为常数。缺点是在ArrayList中插入和删除效率较低，由于每插入/删除一项，都需要移动后续所有项的位置，时间复杂度为O(N)。
ArrayList的常用方法包括get、set、size、isEmpty、add、remove、clear、toArray、contains、indexOf、lastIndexOf、ensureCapacity等方法。前几个方法比较简单，就不介绍了。看一下其他几个方法。
Object[] toArray()
<T> T[] toArray(T[] a)
toArray有两个重载方法，可以很方便的将List转换为为数组。
boolean contains(Object o)
如果List中包含该元素，则返回true，否则返回false。
int indexOf(Object o)
int lastIndexOf(Object o)
这两个方法分别返回List中首次/最后一次出现该元素的位置，如果没有这个元素，则返回-1。
这里需要注意的是，使用contains、indexOf、lastIndexOf这三个方法前，都是需要重写对象的equals方法的，否则contains将永远返回false，indexOf、lastIndexOf将永远返回-1。为什么呢？来看一下源码：
@Override public boolean contains(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return true;
}
}
}
return false;
}
@Override public int indexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return i;
}
}
}
return -1;
}
可以看到，contains和indexOf都是通过equals来判断是否是同一个元素的，而我们知道，如果不重写equals方法，则默认比较地址，那么返回的一定是false。所以，我们需要重写equals方法来自己判断，例如可以通过比较对象中一个特征字段的值来比较两个对象是否相等。
void ensureCapacity(int minCapacity)
前面提过，ArrayList是通过动态数组实现的，ArrayList初始化时会在内存里开辟一块空间，那么如果数据越来越多，这块空间不够用了怎么办呢？ensureCapacity方法可以帮助你扩充原有的数组，实现方式是创建一个新数组并给这个数组重新分配长度为minCapacity的一块内存区域，然后将旧数组的内容拷贝到新数组中，这样就实现了ArrayList的扩容。
说到这里可能有人会有疑问了：平时开发中，都是用ArrayList List = new ArrayList( ); 这样初始化的，然后不停的往里add，好像也没出现什么问题啊？其实这是因为ArrayList自动帮你做了扩容的动作。如果初始化时没有指定ArrayList的大小，将会默认初始化一个长度为10的数组，每当向ArrayList中add元素时，都会先判断数组长度是否足够，如果不够了，那自动将长度扩充为原数组长度*2。前面说过，每扩容一次，都会开辟一块新的内存空间，同时造成了原有内存空间的浪费。所以，如果你从一开始就确定这个ArrayList里至少有100个元素，那么使用ArrayList List = new ArrayList(100);来初始化，就能提升使用效率，减少内存消耗。
3.LinkedList
LinkedList是采用双向链表实现的。所以它也具有链表的特点，每一个元素（结点）的地址不连续，通过引用找到当前结点的上一个结点和下一个结点，即插入和删除效率较高，只需要常数时间，而get和set则较为低效，需要O(N)的时间。
LinkedList的方法和使用和ArrayList大致相同，由于LinkedList是链表实现的，所以额外提供了在头部和尾部添加/删除元素的方法，也没有ArrayList扩容的问题了。另外，ArrayList和LinkedList都可以实现栈、队列等数据结构，但LinkedList本身实现了队列的接口，所以更推荐用LinkedList来实现队列和栈。
4.Vector
前面提到的ArrayList、LinkedList，都是线程不安全的，即在多线程下修改数据可能会造成数据错乱，重复增删等问题。Vector和ArrayList比较类似，但不同的是Vector中的很多重要方法都是用synchronized实现同步，保证线程安全。在多线程下如果要保证线程安全，那么使用Vector比较好，但是在保证线程安全的同时效率也会下降。
5.总结
综上所述，在需要频繁读取集合中的元素时，使用ArrayList效率较高，而在插入和删除操作较多时，使用LinkedList效率较高。使用Vector可以多线程下保证修改数据线程安全。
网友评论