开发中，一个贴切的数据结构，可以非常好的满足需求的同时，最大程度的节省内存，这是一个精细的开发者必须要考虑的事情。 在这里，稍微总结一下安卓开发中经常会使用到的一些数据结构，请大佬批评指正。

1，数据结构与算法 数据结构，表示一种数据模型，模型的元素之间存在着逻辑结构以及存储结构； 算法表示一种规则或者说是一种策略。

数据对象中数据元素之间的相互关系，也就是逻辑关系基本上可以分为： 集合结构，线性结构，属性结构，图形结构。

存储关系： 链式存储，顺序存储；

Android中的List就是线性的存储结构，List本身是一个接口，使用过程中其实是使用它的实现类，其中ArrayList是线性的存储结构，LinkList是链式的存储结构。

线性的存储结构的特点是快速的查询，可以很方便的计算各个元素的地址，但是插入和删除的操作消耗是比较大的，因为删掉或者插入中间的某一个元素，这个元素后面的元素都要进行位置的变迁， 线性存储单元，在内存中是连续的。但是链式存储单元之间，可以是连续的也可以是不连续的。链式存储单元内部包含存储数据的部分，还包含一个指示其直接后继的信息的部分，其实就是相当于c语言中的指针，Java中的下一个元素的对象。 链式存储的特点是，查找耗费比较高，但是删除和插入操作是最快的，因为插入删除，只是和当前的位置的一个节点有关系。

到底层看看源码是怎么写的：

private static final int MIN_CAPACITY_INCREMENT = 12; /** * The elements in this list, followed by nulls. */ transient Object[] array; /** * Constructs a new instance of {@code ArrayList} with the specified * initial capacity. * * @param capacity * the initial capacity of this {@code ArrayList}. */ public ArrayList(int capacity) { if (capacity < 0) { throw new IllegalArgumentException("capacity < 0: " + capacity); } array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]); } /** * Constructs a new {@code ArrayList} instance with zero initial capacity. */ public ArrayList() { array = EmptyArray.OBJECT; } /** * This method controls the growth of ArrayList capacities. It represents * a time-space tradeoff: we don't want to grow lists too frequently * (which wastes time and fragments storage), but we don't want to waste * too much space in unused excess capacity. * * NOTE: This method is inlined into {@link #add(Object)} for performance. * If you change the method, change it there too! */ private static int newCapacity(int currentCapacity) { int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ? MIN_CAPACITY_INCREMENT : currentCapacity >> 1); return currentCapacity + increment; }

显而易见，一个ArrayList，默认的容量是12，当剩余的容量不足6的时候，再扩容12，也就是1.5个byte，当大于等于6，则扩容12<<1,也就是扩容6，也就是0.75byte。

这就让我想起了，StringBuilder和StringBuffer的扩容过程，他们的扩容是每当append或者insert新的内容以后，就会直接扩容16，就是2个byte，

那么问题来了，什么时候，触发扩容这个动作呢？就是说什么时候开始扩容呢？

其实很简单，要扩容，当然是因为现在，容量不足了，为什么不足了，当然是因为add元素了啊，那么就简单了，触发这个扩容的操作当然要在数组的增删改查的，增的操作中进行触发了。

增

/** * Inserts the specified object into this {@code ArrayList} at the specified * location. The object is inserted before any previous element at the * specified location. If the location is equal to the size of this * {@code ArrayList}, the object is added at the end. * * @param index * the index at which to insert the object. * @param object * the object to add. * @throws IndexOutOfBoundsException * when {@code location < 0 || location > size()} */ @Override public void add(int index, E object) { Object[] a = array; int s = size; if (index > s || index < 0) { throwIndexOutOfBoundsException(index, s); } if (s < a.length) { System.arraycopy(a, index, a, index + 1, s - index); } else { // assert s == a.length; Object[] newArray = new Object[newCapacity(s)]; System.arraycopy(a, 0, newArray, 0, index); System.arraycopy(a, index, newArray, index + 1, s - index); array = a = newArray; } a[index] = object; size = s + 1; modCount++; } /** * Adds the objects in the specified collection to this {@code ArrayList}. * * @param collection * the collection of objects. * @return {@code true} if this {@code ArrayList} is modified, {@code false} * otherwise. */ @Override public boolean addAll(Collection<? extends E> collection) { Object[] newPart = collection.toArray(); int newPartSize = newPart.length; if (newPartSize == 0) { return false; } Object[] a = array; int s = size; int newSize = s + newPartSize; // If add overflows, arraycopy will fail if (newSize > a.length) { int newCapacity = newCapacity(newSize - 1); // ~33% growth room Object[] newArray = new Object[newCapacity]; System.arraycopy(a, 0, newArray, 0, s); array = a = newArray; } System.arraycopy(newPart, 0, a, s, newPartSize); size = newSize; modCount++; return true; }

你瞧，源码中，就是这么做的。

删

/** * Removes the object at the specified location from this list. * * @param index * the index of the object to remove. * @return the removed object. * @throws IndexOutOfBoundsException * when {@code location < 0 || location >= size()} */ @Override public E remove(int index) { Object[] a = array; int s = size; if (index >= s) { throwIndexOutOfBoundsException(index, s); } @SuppressWarnings("unchecked") E result = (E) a[index]; System.arraycopy(a, index + 1, a, index, --s - index); a[s] = null; // Prevent memory leak size = s; modCount++; return result; } @Override public boolean remove(Object object) { Object[] a = array; int s = size; if (object != null) { for (int i = 0; i < s; i++) { if (object.equals(a[i])) { System.arraycopy(a, i + 1, a, i, --s - i); a[s] = null; // Prevent memory leak size = s; modCount++; return true; } } } else { for (int i = 0; i < s; i++) { if (a[i] == null) { System.arraycopy(a, i + 1, a, i, --s - i); a[s] = null; // Prevent memory leak size = s; modCount++; return true; } } } return false; } @Override protected void removeRange(int fromIndex, int toIndex) { if (fromIndex == toIndex) { return; } Object[] a = array; int s = size; if (fromIndex >= s) { throw new IndexOutOfBoundsException("fromIndex " + fromIndex + " >= size " + size); } if (toIndex > s) { throw new IndexOutOfBoundsException("toIndex " + toIndex + " > size " + size); } if (fromIndex > toIndex) { throw new IndexOutOfBoundsException("fromIndex " + fromIndex + " > toIndex " + toIndex); } System.arraycopy(a, toIndex, a, fromIndex, s - toIndex); int rangeSize = toIndex - fromIndex; Arrays.fill(a, s - rangeSize, s, null); size = s - rangeSize; modCount++; }

改

/** * Replaces the element at the specified location in this {@code ArrayList} * with the specified object. * * @param index * the index at which to put the specified object. * @param object * the object to add. * @return the previous element at the index. * @throws IndexOutOfBoundsException * when {@code location < 0 || location >= size()} */ @Override public E set(int index, E object) { Object[] a = array; if (index >= size) { throwIndexOutOfBoundsException(index, size); } @SuppressWarnings("unchecked") E result = (E) a[index]; a[index] = object; return result; }

查

@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; } @Override public int lastIndexOf(Object object) { Object[] a = array; if (object != null) { for (int i = size - 1; i >= 0; i--) { if (object.equals(a[i])) { return i; } } } else { for (int i = size - 1; i >= 0; i--) { if (a[i] == null) { return i; } } } return -1; }